3
$\begingroup$

In the 1960's, Dana Scott constructed the domain $D_{\infty}$ which has the property $D_{\infty} \cong D_{\infty}{}^{D_{\infty}}$.

Its construction is based on a cumulative hierarchy of infinite sequences.

For an exposition of its construction one can read the Stenlund (1972) book, “Combinators, $\lambda$-terms and proof theory", Ch1 §6.

Assume that we know the cardinality of $\lVert D_0\rVert = d$.

Then $D_1 = D_0 {}^{D_0}$, so $\lVert D_1\rVert = d^d$.

$D_2 = D_1{}^{D_1}$, so $\lVert D_2\rVert = {(d^d)}^{(d^d)} = d^{d^{(d+1)}}$.

In general, $D_{n+1} = D_n{}^{D_n}$.

Is there a way to express $\lVert D_{\infty}\rVert$ in terms of $d$?

Or, in the finite case, a nice formula for $\lVert D_n\rVert$?

Improve this question
$\endgroup$
21
  • 4
    $\begingroup$ I'm afraid I might be missing something. Assuming $A^A$ means the set of $A$-indexed sequences from $A$, and $\cong$ is something that implies bijection, then it is impossible to have a set with more than one element satisfying $A^A\cong A$. So either I'm missing what $A^A$ means or what $\cong$ means. $\endgroup$
    – Wojowu
    Commented Jan 26, 2021 at 9:44
  • 23
    $\begingroup$ Scott's models are directed-complete partial orders (DCPOs), which form a cartesian closed category, and the exponential $A^B$ of two DCPOs does not consist of all functions from $B$ to $A$, but only those which preserve directed joins. Therefore it is not correct to say that $|A^B| = |A|^{|B|}$ (the cardinal exponential on the right counts all functions). I may come back to say more about the question, but there is nothing shocking going on. $\endgroup$
    – Todd Trimble
    Commented Jan 26, 2021 at 10:59
  • 3
    $\begingroup$ In light of @ToddTrimble's comment, I am not sure if your question remains well-founded, since his comment seems to indicate that some of your assertions about cardinalities is incorrect. Moreover, I don't quite understand what you expect the cardinality to be; if each $D_n$ is finite then the cardinality of $D_\infty$ is going to either be finite or countably infinite. Todd's comment also seems to indicate that cardinality is not really the right notion of "size" for $D_\infty$ anyway $\endgroup$
    – Yemon Choi
    Commented Jan 26, 2021 at 16:46
  • 8
    $\begingroup$ @AlexNelson Ordinal exponentiation is about something else altogether. $\endgroup$
    – Todd Trimble
    Commented Jan 26, 2021 at 19:44
  • 3
    $\begingroup$ @YemonChoi: That is incorrect, $D_\infty$ is either trivial or uncountable, depending on $D_0$. And it is not at all the case that a limit of finite object need be finite. Already the cartesian product of countably many sets of size two is uncountable. $\endgroup$
    – Andrej Bauer
    Commented Jan 27, 2021 at 15:54

1 Answer 1

Reset to default
11
$\begingroup$

If you take $D_0$ to be the two-element chain, $D_1\cong(D_0\to D_0)$ is the three-element chain consisting of order-preserving endofunctions of $D_0$ (not a $4=2^2$-element set). Then $D_2$ is a lattice with ten elements (not $27=3^3$).

It is then a combinatorial question how big the subsequent lattices are; maybe someone can find the sequence using suitable software.

In the limit, there are countably many compact elements of $D_\infty$. The classical cardinality of $D_\infty$ is that of $P{\mathbb N}$.

Then $D_\infty\cong[D_\infty\to D_\infty]$, meaning the domain of functions that preserve directed joins.

Dana Scott discovered this and the "$P\omega$" model of the untyped $\lambda$-calculus after previously believing there was no "mathematical" model of it. (Of course he knew from Church–Rosser that it is syntactically consistent.)

See Scott on the consistency of the lambda calculus for further discussion of that history.

I'm struggling to find where Scott first introduced the $D_\infty$ model, but there is a paragraph about it in An Outline of a Mathematical Theory of Computation.

I removed the "cardinality" tags from this question because they are misleading, cf. @Wojowu's (1 2) and @ToddTrimble's (1) comments above.

Improve this answer
$\endgroup$
8
  • 2
    $\begingroup$ The size of $D_n$ is $\binom{2n+1}{n}$, as in oeis.org/A001700 $\endgroup$
    – user44143
    Commented Jan 27, 2021 at 15:45
  • 2
    $\begingroup$ @LSpice en.wikipedia.org/wiki/Compact_element $\endgroup$
    – Emil Jeřábek
    Commented Jan 27, 2021 at 15:51
  • 1
    $\begingroup$ @MattF. Why is that? I can’t find anything relevant in the (long) comment section of that OEIS page. $\endgroup$
    – Emil Jeřábek
    Commented Jan 27, 2021 at 15:53
  • 5
    $\begingroup$ In fact, since $D_2$ has height $7$, $D_3=D_2\to D_2$ contains a copy of $\{1,\dots,7\}\to\{1,\dots,7\}$ (where $\{1,\dots,7\}$ is linearly ordered). The size of the latter is $\mathrm{A001700}(6)=\binom{13}6=1716$, much more than $\mathrm{A001700}(3)=\binom73=35$. $\endgroup$
    – Emil Jeřábek
    Commented Jan 27, 2021 at 16:08
  • 3
    $\begingroup$ A (probably very crude) lower bound: it is easy to see that if $P$ is a finite lattice of height $h+1$, then $P\to P$ includes a copy of $P\to\{0,\dots,h\}$, which has height $h|P|+1\ge(h+1)h+1>h^2+1$. It follows by induction on $n$ that $D_{n+1}$ has height (and therefore size) more than $2^{2^n}$. $\endgroup$
    – Emil Jeřábek
    Commented Jan 27, 2021 at 16:27

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .