TITLE: Explicit formulas for natural (Hessenberg) and ordinal sum: Do those work?
QUESTION [2 upvotes]: As is known, ordinal numbers have a natural mapping into the surreal numbers of the form
$$f(\alpha) = \{f(\beta):\beta\in\alpha\mid\}$$
Moreover, surreal addition of those numbers corresponds to the natural (Hessenberg) addition of ordinal numbers.
Now the sum of surreal numbers has an explicit recursive formula, while I haven't seen such a formula for the natural sum. Therefore I got the idea to simply translate the surreal number formula back to set theory.
The most direct translation would be
$$\alpha\oplus \beta = \{x\oplus\beta:x\in\alpha\}\cup\{\alpha\oplus x:x\in\beta\}$$
but that is easily checked not to work, as we would get e.g. $1\oplus 1 = \{1\} \ne \{0,1\}=2$. The reason of course is that in the surreal numbers we have the equivalence relations where we can freely add numbers to the left set as long as there's a larger number already in that set.
An easy solution would be to add that “filling up downwards” explicitly to the definition, but that would somewhat defeat the goal of having an explicit formula. Therefore I thought about filling the hole with the operands themselves.
That is, my guess at the explicit formula is:
$$\alpha\oplus\beta = \alpha\cup\beta\cup\{x\oplus\beta:x\in\alpha\}\cup\{\alpha\oplus x:x\in\beta\}$$
However I failed to even prove that this is associative, let alone that it indeed in all cases gives an ordinal again.
Seeing that the most obvious difference between natural and ordinal sum is the non-commutativity of the latter, I also guessed at a formula for the ordinal sum by simply de-symmetrizing the formula:
$$\alpha + \beta = \alpha \cup \{\alpha + x:x\in\beta\}$$
Here I think I at least can prove associativity, which together with the easy to prove fact $\alpha+1=\alpha\cup\{\alpha\}$ means that if it eventually breaks, it does so at a limit ordinal for $\beta$.
My question now is: Do those formulas indeed reproduce natural and ordinal addition of ordinals, and if not, where do they break down?

REPLY [2 votes]: Consider the Cantor normal forms (in descending order) of two ordinals $\alpha= \omega^{\eta_1} m_1+...+\omega^{\eta_r} m_r$ and $\beta=\omega^{\eta_1} n_1 +...+\omega^{\eta_r} n_r$, where some $n_i,m_i$ may be zero. I assume you know how the normal form of $\alpha\oplus\beta$ is obtained from those two.
I claim that your formula is valid. What you want to prove is that any ordinal $\mu$ strictly below $\alpha \oplus \beta$ is of the form $\mu \in \alpha \cup \beta$ or $\mu= \alpha\oplus\gamma$ for some $\gamma \in \beta$ or $\mu = \delta \oplus \beta$ for some $\delta \in \alpha$.
Now considering the normal form of $\mu$, you can parse through these different cases by focusing on the largest exponent with non zero coefficient and seeing whether it appears in the normal form of $\alpha$ or $\beta$. I can give more details if needed.
{"set_name": "stack_exchange", "score": 2, "question_id": 3715343}