Skip to main content

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 $\S$6.

Assume that we know the cardinality of $||D_0|| = d$.

Then $D_1 = D_0 {}^{D_0}$, so $||D_1|| = d^d$.

$D_2 = D_1{}^{D_1}$, so $||D_2|| = {(d^d)}^{(d^d)} = d^{d^{(d+1)}}$.

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

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

Or, in the finite case, a nice formula for $||D_n||$ ?

YKY
  • 558
  • 2
  • 10