I know this is a newbie question, so please bare with me :)

I'd like to prove within ZF axiomatic set theory that the addition of two ordinals is not commutative. In particular, I'd like to prove this counter example:

$\omega + 1 \neq 1 + \omega$

I have the following definition for addition on ordinal numbers (defined from transfinite induction):

(i) $\alpha + 0 = \alpha$

(ii) $\alpha + \beta' = (\alpha + \beta)'$

(iii) if $\beta$ is a limit ordinal then $\alpha + \beta = \bigcup_{\gamma \in \beta}(\alpha + \gamma)$

So my attempt was to start from the right side, which, intuitively would be something like this:

$1 + \omega = \bigcup_{\gamma \in \omega}(1 + \gamma) = \{2, 3, 4, ..\}$

My attempt at the left side started like this:

$\omega + 1 = (\omega + 0)' = \omega'$

And then I'm stuck. I'd like to think that the successor of $\omega$ is $\omega$ but with this definition how can I prove that? Also, if that's the case then there's a $1-1$ function that can map $\{1, 2, 3, ...\}$ to $\{2, 3, 4, ...\}$ and still preserve order, so shouldn't both sides of the addition be the same?

• Show that $\omega+1$ has an element without an immediate predecessor, while $1+\omega$ doesn't. – Mariano Suárez-Álvarez Nov 19 '12 at 17:03
• Or just a maximum. – Michael Greinecker Nov 19 '12 at 17:03
• Yeah, that too :-) – Mariano Suárez-Álvarez Nov 19 '12 at 17:04

Recall the definition $\alpha+\beta=\sup\{\alpha+\gamma\mid\gamma<\beta\}$ when $\beta$ is a limit ordinal.
That means that $1+\omega=\sup\{1+n\mid n<\omega\}=\sup\{n\mid n<\omega\}=\omega$.
On the other hand, $\omega+1=(\omega+0)'=\omega+1\neq\omega$ because $\alpha\neq\alpha'$ for all $\alpha$. This is because $\alpha\in\alpha'$ therefore these sets are distinct. Therefore the ordinals are not order isomorphic either (because every well-ordered set is isomorphic to a unique ordinal).
• Wait, are you saying that I can't find a 1-1 function from $\langle \{2, 3, 4, ...\}, \in \rangle$ to $\langle N, \in \rangle$ with preserved order? How about $f(x) = x + 1$ ? What am I missing? – Nicolas Nov 19 '12 at 17:34
• @Nicolas: I am saying that $\{2,3,4,\ldots\}$ is not an ordinal. In contrast $\omega\cup\{\omega\}$ is an ordinal. – Asaf Karagila Nov 19 '12 at 17:41
• Thanks for your answer. I think I messed up the union definition. What this really means is that $1 + \omega = \cup_{(\gamma \in \omega)}(1 + \gamma) = (1 + 0) \cup (1 + 1) \cup (1 + 2) \cup ... = 1 \cup 2 \cup 3, ... = \{0\} \cup \{0, 1\} \cup \{0, 1, 2\} \cup ... = \omega$. So the real question is, $\omega \neq \omega \cup \{\omega\}$, how can I prove that? – Nicolas Nov 19 '12 at 18:00
• @Nicolas: But that much is obvious. $\omega\notin\omega$ but $\omega\in\omega'$. – Asaf Karagila Nov 19 '12 at 18:00