Neha Patil (Editor)

Scott information system

Updated on
Edit
Like
Comment
Share on FacebookTweet on TwitterShare on LinkedInShare on Reddit

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.

Contents

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
    (Text) CC BY-SA