# $\omega \ \oplus 2 \neq 2\ \oplus \omega$ in NBG set theory

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.

$\textbf{Attempt:}$

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

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

$\textbf{Retrospect:}$

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.

• $\omega$ is the smallest limit ordinal Feb 28, 2016 at 9:18
• $\oplus$ is ordinal addition, right? Feb 28, 2016 at 9:18
• Yes $\oplus$ is ordinal addition and "+" is just to denote successors. Feb 28, 2016 at 9:19
• It makes sense that $\beta < \omega$ means $\beta$ can't be limit but I haven't proven that $\omega$ is the smallest yet. Feb 28, 2016 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.

• I'm not entirely sure which part of my attempt you are referring to ? Feb 28, 2016 at 10:31
• @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. Feb 28, 2016 at 10:33
• Is the above edit to my question valid use of transfinite induction ? Thank you for the help, Henning. Feb 28, 2016 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.

• What do you mean by "$\omega$ is full"? And what does $\operatorname{Ord}(\operatorname{On})$ mean? Feb 28, 2016 at 13:46
• Fullness is the property if $a \in b$ then $a \subseteq b$ Feb 28, 2016 at 13:48
• Ord$(\textit{On})$ is just short hand for $\textit{On}$ being an ordinal class. Feb 28, 2016 at 13:50
• What the Op said. Do you disagree with my answer @Stefan? Feb 28, 2016 at 14:00
• 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. Feb 28, 2016 at 14:07