- Scott information system
In
domain theory , a branch ofmathematics andcomputer science , a Scott information system is a primitive kind of logicaldeductive system often used as an alternative way of presentingScott domain s.Definition
A Scott information system, "A", is an ordered triple T, Con, vdash)
* T mbox{ is a set of tokens (the basic units of information)}
* Con subseteq mathcal{P}_f(T) mbox{ the finite subsets of T}
* vdash subseteq Con imes Tsatisfying
# mbox{If } a in X in Conmbox{ then }X vdash a
# mbox{If } X vdash Y mbox{ and }Y vdash a mbox{, then }X vdash a
# mbox{If }X vdash a mbox{ then } X cup a in Con
# forall a in T : { a} in Con
# mbox{If }X in Con mbox{ and} X^prime, subseteq X mbox{ then }X^prime in Con.Here X vdash Y means forall a in Y, X vdash a.
Examples
Propositional calculus
The
propositional calculus gives us a very simple Scott information system as follows:* T := { phi mid phi mbox{ is satisfiable} }
* Con := { X in mathcal{P}_f(T) mid X mbox{ is consistent} }
* X vdash ambox{ iff }X vdash a mbox{ in the propositional calculus}.cott domains
Let "D" be a
Scott domain . Then we may define an information system as follows* T := D^0 the set of
compact element s of D
* Con := { X in mathcal{P}_f(T) mid X mbox{ has an upperbound} }
* X vdash dmbox{ iff }d sqsubseteq igsqcup X.Let mathcal{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, Con, vdash) , we can build a
Scott domain as follows.* Definition: x subseteq T is a point iff
** mbox{If }X subseteq_f x mbox{ then } X in Con
** mbox{If }X vdash a mbox{ and } X subseteq_f x mbox{ then } a in x.Let mathcal{D}(A) denote the set of points of A with the subset ordering. mathcal{D}(A) will be a countable Scott domain when T is countable. In general, for any Scott domain D and information system A
* mathcal{D}(mathcal{I}(D)) cong D
* mathcal{I}(mathcal{D}(A)) cong Awhere the second congruence is given byapproximable mapping s.ee also
*
Scott domain
*Domain theory
Wikimedia Foundation. 2010.