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?
How to prove that $\epsilon_0$ exists?
-
0I'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
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.
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$.
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) and continuous. "Continuous" means that $f(N) = \sup_{i
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$.