# How to prove that $\epsilon_0$ exists?

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?

-
Easy: $\epsilon_0 = \sup \{ \omega, \omega^\omega, \omega^{\omega^\omega}, \ldots \}$. – Zhen Lin Sep 17 '12 at 4:44
@Zhen Lin: That looks like an answer to me. – Brian M. Scott Sep 17 '12 at 4:49
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. – Zhen Lin Sep 17 '12 at 4:52

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

-

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<b$) and continuous. "Continuous" means that $f(N) = \sup_{i<N} f(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$.

-