Skip to main content
7 of 7
|| || -> \lVert \rVert
LSpice
  • 12.9k
  • 4
  • 45
  • 69

What is the cardinality of Dana Scott's $D_{\infty}$?

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$?

YKY
  • 558
  • 2
  • 10