Talk:Scott domain

[Untitled]

The definition given in Chapter 12 of Winskel's "The Formal Semantics of Programming Languages" (1993) requires that a Scott domain be omega-algebraic. This definition may be a little dated, but anyway... In turn, omega-algebraic requires that the set of finite elements of the domain be countable. What, if any, part of the definition (currently) given in the article corresponds to that requirement? It seems to be important, as it's used in the book to show that general function spaces are not Scott (pre)domains. --Malcohol 13:11, 24 April 2006 (UTC)

What does omega-algebraic mean exactly? The definitions I can find are all from FOLDOC and seem to mean "algebraic, and the set of compacts is countable". The following argument is based on that, but it could be that the definition is poorly worded and really means "each element is the sup of its compact approximations of which there are at most countably many", which is a weaker definition that includes the example below.

With the usual construction of domains from bottom, binary separated or amalgamated sum, binary product and fixpoints, they usually turn out (by induction) to be omega-algebraic anyway. The only way they could be non-omega-algebraic is if the specialisation ordering is infinitely branching. For example let $\mathbb {N} _{\bot }$ be the flat domain of natural numbers (all elements incomparable except $\forall x.\bot \leq x$) and $F(D)=D\times F(D)$ the domain of streams of $D$ (defined as the greatest fixpoint of $F'(F)(D)=D\times F(D)$). By diagonalisation $F(\mathbb {N} _{\bot })$ has uncountably many non-compact elements (which include all the fully specified streams, i.e. it's a superset of Baire space). Since for each non-compact element there are infinitely many compact approximations, there are uncountably many compact elements as well, hence this domain is not omega-algebraic.

Anyway, there are domains that are function spaces, but all functions in them are Scott-continuous. Not all functions between two domains that exist set-theoretically can be included in such a domain because it would be too big in some sense (I forget exactly what, but Mathematical Theory of Domains, Cambridge Tracts in Theoretical Computer Science 22 will tell you). Hairy Dude (talk) 00:02, 17 February 2010 (UTC)

(Aside: By "Baire space" I mean $\mathbb {N} ^{\omega }$, which definition I was taught in contrast to Cantor space, i.e. $2^{\omega }$.) Hairy Dude (talk) 00:17, 17 February 2010 (UTC)

There is a flaw in the preceding argument that $F(\mathbb {N} _{\bot })$ were uncountably based. You wrote "for each non-compact element there are infinitely many compact approximations". But the sets of compact approximations are not pairwise disjoint, and one may not conclude from it that "there are uncountably many compact elements". In fact, $F(\mathbb {N} _{\bot })$ is countably based, because it has countably many compact element. To see it, pick arbitrary compact element $c\in F(\mathbb {N} _{\bot })$ and let $A$ be the set of elements $e$ such that $e\leq c$ and $e$ is specified at finitely many entries. Then $A$ is directed and $c\leq \sup A$. By the definition of compactness, there exists $e'\in A$ such that $c\leq e'$, so $c$ is specified at finitely many entries. The set of finite sequences of natural numbers is countable. EvenEntity (talk) 11:12:00, 29 September 2016 (UTC)

Supremum Explanation

I wanted to point out that this explanation

"Obviously, such a supremum only exists (i.e., makes sense) provided X does not contain inconsistent information; hence the domain is directed and bounded complete, but not all suprema necessarily exist."

seems confused w.r.t the original paper of Dana Scott, Outline of a Mathematical Theory of Computation, 1970. In the original paper, every subset X of D has a supremum. The supremum T of a domain D is described as an overdetermination, such that for x,y in D, x U y = T intuitively means that x and y are inconsistent with each other. — Preceding unsigned comment added by 2001:b07:644e:c37f:fdeb:ef8b:6c7f:4da1 (talk • contribs) 23:04, 11 November 2020 (UTC)

Now I don't remember everything I once knew about domains, but I can be quite clear that the definitions didn't come from a 1970 paper, which incidentally I haven't read. Denotational semantics as a field did not spring fully formed from the mind of Dana Scott in 1970, so it's unsurprising that the definitions there are different. Rather the definitions here came from a book, from the "Cambridge Tracts in Theoretical Computer Science" series, with the teal cover. I think it was Mathematical Theory of Domains by Stoltenberg-Hansen, Lindström & Griffor, from 1994. There "Scott domain" means "algebraic bounded-complete dcpo", a structure defined precisely so as to get rid of the inconsistent suprema. Specifically, it does not require that all suprema exist, only that "has an upper bound" is equivalent to "has a least upper bound". Hairy Dude (talk) 01:07, 20 May 2022 (UTC)