4
$\begingroup$

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?

  • 4
    Show that $\omega+1$ has an element without an immediate predecessor, while $1+\omega$ doesn't.2012-11-19
  • 1
    Or just a maximum.2012-11-19
  • 0
    Yeah, that too :-)2012-11-19

1 Answers 1

4

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

  • 0
    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?2012-11-19
  • 3
    @Nicolas: I am saying that $\{2,3,4,\ldots\}$ is **not** an ordinal. In contrast $\omega\cup\{\omega\}$ **is** an ordinal.2012-11-19
  • 0
    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?2012-11-19
  • 0
    @Nicolas: But that much is obvious. $\omega\notin\omega$ but $\omega\in\omega'$.2012-11-19
  • 0
    Oh yes, I finally understood it, thanks for your help!2012-11-19