2
$\begingroup$

How do we prove that $\epsilon_0$ exists? The definition of $\epsilon_0$ says that $\omega^{\epsilon_0} = \epsilon_0$. So, how do we know whether such number exists?

  • 0
    I'm not sure the OP will think so. There are many subtleties I didn't address: Why does the set $\{ \omega, \omega^\omega, \omega^{\omega^\omega}, \ldots \}$ exist in the first place? How do we know this is the _least_ fixed point of the function $\alpha \mapsto \omega^\alpha$? And so on. It would be best if the OP asks a more specific question. – 2012-09-17

2 Answers 2

9

There are two ways of doing this. The first way is not too constructive and does not reveal a whole lot, but it proves the existence of $\varepsilon$ numbers nonetheless.

  1. First note that $\omega_1$ exists. This is true because the collection of countable ordinals is uncountable.

    Now note that $\omega^{\omega_1}$ (in ordinal exponentiation!) is simply $\omega_1$. So there exists an ordinal for which $\alpha=\omega^\alpha$, therefore there exists a minimal ordinal with this property, and that is $\varepsilon_0$.

  2. We can define $\varepsilon_0=\sup\{\omega,\omega^\omega,\omega^{\omega^\omega},\ldots\}$, namely the least ordinal above the sequence $\alpha_0=\omega;\alpha_{n+1}=\omega^{\alpha_n}$.

    Again, we observe that this set of ordinals actually exists and this is true because of induction arguments and replacement axioms.

    Now we can prove that $\varepsilon_0$ has the property $\omega^{\varepsilon_0}=\varepsilon_0$, again this follows from the definition of ordinal exponentiation and the fact that $\varepsilon_0$ is the limit of the aforementioned sequence.

    Lastly, we need to prove that there is no smaller ordinal with this property, but this is simple. Clearly there is no one below $\omega$, and by induction we can show that there is no such ordinal between $\alpha_n$ and $\alpha_{n+1}$ for all $n$.

8

You can prove that any "normal" function $f$ on ordinals has a fixed point, which is an ordinal $x$ such that $f(x)=x$, and indeed every such function has an infinite sequence of fixed points. This is called the fixed-point lemma.

A "normal" function is one which is strictly increasing (that is, $f(a) < f(b)$ whenever $a) and continuous. "Continuous" means that $f(N) = \sup_{i whenever $N$ is a limit ordinal. One example of a normal function is the function $x\mapsto 1+x$. A non-example is the function $x\mapsto x+1$, since it does not have $f(\omega) = \sup_{i<\omega} i+1$; the left side is $\omega + 1$ but the right side is only $\omega$.

Now the function $x\mapsto \omega^x$ is easily shown to be normal, and so by the fixed-point lemma, it has a fixed point. Since the set of fixed points is a nonempty set of ordinals, it has a least element, and we call this least fixed point $\epsilon_0$.

One can similarly define:

  • $\omega$ as the least fixed point of the function $x\mapsto 1+x$;
  • $\omega\cdot 2$ as the next-least fixed point of the same function;
  • $\omega^2$ as the least fixed point of the function $x\mapsto \omega+ x$;
  • $\omega^\omega$ as the least fixed point of the function $x\mapsto \omega\cdot x$;
  • etc.

The fixed-point lemma also implies that the function $x\mapsto \epsilon_x$ has a fixed point… and so too the function that takes ordinal $x$ to the smallest ordinal with cardinality $\aleph_x$.