4
$\begingroup$

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

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

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

$\endgroup$
4
  • $\begingroup$ $\omega$ is the smallest limit ordinal $\endgroup$ Feb 28, 2016 at 9:18
  • $\begingroup$ $\oplus$ is ordinal addition, right? $\endgroup$
    – Wojowu
    Feb 28, 2016 at 9:18
  • $\begingroup$ Yes $\oplus$ is ordinal addition and "+" is just to denote successors. $\endgroup$ Feb 28, 2016 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$ Feb 28, 2016 at 9:21

2 Answers 2

2
$\begingroup$

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.

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

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.

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