Scott information system - Alchetron, the free social encyclopedia

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

If a ∈ X ∈ C o n then X ⊢ a
If X ⊢ Y and Y ⊢ a , then X ⊢ a
If X ⊢ a then X ∪ { a } ∈ C o n
∀ a ∈ T : { a } ∈ C o n
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

(Text) CC BY-SA