Scott's graph model (\mathcal{P}\omega)

Scott's graph model (commonly referred to as **\mathcal{P}\omega) is a model of the untyped \lambda-calculus.

It is historically the second model of the untyped \lambda-calculus, with D_\infty being the first. It belongs to the class of graph models.

The model is closely related to notions from higher-order computability, in particular enumeration and continuous functionals.

Description

The domain underlying Scott's graph model is the powerset of natural numbers

\mathcal{P}\omega = \{ X \mid X \subseteq \mathbb{N} \}

(The ordinal notation \omega, which is synonymous to \mathbb{N}, is used here.)

Please expand: description of the model.

Nondeterminism

Because every \lambda-term is interpreted as a set of numbers, \mathcal{P}\omega is naturally able to support nondeterminism.

Lattice-theoretic properties

This is known to be an algebraic lattice. This means that it has joins and unions of arbitrary subsets (and hence top and bottom elements); and that every one of its elements can be written as a directed family of compact elements.

In this particular case, algebraicity amounts to the observation that any set of natural numbers is the union of its finite subsets, which are the compact elements:

X = \bigcup_{D \subseteq_\text{fin} X} D

See also

• Graph models

References

• Scott's graph model was introduced in the following landmark paper, while Scott was a professor at the University of Oxford:

@article{scott_1976,
	title = {Data {Types} as {Lattices}},
	volume = {5},
	doi = {10.1137/0205037},
	number = {3},
	journal = {SIAM Journal on Computing},
	author = {Scott, Dana S.},
	year = {1976},
	pages = {522--587},

Previous versions had been published under alternative titles at conference proceedings, as technical reports, etc.