Scott information system

Updated on

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 , C o n , )

• T  is a set of tokens (the basic units of information)
• C o n P f ( T )  the finite subsets of T
• ⊢⊆ ( C o n { } ) × T
• satisfying

1. If  a X C o n  then  X a
2. If  X Y  and  Y a , then  X a
3. If  X a  then  X { a } C o n
4. a T : { a } C o n
5. If  X C o n  and  X X  then  X C o n .

Here X Y means a Y , X 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:

• T := N
• C o n := { } { { n } n N }
• X a  iff  a X .
• That is, the result can either be a natural number, represented by the singleton set { n } , or "infinite recursion," represented by .

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

Propositional calculus

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

• T := { ϕ ϕ  is satisfiable }
• C o n := { X P f ( T ) X  is consistent }
• X a  iff  X a  in the propositional calculus .
• Scott 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
• C o n := { X P f ( T ) X  has an upper bound }
• X d  iff  d X .
• Let 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 , C o n , ) , we can build a Scott domain as follows.

• Definition: x T is a point iff
• If  X f x  then  X C o n
• If  X a  and  X f x  then  a x .
• Let D ( A ) denote the set of points of A with the subset ordering. D ( A ) will be a countably based Scott domain when T is countable. In general, for any Scott domain D and information system A

• D ( I ( D ) ) D
• I ( D ( A ) ) A
• where the second congruence is given by approximable mappings.

References

Scott information system Wikipedia

Similar Topics
Came the Brawn
Ibrahim Balla
Pat Steir
Topics