5
$\begingroup$

I was recently learning about ordinal collapsing functions, which are a systematic way to produce very large countable ordinals. Before I talk about collapsing functions, I will briefly explain some ordinals:

$$\epsilon_0=\omega^{\omega^{\omega^{\dots}}}\bigg\}\omega\text{ powers going up}$$

$$\epsilon_1=\epsilon_0^{\epsilon_0^{\epsilon_0^{\dots}}}\bigg\}\omega\text{ powers going up}$$

$$\epsilon_2=\epsilon_1^{\epsilon_1^{\epsilon_1^{\dots}}}\bigg\}\omega\text{ powers going up}\\\vdots$$

$\epsilon_\omega$ is thus the limit of this sequence, and from there, we get another ordinal:

$$\zeta_0=\epsilon_{\epsilon_{\epsilon_{\ddots}}}$$

This generalizes into the Veblen function.


We can now tackle the ordinal collapsing function:

$$C(\alpha)=C(\alpha)_0\cup C(\alpha)_1\cup C(\alpha)_2\cup\dots$$

where

$$C(\alpha )_{{n+1}}=C(\alpha )_{n}\cup \{\beta _{1}+\beta _{2},\beta _{1}\beta _{2},{\beta _{1}}^{{\beta _{2}}}:\beta _{1},\beta _{2}\in C(\alpha )_{n}\}\cup \{\psi (\beta ):\beta \in C(\alpha )_{n}\land \beta <\alpha \}$$

$$C(\alpha)_0=\{0,1,\omega,\Omega\}$$

where $\Omega$ is larger than any ordinal we are going to produce (sometimes we set it to be $\omega_1$)

$\psi(\alpha)$ is then the smallest ordinal not in $C(0)$. $\psi(0)$ is seen above, and it is

$$\psi(0)=\epsilon_0$$

Then, $\psi(1)$ is clearly $\epsilon_1$.

We can continue this, and we find that for any $\alpha<\zeta_0$, we have

$$\psi(\alpha)=\epsilon_\alpha$$

But the interesting thing is that we can never surpass $\zeta_0$ due to the forced restriction of "finite combination of..." which is simply beyond the power of $\epsilon_\alpha$, that is

$$\psi(\alpha)=\zeta_0\forall\zeta_0\le\alpha<\Omega$$ and so this is where we pull in the magic $\Omega$:

$$\psi(\Omega)=\zeta_0$$

This now let's us pocket $\zeta_0$ into our $C(\Omega)$ and we can continue on. We get stuck once again at $\zeta_1$, which we bail out using

$$\psi(\Omega\cdot2)=\zeta_1$$

and so on. Eventually, we reach $\psi\left(\Omega^{\Omega^\Omega}\right)$ which is the supremum of Veblen ordinals.

And after that, we reach the supremum of the 'first' ordinal collapsing function, since we can never reach $\psi\left(\Omega^{\Omega^{\Omega^{\Omega^{\dots}}}}\right)$.

We thus introduce $\psi_1(\alpha)$, which is the same as the previous with the only addition that $C_1(0)=\{0,1,\omega,\Omega,\Omega_1\}$, which by using $\Omega_1$, we may now surpass $\psi\left(\Omega^{\Omega^{\Omega^{\Omega^{\dots}}}}\right)$. Likewise, we'll hit a limit, and start all over with $\psi_2(\alpha)$.

And we can go on and on, and perhaps even do some crazy things like

$$\psi_{\psi_\omega(0)}(0)$$

Anyways, I was wondering if the class of all ordinals producible through ordinal collapsing functions is countable or uncountable. I imagine that its countable, though a friend of mine believes it may be uncountable. Does anyone know?

