A Scott information system, A, is an ordered triple
-
-
-
satisfying
-
-
-
-
-
Here means
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 , or "infinite recursion," represented by .
Of course, the same construction can be carried out with any other set instead of .
Propositional calculus
edit
The propositional calculus gives us a very simple Scott information system as follows:
-
-
-
Let D be a Scott domain. Then we may define an information system as follows
- the set of compact elements of
-
-
Let be the mapping that takes us from a Scott domain, D, to the information system defined above.
Information systems and Scott domains
edit
Given an information system, , we can build a Scott domain as follows.
- Definition: is a point if and only if
-
-
Let denote the set of points of A with the subset ordering. 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.
- Glynn Winskel: "The Formal Semantics of Programming Languages: An Introduction", MIT Press, 1993 (chapter 12)