Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
6  
Easy: $\epsilon_0 = \sup \{ \omega, \omega^\omega, \omega^{\omega^\omega}, \ldots \}$. –  Zhen Lin Sep 17 '12 at 4:44
1  
@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

2 Answers 2

up vote 8 down vote accepted

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

share|improve this answer

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

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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