1
$\begingroup$

Here $\alpha$ and $\beta$ are ordinals. I need to prove that if $\alpha+\beta=\beta$, then $\alpha\le \beta$.

My textbook just gives that that if $\alpha\le \beta$, then exists ordinal $\gamma$ such that $\alpha+\gamma=\beta$.

I am completely new to transfinite arithmetic, could someone please give a proof? Thanks in advance!

$\endgroup$

closed as off-topic by Andrés E. Caicedo, C. Falcon, Daniel W. Farlow, Claude Leibovici, user223391 Apr 24 '17 at 4:03

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "This question is missing context or other details: Please improve the question by providing additional context, which ideally includes your thoughts on the problem and any attempts you have made to solve it. This information helps others identify where you have difficulties and helps them write answers appropriate to your experience level." – Andrés E. Caicedo, C. Falcon, Daniel W. Farlow, Claude Leibovici, Community
If this question can be reworded to fit the rules in the help center, please edit the question.

  • $\begingroup$ Isn't $\alpha$ order-isomorphic to an initial segment of $ \alpha+\beta$, so that $\alpha\le\alpha+\beta$? $\endgroup$ – Lord Shark the Unknown Apr 22 '17 at 18:48
  • $\begingroup$ @LordSharktheUnknown It makes sense to me. But could you please expand a little bit, say, how to formally prove that they are order isomorphic and how can I thus deduce that $α≤α+β$? $\endgroup$ – non-abelian group of order 9 Apr 22 '17 at 18:56
2
$\begingroup$

Let $E$ and $F$ be ordered sets, and let $E\oplus f$ be the ordered set on the disjoint union $E\times\{0\}\cup F\times\{1\}$ where the order is taken to coincide with that of $E$ on $E$, that of $F$ on $F$, and where any element of $E$ is smaller than any element of $F$.

When $E$ and $F$ are well ordered, you can prove that $E\oplus F$ is as well (consider a non empty subset, and then discuss whether it intersects $E$ or not).

So if $\alpha$ and $\beta$ are ordinals, $\alpha\oplus\beta$ is order isomorphic with a unique ordinal. Now what I will prove is that $\alpha\oplus \beta \simeq \alpha + \beta$, and that the (unique) order isomorphism sends any element of $\alpha$ to itself. Once we have this, since $\alpha$ is obviously an initial segment of $\alpha\oplus\beta$, $\alpha$ will be an initial segment of $\alpha+\beta$, and thus $\alpha\leq \alpha+\beta$, and in your case since $\alpha+\beta =\beta$, this will give $\alpha\leq \beta$, as wanted.

To prove the claim $\alpha\oplus\beta\simeq \alpha+\beta$ we proceed by induction on $\beta$, fixing $\alpha$, on the following property : "there is an order isomorphism from $\alpha\oplus\beta$ to $\alpha+\beta$".

The property obviously holds for $\beta =0$, and the definition of addition makes the induction step $\beta\to \beta+1$ immediate.

Now for the limit case, we can argue as follows : let $\beta$ be a limit ordinal and assume the property holds for $\gamma<\beta$. Notice that for $\gamma<\beta$, $\alpha\oplus\gamma \subset \alpha\oplus\beta$, and in fact the LHS is an initial segment of the RHS. Fix for $\gamma<\beta$ an isomorphism $f_\gamma : \alpha\oplus \gamma \to \alpha+\gamma$ (this doesn't use the axiom of choice since order isomorphisms between well ordered sets are unique).

Whenever $\gamma\leq\delta<\beta$, the restriction of $f_\delta$ to $\alpha\oplus\gamma$ is an order preserving bijection with an initial segment of an ordinal, so an ordinal, so it is the unique ordinal with which $\alpha\oplus\gamma$ is isomorphic, i.e. $\alpha+\gamma$ by the induction hypothesis. Therefore, by unicity, the restriction of $f_\delta$ to $\alpha\oplus\gamma$ is $ f_\gamma$.

Therefore $f:=\displaystyle\bigcup_{\gamma<\beta}f_\gamma$ is a function, whose domain is $\alpha\oplus\beta$ (why ?) and whose range is included in $\displaystyle\bigcup_{\gamma<\beta}\alpha+\gamma = \alpha +\beta$.

Moreover $f$ is obviously order preserving and injective. Now if you let $\kappa\in \alpha+\beta$, there exists $\gamma<\beta$ such that $\kappa\in \alpha+\gamma$, because $\beta$ is a limit ordinal and by definition of the ordinal sum, and so $\kappa\in range(f_\gamma)\subset range(f)$, and so $f: \alpha\oplus\beta \to \alpha +\beta$ is an order preserving bijection, an isomorphism.

This completes the induction proof. Notice that it would be easy to prove at the same time that this isomorphism fixes $\alpha$, which proves my claim.

EDIT : I'm adding a precision on a point, as asked in the comments. Let $\delta$ and $\gamma$ be two ordinals, such that $\delta$ is an initial segment of $\gamma$. If $\delta$ is not a proper initial segment, then $\delta=\gamma$ and so $\delta\leq \gamma$. For the case where $\delta$ is a proper initial segment, I'll have to prove a general claim : Let $E$ be a well-ordered set, and $F$ a proper initial segment. Then there exists $x\in E$ such that $F= S_x := \{y\in E, y<x\}$. For this you can consider $x:= min\{z\in E, \forall y\in F, y<z\}$. This set is nonempty since $F$ is an initial segment and is not equal to $E$, and so $x$ is well-defined. You can easily see that then $F=S_x$.

So in our case, there is $\kappa\in \gamma$ such that $\delta = S_\kappa = \{y\in \gamma\mid y<\kappa\}$. Then you have to remember two things : on ordinals, $<$ is the same thing as $\in$, and $\kappa\subset\gamma$, by transitivity. Therefore $\delta = S_\kappa = \{y\in \gamma\mid y\in \kappa\} = \gamma\cap\kappa = \kappa$. And so, since $\kappa\in \gamma$, $\delta\in \gamma$, and so $\delta<\gamma$

$\endgroup$
  • $\begingroup$ It is much clearer! May I please ask how does $\alpha$ is a initial segment of $\alpha+\beta$ implies $\alpha\le \alpha+\beta$? $\endgroup$ – non-abelian group of order 9 Apr 23 '17 at 1:23
  • $\begingroup$ I've added a precision in my answer, you can look at it $\endgroup$ – Max Apr 23 '17 at 8:26

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