Scott information system

In domain theory, a branch of mathematics and computer science, a Scott information system is a primitive kind of logical deductive system often used as an alternative way of presenting Scott domains.

Definition

A Scott information system, "A", is an ordered triple $(T,\; Con,\; vdash)$
* $T\; mbox\{\; is\; a\; set\; of\; tokens\; (the\; basic\; units\; of\; information)\}$
* $Con\; subseteq\; mathcal\{P\}\_f(T)\; mbox\{\; the\; finite\; subsets\; of\; T\}$
* $vdash\; subseteq\; Con\; imes\; T$satisfying
# $mbox\{If\; \}\; a\; in\; X\; in\; Conmbox\{\; then\; \}X\; vdash\; a$
# $mbox\{If\; \}\; X\; vdash\; Y\; mbox\{\; and\; \}Y\; vdash\; a\; mbox\{,\; then\; \}X\; vdash\; a$
# $mbox\{If\; \}X\; vdash\; a\; mbox\{\; then\; \}\; X\; cup\; a\; in\; Con$
# $forall\; a\; in\; T\; :\; \{\; a\}\; in\; Con$
# $mbox\{If\; \}X\; in\; Con\; mbox\{\; and\}\; X^prime,\; subseteq\; X\; mbox\{\; then\; \}X^prime\; in\; Con.$

Here $X\; vdash\; Y$ means $forall\; a\; in\; Y,\; X\; vdash\; a.$

Examples

Propositional calculus

The propositional calculus gives us a very simple Scott information system as follows:

* $T\; :=\; \{\; phi\; mid\; phi\; mbox\{\; is\; satisfiable\}\; \}$
* $Con\; :=\; \{\; X\; in\; mathcal\{P\}\_f(T)\; mid\; X\; mbox\{\; is\; consistent\}\; \}$
* $X\; vdash\; ambox\{\; iff\; \}X\; vdash\; a\; mbox\{\; in\; the\; propositional\; calculus\}.$

cott domains

Let "D" be a Scott domain. Then we may define an information system as follows

* $T\; :=\; D^0$ the set of compact elements of D
* $Con\; :=\; \{\; X\; in\; mathcal\{P\}\_f(T)\; mid\; X\; mbox\{\; has\; an\; upperbound\}\; \}$
*

Let $mathcal\{I\}$ be the mapping that takes us from a Scott domain, "D", to the information system defined above.

Information systems and Scott domains

Given an information system, $A\; =\; (T,\; Con,\; vdash)$, we can build a Scott domain as follows.

* Definition: $x\; subseteq\; T$ is a point iff
** $mbox\{If\; \}X\; subseteq\_f\; x\; mbox\{\; then\; \}\; X\; in\; Con$
** $mbox\{If\; \}X\; vdash\; a\; mbox\{\; and\; \}\; X\; subseteq\_f\; x\; mbox\{\; then\; \}\; a\; in\; x.$

Let $mathcal\{D\}(A)$ denote the set of points of A with the subset ordering. $mathcal\{D\}(A)$ will be a countable Scott domain when T is countable. In general, for any Scott domain D and information system A
* $mathcal\{D\}(mathcal\{I\}(D))\; cong\; D$
* $mathcal\{I\}(mathcal\{D\}(A))\; cong\; A$where the second congruence is given by approximable mappings.

ee also

* Scott domain
* Domain theory