I'm struggling to rigorously prove $\omega \ \oplus 2 \neq 2\ \oplus \omega$ in context of NBG set theory.

I haven't really seen a full proof anywhere besides the basic structure. Please direct me to one if I missed it.


Starting on LHS: $\omega \ \oplus 2 = \omega \ \oplus (1+1) = \omega \ \oplus ((0+1) +1) = ((\omega \ \oplus \ 0)+1)+1$, since $2$ is the successor of $1$ and $1$ is the successor of $0$.

From the definition of "$\oplus$" we have, $\omega \ \oplus \ 0 = \omega$.

It follows $\omega \ \oplus 2 = (\omega+1)+1 = \omega + 2$ (the 2nd successor ordinal to $\omega$)

The crux now lies in showing $2 \oplus \omega = \omega $.

From the definition of "$\oplus$" we know:

$2\ \oplus \ \omega = \bigcup_{\gamma <\omega} 2\oplus\gamma$

A previous theorem stated: "If $x$ is a set of ordinals then $\bigcup x$ is also an ordinal and is the least upper bound of the set $x$."

Clearly the following is a set of ordinals: $x= \{\beta: \beta = 2\oplus\gamma \ \forall\gamma < \omega\}$

So it remains to show$\ $ $\bigcup_{\gamma <\omega} 2\oplus\gamma = \sup\{\beta: \beta = 2\oplus\gamma \ \forall\gamma < \omega\} = \omega$.

This is where things go awry. Next I said we first need to show $\omega$ is indeed an upper bound for the set.

So $2 \oplus \gamma \leq \omega\ \forall \gamma < \omega$ needs to hold true. Assume for contradiction: $\exists \beta < \omega$ s.t. $2\oplus\beta > \omega$

This is a clear contradiction if $\beta = 0$. I keep running in circles for the case where $\beta$ is a successor ordinal. Since we assumed $\beta < \omega$ we can't have $\beta$ being a limit ordinal itself ?

$\textbf{Update I:}$

We can assume $\beta = \alpha +1 $ for some $\alpha \in \textit{On}$

So $2 \oplus (\alpha +1) > \omega $

If we can show $2\oplus \alpha < \omega$ $...(1)$

This would provide the contradiction.

$\textbf{Update II:}$

To prove this I'll use Henning's hint, but with normal induction:

$\alpha$ is a successor so we can say $\alpha, 2 \in (<)\ \omega$

If $\alpha = 0$ then $2\oplus \alpha <\omega$ is trivial.

if $\alpha = \eta +1$ for some $\eta \in \textit{On}$

We can assume $\alpha \oplus \eta < \omega$ $\}$ (!!) this is the part of transfinite induction I am unsure about. Is this allowed ? Just like in normal induction?

Then $2\oplus (\eta +1) =(2\oplus \eta)+1 $

We know then $(2\oplus \eta)+1 < \omega$ since $2\oplus \eta < \omega$ ($2\oplus \eta$ is a successor ordinal)

We have established $\alpha$ is not a limit ordinal so this proves $(1)$.


It still remains to show that $\omega$ is indeed the $\textit{least}$ upper bound which makes this long proof even longer, so I wouldn't recommend this approach.

  • $\begingroup$ $\omega$ is the smallest limit ordinal $\endgroup$ – Hagen von Eitzen Feb 28 '16 at 9:18
  • $\begingroup$ $\oplus$ is ordinal addition, right? $\endgroup$ – Wojowu Feb 28 '16 at 9:18
  • $\begingroup$ Yes $\oplus$ is ordinal addition and "+" is just to denote successors. $\endgroup$ – Walt van Amstel Feb 28 '16 at 9:19
  • $\begingroup$ It makes sense that $\beta < \omega$ means $\beta$ can't be limit but I haven't proven that $\omega$ is the smallest yet. $\endgroup$ – Walt van Amstel Feb 28 '16 at 9:21

You can prove that if $\delta,\gamma\in\omega$ then $\delta\oplus\gamma\in\omega$, by induction on $\gamma$:

Assume to the contrary that there is at least one $\beta<\omega$ such that $\delta\oplus\beta\notin\omega$. Then there is a least such $\beta$, and since by definition there is no limit ordinals in $\omega$, we must have $\beta=\alpha+1$ where $\delta\oplus\alpha\in\omega$. A contradiction now follows.

  • $\begingroup$ I'm not entirely sure which part of my attempt you are referring to ? $\endgroup$ – Walt van Amstel Feb 28 '16 at 10:31
  • $\begingroup$ @rt6: The one where you say "If we can show $2\oplus \alpha<\omega$ ...". That is your induction hypothesis, not something you need to show separately. $\endgroup$ – hmakholm left over Monica Feb 28 '16 at 10:33
  • $\begingroup$ Is the above edit to my question valid use of transfinite induction ? Thank you for the help, Henning. $\endgroup$ – Walt van Amstel Feb 28 '16 at 10:59

Assume $2 \oplus \beta >\omega$ is true for some $\beta \in \omega$

We know that $2 \in \omega$ and as Henning said then $2 \oplus \beta \in \omega$.

We know that $\omega \in On$ so $\omega$ is full. Thus it holds that $2 \oplus \beta \subseteq \omega$, but from assumption $\omega \in 2 \oplus \beta$, so $\omega \in \omega$ -(1).

Now $\omega \in On$ and it's true that $\text{Ord}(On)$ so $\in$ is irreflexive in $On$, but (1) contradicts this. We then have the contradiction that you need.

  • $\begingroup$ What do you mean by "$\omega$ is full"? And what does $\operatorname{Ord}(\operatorname{On})$ mean? $\endgroup$ – Stefan Mesken Feb 28 '16 at 13:46
  • $\begingroup$ Fullness is the property if $a \in b$ then $a \subseteq b$ $\endgroup$ – Walt van Amstel Feb 28 '16 at 13:48
  • $\begingroup$ Ord$(\textit{On})$ is just short hand for $\textit{On}$ being an ordinal class. $\endgroup$ – Walt van Amstel Feb 28 '16 at 13:50
  • $\begingroup$ What the Op said. Do you disagree with my answer @Stefan? $\endgroup$ – K.Power Feb 28 '16 at 14:00
  • $\begingroup$ I've never encountered this terminology, but that's besides the point. Your proof can be shortened: If $2 \oplus \beta > \omega$ and $2 \oplus \beta < \omega$, then $2 \oplus \omega \in \omega \in 2 \oplus \beta$, contradicting regularity. $\endgroup$ – Stefan Mesken Feb 28 '16 at 14:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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