$\endgroup$
  • 4
    $\begingroup$ It's absolutely countable. You can describe all of these ordinals using a finite string of symbols in a finite language (specifically, English). There are only countably many such strings. $\endgroup$ – Reese Mar 7 '17 at 23:08
  • $\begingroup$ @Reese Could you prove that to me? Its not as obvious as I'd like, and I didn't restrict this to a finite amount of function iterations by the way. $\endgroup$ – Simply Beautiful Art Mar 7 '17 at 23:11
  • 1
    $\begingroup$ Every finite string of symbols in a finite language can be coded as a finite integer: represent each symbol by a positive natural, and take the product of $p_i^{a_i}$, where $p_i$ is the $i$th prime and $a_i$ is the $i$th symbol. As for the iterations: where do you stop? If you allow any ordinal number of iterations, then every ordinal is reachable this way. If you require that the number of iterations itself be describable, we're back to countable. $\endgroup$ – Reese Mar 7 '17 at 23:25
  • $\begingroup$ I lost the thread at $\psi(\Omega)$. Up until that point it looked like $\psi$ was a strictly increasing ordinal function, which implies $\psi(\alpha)\ge \alpha$. But then how can $\psi(\Omega)$ possibly be countable if you can set $\Omega=\omega_1$? Did you mean $\Omega=\omega_1^{CK}$? $\endgroup$ – Henning Makholm Mar 7 '17 at 23:34
  • 1
    $\begingroup$ @SimplyBeautifulArt Are you still unsure? Reese's answer seems very good. $\endgroup$ – Deedlit Mar 8 '17 at 7:08
5
$\begingroup$

The set of ordinals expressible in a notation system using an ordinal collapsing function will be countable, because every ordinal will be expressed using a finite set of starting ordinals and a finite set of operations some finite number of times. For example, using the ordinal notation system you give above, we can let

$$C_0=\{0,1,\omega,\Omega\}$$

and

$$C_{{n+1}}=C_{n}\cup \{\beta _{1}+\beta _{2},\beta _{1}\beta _{2},{\beta _{1}}^{{\beta _{2}}}, \psi(\beta):\beta _{1},\beta _{2}\in C_{n}\}$$

Then

$$C = \bigcup_n C_n$$

is the set of all ordinals expressible in this notation system. Each $C_n$ is finite, so $C$ will be countably infinite. The same reasoning goes for any other ordinal collapsing function, except sometimes the starting set or set of operations could be countably infinite; this still leads to a countably infinite set of ordinals.

I feel I must mention that the definition of $\psi_1$ you give is nonstandard. A typical ordinal notation for higher cardinals will be something like:

$$C_0 (\nu, \alpha) = \Omega_\nu \cup \lbrace 0 \rbrace$$

$$C_{n+1} (\nu, \alpha) = \lbrace \beta + \gamma, \varphi(\beta, \gamma), \psi_\mu(\delta) | \beta, \gamma, \delta \in C_n (\nu, \alpha); \delta < \alpha; \nu \le \mu \rbrace $$

$$C (\nu, \alpha) = \bigcup_{n = 1}^{\infty} C_n (\nu,\alpha) $$

$$\psi_\nu (\alpha) = \min \lbrace \beta | \beta \notin C(\nu,\alpha) \rbrace $$

Note in particular that $C_0(1,\alpha)$ contains $\Omega_1$ as a subset, and therefore $\psi_1(\alpha)$ is always uncountable (of cardinality $\Omega_1$). So $\psi_1$ collapses ordinals of large cardinality down to ordinals of cardinality $\Omega_1$, and those large uncountable ordinals help $\psi_0$ produce really large countable ordinals. This is much more powerful than the system you describe; for example, $\psi_{\psi_\omega(0)}(0)$ in your system is going to be much less than $\psi_0(\Omega_3)$ in the standard system.

In this system, the $C_n(\nu,\alpha)$'s will be uncountable for positive $\nu$, so if this is what you meant by "produces" then you can get uncountable sets from ordinal collpsing functions. But, you cannot actually express all the ordinals in $C_n(\nu,\alpha)$; the set of expressible ordinals will be countable, from the previous argument.

$\endgroup$
  • $\begingroup$ Ah, right. It's honestly going to take me a bit to figure out how everything works, especially due to my lack of experience in things like set theory. $\endgroup$ – Simply Beautiful Art Mar 8 '17 at 12:49
  • $\begingroup$ I'm not entirely sure, but did you mean $\mu\le\nu$? $\endgroup$ – Simply Beautiful Art Mar 11 '17 at 14:14
  • $\begingroup$ $\nu \le \mu$ looks correct; we want to be able to access higher order collasping functions from the lower order ones. $\endgroup$ – Deedlit Mar 12 '17 at 20:51
  • $\begingroup$ D: Holy jesus, you need to explain how that would work to me some time! $\endgroup$ – Simply Beautiful Art Mar 12 '17 at 21:12
  • $\begingroup$ Using this definition of ordinal collapsing function, what is the least ordinal not reachable with an ordinal collapse? $\endgroup$ – Zetapology Dec 25 '17 at 7:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.