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.

I want to describe Ordinals using as much low-level mathematics as possible, but I need examples in order to explain the general idea. I want to show how certain mathematical objects are constructed using transfinite recursion, but can't think of anything simple and yet not artificial looking. The simplest natural example I have are Borel sets, which can be defined via transfinite recursion, but I think it's already too much (another example are Conway's Surreal numbers, but that again may already be too much).

share|improve this question
    
Would proving Zorn be too much? Or special cases, like a Hamel basis for $\mathbb{R}$ over $\mathbb{Q}$ and additive nonlinear functions? –  Chris Eagle May 24 '11 at 7:13
2  
Have you seen dpmms.cam.ac.uk/~wtg10/ordinals.html ? –  Qiaochu Yuan May 24 '11 at 7:47
5  
It is not a bad idea to go back to the original motivation of Cantor. As usual let $A'$, the derived set of $A$, as the set of limit points of $A$. Then we can define the $n$-th derived set $A^{(n)}$ of $A$, and wish to continue the idea beyond the finite. One can then mention the result about trigonometric series that he obtained. –  André Nicolas May 24 '11 at 12:40
    
6312 - Thanks, this was exactly my first example, but I want another, maybe a little more "clean". –  Gadi A May 24 '11 at 12:45
    
I posted some introductory notes on ordinal numbers at groups.google.com/group/sci.math/msg/24bd786487c5b493 and I intended to follow these up as explained at groups.google.com/group/sci.math/msg/1b9648b625951c95 Perhaps something there can be of use, as many of the arithmetic results I stated can be proved by transfinite induction. I wound up not posting the rest of my handwritten notes because I got busy at work and also I decided that I was wasting way too much time trying to format things like this in ASCII, rather than putting my efforts towards LaTeX'ing my writings. –  Dave L. Renfro Nov 8 '11 at 22:04

3 Answers 3

up vote 6 down vote accepted

You might find something useful in this post by Tim Gowers: http://www.dpmms.cam.ac.uk/~wtg10/ordinals.html. Especially his first example, with (countable) ordinals introduced as a convenient notation for indexing an increasing sequence of bounded increasing sequences (and so on in many levels perhaps), was quite illuminating for me.

That is, if $a_n \nearrow a$, and $a < b_n \nearrow b$, and $b < c_n \nearrow c$, etc., we will have the notational problem of running out of letters after a while. But we can instead write $a_{\omega}$ instead of $a$, and $a_{\omega+n}$ instead of $b_n$, and $a_{2\omega}$ instead of $b$, and $a_{2\omega+n}$ instead of $c_n$, etc., and thus index all the numbers using a single symbol $a$ with ordinals attached as subscripts. Even countably many sequences will not be a problem, since then we just denote the limit of the sequence $(a_{n\omega})_{n=1}^{\infty}$ by $a_{\omega^2}$. And so on...

share|improve this answer
    
There really should be a "new comments have been posted" notification... Qiaochu's comment wasn't there when I started writing. Well, I'll leave the answer as it is anyway. –  Hans Lundmark May 24 '11 at 8:12
    
I like his game-based example most and I think I'll use it. Thanks for the link - it's a very good post. –  Gadi A May 25 '11 at 6:58

I think that the most pedagogical way of looking at ordinals is the task: How do you write the (sufficiently simple) expressions for arbitrarily large - usually extremely large - integers by addition, multiplication, and exponentiation involving a few small numbers such as $1,2,3,4,5$ and a few others as well as one million that you represent by $\omega=1,000,000$?

Well, you may write $\omega$ itself but you may also write $\omega+\omega$ or $\omega^\omega+2\omega^3+5$ or any ordinal. If $\omega$ is as small as a million, you could get wrong identities such as $[(1+1+1+1+1)(1+1)]^{1+1+1+1+1+1}=\omega$ but if $\omega$ is really large, those identities disappear and any formal prescription using $\omega$ is different.

The key feature that makes ordinals with an abstract $\omega$ worth considering is that the ordering - which of two expressions $A,B$ viewed as functions of $\omega$ is greater - doesn't depend on $\omega$ if $\omega$ is really large. So one may define the ordering $A<B$ or $A>B$ as the limit of the relationship between the evaluations of the functions of $\omega$ for which you substitute a positive integer number sent to infinity.

share|improve this answer
6  
However large you make $\omega$, you'll get wrong identities like $1+\omega=\omega+1$. –  Chris Eagle May 24 '11 at 7:19
    
This sucks. I didn't know that $1+\omega$ was $\omega$. What's the purpose of such a noncommutative "addition"? –  Luboš Motl May 25 '11 at 9:01
4  
Unlike the commutative version, it actually corresponds to a natural operation on ordered sets. $\alpha + \beta$ is the order type of an order of length $\alpha$ followed by an order of length $\beta$. –  Chris Eagle May 25 '11 at 13:13
    
But there is also a natural commutative addition defined on ordinals: en.wikipedia.org/wiki/Cantor_normal_form#Natural_operations –  JDH Nov 8 '11 at 15:50

Some accessible applications transfinite induction could be the following (depending on what the audience already knows):

  • Defining the addition, multiplication (or even exponentiation) of ordinal numbers by transfinite recursion and then showing some of their basic properties. (Probably most of the claims for addition and multiplication can be proved easier in a non-inductive way.)

  • $a.a=a$ holds for every cardinal $a\ge\aleph_0$. E.g. Cieselski: Set theory for the working mathematician, Theorem 5.2.4, p.69. Using the result that any two cardinals are comparable, this implies $a.b=a+b=\max\{a,b\}$. See e.g. here

  • The proof that Axiom of Choice implies Zorn's lemma. (This implication is undestood as a theorem in ZF - in all other bullets we work in ZFC.)

  • Proof of Steinitz theorem - every field has an algebraically closed extension. E.g. Antoine Chambert-Loir: A field guide to algebra, Theorem 2.3.3, proof is given on p.39-p.40.

  • Some constructions of interesting subsets of plane are given in Cieselski's book, e.g. Theorem 6.1.1 in which a set $A\subseteq\mathbb R\times\mathbb R$ is constructed such that $A_x=\{y\in\mathbb R; (x,y)\in A\}$ is singleton for each $x$ and $A^y=\{x\in\mathbb R; (x,y)\in A\}$ is dense in $\mathbb R$ for every $y$.

share|improve this answer
    
Assume the axiom of countable choice, then $A$ is infinite implies $|A|\ge\aleph_0$. Since your second exercise means that $|A|=|A\times A|$ we can deduce the full axiom of choice. However we already know that this is very far from being true. –  Asaf Karagila Nov 8 '11 at 12:40
    
@Asaf: I meant to work in ZFC there. Perhaps I should have written something like if you have already shown instead of if we know. –  Martin Sleziak Nov 8 '11 at 12:43
    
Ah, it seemed as though you derive that from the assumption $|A|\ge\aleph_0\rightarrow |A|=|A\times A|$. :-) –  Asaf Karagila Nov 8 '11 at 12:55

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.