Scott's graph model

Scott's graph model is a model of the untyped \lambda-calculus. It was discovered by Dana Scott in the mid-1970s, and presented in the landmark paper Scott 1976.

The carrier of the model is the set

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

of subsets of natural numbers (where we use the ordinal notation \omega to stand for natural numbers).

The graph model has strong connections with both the notion of continuity from domain theory, but also various notions from computability theory.

Construction

As a topological space, through Sierpiński

Let \Sigma \triangleq \{ \bot, \top \} be the Sierpiński space, with the usual topology. Then the graph model is homeomorphic to its infinite product:

	\mathcal{P}\omega \cong \Sigma^\omega

See Scott 1976, Appendix A.

References

@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},
	file = {Attachment:C\:\\Users\\tz20861\\Zotero\\storage\\CM9NV7SM\\Scott - 1976 - Data Types as Lattices.pdf:application/pdf},
}