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.


A Scott information system, A, is an ordered triple (T, Con, \vdash)


  1. \mbox{If } a \in X \in Con\mbox{ then }X \vdash a
  2. \mbox{If } X \vdash Y \mbox{ and }Y \vdash a \mbox{, then }X \vdash a
  3. \mbox{If }X \vdash a \mbox{ then } X \cup \{ a \} \in Con
  4. \forall a \in T : \{ a\} \in Con
  5. \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.


Natural numbers

The return value of a partial recursive function, which either returns a natural number or goes into an infinite recursion, can be expressed as a simple Scott information system as follows:

That is, the result can either be a natural number, represented by the singleton set \{n\}, or "infinite recursion," represented by \empty.

Of course, the same construction can be carried out with any other set instead of \mathbb{N}.

Propositional calculus

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

Scott domains

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

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.

Let \mathcal{D}(A) denote the set of points of A with the subset ordering. \mathcal{D}(A) will be a countably based Scott domain when T is countable. In general, for any Scott domain D and information system A

where the second congruence is given by approximable mappings.

See also


This article is issued from Wikipedia - version of the 3/17/2013. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.