Is this formula for the minimal sum correct?
As is well known, the addition of natural numbers can be extended to the ordinal numbers in different ways. The first way is the ordinal sum, and the second is the natural or Hessenberg sum.
Now I've been thinking about other possible sums of ordinals. For that purpose I've used the following general definition:
Given two ordinals $\alpha$ and $\beta$, an ordinal $\gamma$ is a sum of $\alpha$ and $\beta$ if there exists a partition of $\gamma$ into two subsets $A$ and $B$ such that $A$ is order-isomorphic to $\alpha$ and $B$ is order-isomorphic to $\beta$
Obviously the ordinal sum $\alpha+\beta$ is the special case where you can choose $A$ and $B$ so that all elements of $A$ are smaller than all elements of $B$. Also, if I'm not mistaken, the natural sum is simply the largest sum, that is, $$\alpha\oplus\beta = \max_{\text{$\gamma$ is a sum of $\alpha$ and $\beta$}} \gamma$$
Now given this, there is an obvious other candidate for a specific sum: $$\alpha\boxplus\beta = \min_{\text{$\gamma$ is a sum of $\alpha$ and $\beta$}} \gamma$$ This minimal sum obviously exists because the ordinals are well-ordered, and moreover from the definition is it immediately obvious that the minimal sum is commutative.
Now the obvious next thing one wants is an explicit expression for the minimal sum. Now I think if we write $\alpha = \lambda + m$ and $\beta = \mu + n$ where $\lambda$ and $\mu$ are limit ordinals or zero, and $m$ and $n$ are finite ordinals, then we have $$\alpha \boxplus \beta = \begin{cases} \beta & \text{if } \alpha < \mu\\ \alpha & \text{if } \beta < \lambda\\ \alpha +n & \text{otherwise} \end{cases}$$ Or said differently, if the ordinals are infinitely far apart, the minimal sum is just the larger of them, otherwise the finite parts add up.
If this should indeed be the case, then obviously the minimal addition would also be associative, and moreover, if we restrict it to the initial ordinals, it would reduce to cardinal addition, so it would actually be a generalisation of cardinal addition to arbitrary ordinals.
Therefore my question is:
Is the formula above correct, and if so, how can I prove it?
Also, if the formula is not correct, what would be a counterexample, and can you tell me the correct formula?
1 answer
I think I've solved the problem: The formula is correct.
For the proof I'm using the decomposition $\alpha = \lambda + m$ and $\beta = \mu + n$ from the question. Also, I'll use the notation $A\cong B$ for “$A$ is order-equivalent to $B$”. Also note that $+$ and $\cdot$ denote the standard ordinal addition and multiplication.
Since the minimal sum is commutative by definition, it suffices to consider the case $\alpha\le\beta$. In that case, there exists an unique $\delta$ such that $\alpha+\delta = \beta$.
Now the first observation is that in this case, the right hand side of the explicit formula can be written as $2\cdot\alpha + \delta$. This can be seen by the fact that $2\cdot\alpha = \lambda + 2m$, and therefore for finite $\delta$ we have $m+\delta = n$ and therefore $2\cdot\alpha+\delta = \alpha + n$, while for infinite $\delta$ we have $m + \delta = \delta$ and therefore $2\cdot\alpha+\delta = \alpha + \delta = \beta$.
Next, we can see that $2\cdot\alpha+\delta$ is a sum of $\alpha$ and $\beta$, since by the definitions of the ordinal operations, we have the partition $2\cdot\alpha+\delta = 2\cdot\alpha\cup D$ where $D\cong\delta$, and $2\cdot\alpha\cong \alpha\times\{0,1\}$ under lexicographical order, giving rise to the partition $P=A\cup A'$ where $A\cong A'\cong\alpha$. Then $B=A'\cup D\cong\beta$, thus $A$ and $B$ are a partition of the form required by the definition of a sum. Therefore we have for the minimal sum $\alpha\boxplus\beta \le 2\cdot\alpha + \delta$.
What remains to prove is that $\alpha\boxplus\delta\ge 2\cdot\alpha + \delta$. Now for infinite $\delta$, this is obvious, as there the right hand side is just $\beta$, and $\alpha\boxplus\beta\ge\beta$ by construction. For finite $\delta$, we know that the finite part of $\alpha$ and the finite part of $\beta$ must both necessarily be mapped to the finite part of $\alpha\boxplus\beta$, as otherwise we'd have a strictly increasing mapping from a larger to a smaller ordinal. Thus in this case the finite part of the minimal sum has to be a sum of the finite parts. But for finite numbers, the sum is unique, which concludes the proof.
0 comment threads
0 comment threads