Neha Patil

Scott information system

Updated on
Share on FacebookTweet on TwitterShare on LinkedIn

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


    Similar Topics
    Came the Brawn
    Ibrahim Balla
    Pat Steir
    Topics