- Source: Scott information system
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
,
⊢
)
{\displaystyle (T,Con,\vdash )}
T
is a set of tokens (the basic units of information)
{\displaystyle T{\mbox{ is a set of tokens (the basic units of information)}}}
C
o
n
⊆
P
f
(
T
)
the finite subsets of
T
{\displaystyle Con\subseteq {\mathcal {P}}_{f}(T){\mbox{ the finite subsets of }}T}
⊢
⊆
(
C
o
n
∖
{
∅
}
)
×
T
{\displaystyle {\vdash }\subseteq (Con\setminus \lbrace \emptyset \rbrace )\times T}
satisfying
If
a
∈
X
∈
C
o
n
then
X
⊢
a
{\displaystyle {\mbox{If }}a\in X\in Con{\mbox{ then }}X\vdash a}
If
X
⊢
Y
and
Y
⊢
a
, then
X
⊢
a
{\displaystyle {\mbox{If }}X\vdash Y{\mbox{ and }}Y\vdash a{\mbox{, then }}X\vdash a}
If
X
⊢
a
then
X
∪
{
a
}
∈
C
o
n
{\displaystyle {\mbox{If }}X\vdash a{\mbox{ then }}X\cup \{a\}\in Con}
∀
a
∈
T
:
{
a
}
∈
C
o
n
{\displaystyle \forall a\in T:\{a\}\in Con}
If
X
∈
C
o
n
and
X
′
⊆
X
then
X
′
∈
C
o
n
.
{\displaystyle {\mbox{If }}X\in Con{\mbox{ and }}X^{\prime }\,\subseteq X{\mbox{ then }}X^{\prime }\in Con.}
Here
X
⊢
Y
{\displaystyle X\vdash Y}
means
∀
a
∈
Y
,
X
⊢
a
.
{\displaystyle \forall a\in Y,X\vdash a.}
Examples
= 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
{\displaystyle T:=\mathbb {N} }
C
o
n
:=
{
∅
}
∪
{
{
n
}
∣
n
∈
N
}
{\displaystyle Con:=\{\emptyset \}\cup \{\{n\}\mid n\in \mathbb {N} \}}
X
⊢
a
⟺
a
∈
X
.
{\displaystyle X\vdash a\iff a\in X.}
That is, the result can either be a natural number, represented by the singleton set
{
n
}
{\displaystyle \{n\}}
, or "infinite recursion," represented by
∅
{\displaystyle \emptyset }
.
Of course, the same construction can be carried out with any other set instead of
N
{\displaystyle \mathbb {N} }
.
= Propositional calculus
=
The propositional calculus gives us a very simple Scott information system as follows:
T
:=
{
ϕ
∣
ϕ
is satisfiable
}
{\displaystyle T:=\{\phi \mid \phi {\mbox{ is satisfiable}}\}}
C
o
n
:=
{
X
∈
P
f
(
T
)
∣
X
is consistent
}
{\displaystyle Con:=\{X\in {\mathcal {P}}_{f}(T)\mid X{\mbox{ is consistent}}\}}
X
⊢
a
⟺
X
⊢
a
in the propositional calculus
.
{\displaystyle X\vdash a\iff X\vdash a{\mbox{ in the propositional calculus}}.}
=
Let D be a Scott domain. Then we may define an information system as follows
T
:=
D
0
{\displaystyle T:=D^{0}}
the set of compact elements of
D
{\displaystyle D}
C
o
n
:=
{
X
∈
P
f
(
T
)
∣
X
has an upper bound
}
{\displaystyle Con:=\{X\in {\mathcal {P}}_{f}(T)\mid X{\mbox{ has an upper bound}}\}}
X
⊢
d
⟺
d
⊑
⨆
X
.
{\displaystyle X\vdash d\iff d\sqsubseteq \bigsqcup X.}
Let
I
{\displaystyle {\mathcal {I}}}
be the mapping that takes us from a Scott domain, D, to the information system defined above.
Given an information system,
A
=
(
T
,
C
o
n
,
⊢
)
{\displaystyle A=(T,Con,\vdash )}
, we can build a Scott domain as follows.
Definition:
x
⊆
T
{\displaystyle x\subseteq T}
is a point if and only if
If
X
⊆
f
x
then
X
∈
C
o
n
{\displaystyle {\mbox{If }}X\subseteq _{f}x{\mbox{ then }}X\in Con}
If
X
⊢
a
and
X
⊆
f
x
then
a
∈
x
.
{\displaystyle {\mbox{If }}X\vdash a{\mbox{ and }}X\subseteq _{f}x{\mbox{ then }}a\in x.}
Let
D
(
A
)
{\displaystyle {\mathcal {D}}(A)}
denote the set of points of A with the subset ordering.
D
(
A
)
{\displaystyle {\mathcal {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
{\displaystyle {\mathcal {D}}({\mathcal {I}}(D))\cong D}
I
(
D
(
A
)
)
≅
A
{\displaystyle {\mathcal {I}}({\mathcal {D}}(A))\cong A}
where the second congruence is given by approximable mappings.
See also
Scott domain
Domain theory
References
Glynn Winskel: "The Formal Semantics of Programming Languages: An Introduction", MIT Press, 1993 (chapter 12)
Kata Kunci Pencarian:
5.5
7.348
7.667
4.8
6.9
6.934
7.077
6.458
4.6
7.018
No More Posts Available.
No more pages to load.
