In this post, I'll present a nice application of ordinals (specifically, transfinite induction/recursion) in order to arrive at a result of basic Real Analysis.
It is of my opinion that the Least Upper Bound axiom is a strong one, which usually has never been thought before by a student by the time he first learns it. As I've already argued before with some colleagues, having a least upper bound for any subset of $\mathbb{R}$ which is bounded by above is quite a statement. Subsets of $\mathbb{R}$ can be quite weird and difficult to handle (see, for instance, the Continuum Hypothesis).
However, it is of natural intuition that every increasing, bounded sequence of real numbers converges. This is a simple statement, and one that even a high-school student can easily understand and agree with after some thought (and maybe persuasion).
It is a basic fact of analysis that the Least Upper Bound axiom implies what we will call the Monotone Convergence Axiom for Sequences (MCAS, shortly): every increasing, bounded sequence of real numbers converges.
We will prove that MCAS implies the Least Upper Bound axiom. More precisely, we will prove that:
Theorem: If $\mathbb{R}$ is an ordered field containing the rational numbers (with its usual order) and which satisfies the MCAS, then $\mathbb{R}$ satisfies the Least Upper Bound axiom.
It is an easy consequence of MCAS that $\mathbb{R}$ satisfies the Archimedean Property, that is:
Proposition: For every $x,y>0$, there exists $n>0$ such that
$$nx>y.$$
Proof: If the proposition was false, then the sequence $nx$ would be bounded. Since it is clearly increasing, we would have that $nx \rightarrow a$ for some $a$. Note that $(n+1)x$ is a subsequence, hence we would have that $a=a+x \implies x=0$, a contradiction.
It also follows easily the density of rationals (this only uses the Archimedean Property). We leave this as an exercise.
Now, we want to prove that $\mathbb{R}$ satisfies the Least Upper Bound axiom. Therefore, take $A \subset \mathbb{R}$ bounded by above. We must prove that $A$ has a least upper bound.
A first idea would be to take an increasing sequence of elements of $A$ and hope for it to converge to what should be the least upper bound. However, this clearly is not intelligent enough, since the following situation could happen
One might be tempted to abandon this idea and pursue something with more finesse. However, stubbornness can also yield fruitful results. The idea is... keep doing this. Do it, and if the limit of your sequence is not a least upper bound, do it again. Then repeat and repeat etc etc. If you do this, but do it really fast, being able to jump infinite cases which prove not to be useful, you have to be right eventually.
That is the core idea. We now proceed with the proof:
Suppose $A$ has no least upper bound.
Consider the set $\Omega$ (the least uncountable ordinal. Remember that $\Omega=[0,\Omega)$). We will define a function $f: \Omega \rightarrow \mathbb{Q}$ by transfinite recursion.
Take $f(0)$ to be any rational smaller than an element of $A$.
Given $f(a)$, take $f(a+1)$ to be a rational greater than $f(a)$ and smaller than an element of $A$.
Given a limit ordinal $\gamma$, suppose we have defined an increasing function on the ordinals for all ordinals $\beta$ smaller than $\gamma$ in such a way that each $f(\beta)$ is smaller than some $b \in A$. We have that there exists an increasing sequence of ordinals $\alpha_n$ smaller than $\gamma$ that converges to the limit ordinal (order topology). The associated $f(\alpha_n)$ is a bounded increasing sequence of real numbers, hence converge to a given real number $x$. Take a rational number which is greater than $x$, and smaller than an element of $A$ (this is guaranteed by the assumption that there is no least upper bound of $A$), and make $f(\gamma)$ to be this rational number. This completes the construction of $f$. We have thus constructed an injection from $\Omega$ to $\mathbb{Q}$. But $\Omega$ isn't enumerable, so we have reached a contradiction.
It is of my opinion that the Least Upper Bound axiom is a strong one, which usually has never been thought before by a student by the time he first learns it. As I've already argued before with some colleagues, having a least upper bound for any subset of $\mathbb{R}$ which is bounded by above is quite a statement. Subsets of $\mathbb{R}$ can be quite weird and difficult to handle (see, for instance, the Continuum Hypothesis).
However, it is of natural intuition that every increasing, bounded sequence of real numbers converges. This is a simple statement, and one that even a high-school student can easily understand and agree with after some thought (and maybe persuasion).
It is a basic fact of analysis that the Least Upper Bound axiom implies what we will call the Monotone Convergence Axiom for Sequences (MCAS, shortly): every increasing, bounded sequence of real numbers converges.
We will prove that MCAS implies the Least Upper Bound axiom. More precisely, we will prove that:
Theorem: If $\mathbb{R}$ is an ordered field containing the rational numbers (with its usual order) and which satisfies the MCAS, then $\mathbb{R}$ satisfies the Least Upper Bound axiom.
It is an easy consequence of MCAS that $\mathbb{R}$ satisfies the Archimedean Property, that is:
Proposition: For every $x,y>0$, there exists $n>0$ such that
$$nx>y.$$
Proof: If the proposition was false, then the sequence $nx$ would be bounded. Since it is clearly increasing, we would have that $nx \rightarrow a$ for some $a$. Note that $(n+1)x$ is a subsequence, hence we would have that $a=a+x \implies x=0$, a contradiction.
It also follows easily the density of rationals (this only uses the Archimedean Property). We leave this as an exercise.
Now, we want to prove that $\mathbb{R}$ satisfies the Least Upper Bound axiom. Therefore, take $A \subset \mathbb{R}$ bounded by above. We must prove that $A$ has a least upper bound.
A first idea would be to take an increasing sequence of elements of $A$ and hope for it to converge to what should be the least upper bound. However, this clearly is not intelligent enough, since the following situation could happen
One might be tempted to abandon this idea and pursue something with more finesse. However, stubbornness can also yield fruitful results. The idea is... keep doing this. Do it, and if the limit of your sequence is not a least upper bound, do it again. Then repeat and repeat etc etc. If you do this, but do it really fast, being able to jump infinite cases which prove not to be useful, you have to be right eventually.
That is the core idea. We now proceed with the proof:
Suppose $A$ has no least upper bound.
Consider the set $\Omega$ (the least uncountable ordinal. Remember that $\Omega=[0,\Omega)$). We will define a function $f: \Omega \rightarrow \mathbb{Q}$ by transfinite recursion.
Take $f(0)$ to be any rational smaller than an element of $A$.
Given $f(a)$, take $f(a+1)$ to be a rational greater than $f(a)$ and smaller than an element of $A$.
Given a limit ordinal $\gamma$, suppose we have defined an increasing function on the ordinals for all ordinals $\beta$ smaller than $\gamma$ in such a way that each $f(\beta)$ is smaller than some $b \in A$. We have that there exists an increasing sequence of ordinals $\alpha_n$ smaller than $\gamma$ that converges to the limit ordinal (order topology). The associated $f(\alpha_n)$ is a bounded increasing sequence of real numbers, hence converge to a given real number $x$. Take a rational number which is greater than $x$, and smaller than an element of $A$ (this is guaranteed by the assumption that there is no least upper bound of $A$), and make $f(\gamma)$ to be this rational number. This completes the construction of $f$. We have thus constructed an injection from $\Omega$ to $\mathbb{Q}$. But $\Omega$ isn't enumerable, so we have reached a contradiction.
RSS Feed
