I was given the following definition of Hessenberg sum:
Definition. Given $\alpha,\beta \in \text{Ord}$ their Hessenberg sum $\alpha \oplus \beta$ is defined as the least ordinal greater than all Hessenberg sums of the form $\alpha' \oplus \beta'$, for $\alpha ' \leq \alpha$, $\beta' \leq \beta$ and $(\alpha',\beta') \ne (\alpha,\beta)$.
Reading online I understood (I hope) that this is equivalent to making the sum between $\alpha$ and $\beta$ component-wise in Cantor Normal Form. Does anyone have a simple proof of this fact?
A simple proof? As someone who loves ordinals and whose research has involved them extensively, particularly the Hessenberg sum, I've found that proofs about them are not difficult, but typically involve lots of tedious bookkeeping.
For a bounded set $\mathcal{U}$ of ordinals, $$\sup\{\xi+1:\xi\in\mathcal{U}\}$$ is the smallest ordinal which is greater than every member of $\mathcal{U}$. Here, $\sup \varnothing=0$.
For ordinals $\alpha,\beta$, let $$L(\alpha,\beta)=\{(\gamma,\delta):\gamma\leqslant \alpha,\delta\leqslant \beta,(\gamma,\delta)\neq (\alpha,\beta)\}.$$
Let $\boxplus$ denote the Hessenberg sum. That is, if $\alpha,\beta$ are ordinals and $p,m_1,\ldots,m_p,n_1,\ldots,n_p$ are finite ordinals and $\varepsilon_1>\ldots>\varepsilon_p$ are ordinals such that $$\alpha=\omega^{\varepsilon_1}m_1+\ldots+\omega^{\varepsilon_p}m_p$$ and $$\beta=\omega^{\varepsilon_1}n_1+\ldots+\omega^{\varepsilon_p}n_p,$$ then $$\alpha\boxplus\beta=\omega^{\varepsilon_1}(m_1+n_1)+\ldots+\omega^{\varepsilon_p}(m_p+n_p).$$ We note that such representations exist for any pair of ordinals $\alpha,\beta$ (which uses Cantor normal form possibly "filled out" with zeros), and the value of $\alpha\boxplus \beta$ is well-defined, because different representations differ only in zero terms.
Definitionally, we have that $$\alpha\oplus\beta=\sup\{\gamma\oplus\delta + 1:(\gamma,\delta)\in L(\alpha,\beta)\},$$ so we need to show that $$\alpha\boxplus\beta=\sup\{\gamma\boxplus\delta+1:(\gamma,\delta)\in L(\alpha,\beta)\}.\tag{$\star$}$$
We prove this by double induction. That is, we prove by induction on $\alpha$ that for every $\beta$, $(\star)$ holds. That will be our "outer" induction hypothesis. For a fixed $\alpha$, we prove by induction on $\beta$ that $(\star)$ holds, which will be our "inner" induction hypothesis. So for a given $\alpha,\beta$, we will prove that $$\alpha\boxplus\beta=\sup\{\gamma\boxplus\delta+1:(\gamma,\delta)\in L(\alpha,\beta)\}$$ under the assumption that $$\xi\boxplus\zeta=\sup\{\gamma\boxplus\delta+1:(\gamma,\delta)\in L(\xi,\zeta)\}$$ whenever either $\xi<\alpha$ or $\xi=\alpha$ and $\zeta<\beta$.
Let's first take care of the case that $\alpha=0$. We have $$0\boxplus 0 = 0=\sup\varnothing=\sup\{\gamma\boxplus\delta+1:(\gamma,\delta)\in \varnothing\}=\sup\{\gamma\boxplus\delta+1:(\gamma,\delta)\in L(0,0)\}.$$ For $\beta>0$, $$0\boxplus \beta = \beta=\sup\{\delta+1:\delta<\beta\}=\sup\{0\boxplus\delta+1:(0,\delta)\in L(0,\beta)\}.$$ This gives us the $\alpha=0$ case. By a symmetric argument, we have that for $\alpha>0$, $$\alpha\boxplus 0 = \alpha=\sup\{\gamma+1:\gamma<\alpha\}=\sup\{\gamma\boxplus 0+1:(\gamma,0)\in L(\alpha,0)\}.$$ This gives us the $\beta=0$ case for a fixed $\alpha>0$.
In the remainder, we have reduced to the case $\alpha,\beta>0$. First, note that by the inductive hypothesis, if $\gamma<\alpha$ and $\delta<\beta$, then $$\gamma\boxplus \delta<\alpha\boxplus\delta$$ and $$\gamma\boxplus\delta<\gamma\boxplus\beta.$$ Therefore $$\sup\{\gamma\boxplus\delta+1:(\gamma,\delta)\in L(\alpha,\beta)\}=\max\bigl\{\sup\{\alpha\boxplus \delta + 1:\delta<\beta\},\sup\{\gamma\boxplus\beta +1:\gamma<\alpha\}\bigr\}.\tag{$\star\star$}$$ That is, to get the supremum over $(\gamma,\delta)\in L(\alpha,\beta)$, it suffices to back off only in one direction at a time. Here we are using the fact that the functions $\gamma\mapsto \gamma\boxplus\beta$ and $\delta\mapsto \alpha\boxplus \delta$ are strictly increasing on $[0,\alpha)$ and $[0,\beta)$, respectively, which also follows from the inductive hypothesis. The fact that these functions are strictly increase means that it is sufficient to consider limits rather than suprema. We also note the symmetry of the expressions in $(\star\star)$. So it suffices to look at only one of the two expressions inside the $\max$ in $(\star\star)$.
Let's reset: $\alpha,\beta>0$, $\gamma\mapsto \gamma\boxplus\beta$ and $\delta\mapsto\alpha\boxplus \delta$ are strictly increasing on $[0,\alpha)$ and $[0,\beta)$, respectively.
Let $\delta$ be the smallest exponent in the Cantor normal form of $\alpha$ and let $\varepsilon$ be the smallest exponent in the Cantor normal form of $\beta$ (we won't use this for a while, but don't forget the definition of $\varepsilon$). Let's write $\beta=\rho+\omega^\delta n+\tau$, where $\rho$ is the sum of the terms in the Cantor normal form of $\beta$ with exponents greater than $\delta$, $\omega^\delta n$ is the term in the Cantor normal form of $\beta$ with exponent $\delta$ if there is one, and otherwise we just take $n=0$, and $\tau$ is the sum of the terms in the Cantor normal form of $\beta$ with exponents smaller than $\delta$. So $\beta=\rho+\omega^\delta n+\tau$. Note that any of $\rho,\omega^\delta n,\tau$ could be zero (and in fact any two of them could be zero).
Since $\delta$ is the smallest exponent in the Cantor normal form of $\alpha$, we can write $\alpha=\xi+\omega^\delta m$ for some positive integer $m$, where $\xi$ is either zero or has all of the exponents in its Cantor normal form greater than $\delta$.
If $\delta=0$ (which happens iff $\alpha$ is a successor, in which case $\alpha=\xi+m$), since $\gamma\mapsto \gamma\boxplus\beta$ is strictly increasing on $[0,\alpha)$, $$\sup_{\gamma<\alpha}\gamma\boxplus\beta+1 = (\xi+m-1)\boxplus \beta +1=(\xi+m-1+1)\boxplus\beta=\alpha\boxplus\beta,$$ which is what we wanted. If $\delta>0$, then $\omega^\delta$ and $\alpha$ are both limits ordinals. Since $\gamma\mapsto \gamma\boxplus\beta$ is strictly increasing on $[0,\alpha)$, $$\sup_{\gamma<\alpha}\gamma\boxplus\beta +1 = \lim_{\gamma\uparrow \alpha} \gamma\boxplus \beta+1=\lim_{\mu\uparrow \omega^\delta} (\xi+\omega^\delta(m-1)+\mu)\boxplus \beta + 1.$$ Note that for any $\mu<\omega^\delta$, we have that \begin{align*} (\xi+\omega^\delta(m-1)+\mu)\boxplus \beta & =(\xi+\omega^\delta(m-1)+\mu)\boxplus (\rho+\omega^\delta n+\tau) \\ & = (\xi\boxplus \rho)+\omega^\delta(m+n-1)+(\mu\boxplus\tau +1) \\ & = (\xi\boxplus \rho)+\omega^\delta(m+n-1)+(\mu\boxplus(\tau +1)).\end{align*}
Maybe a bit more detail should be shown here, but we're just splitting the terms in the $\boxplus$ into the parts with exponents greater than, equal to, and less than $\delta$, respectively. As we take the limit $\mu\uparrow \omega^\delta$, only the last of the summands is changing. Since the largest exponent in $\tau+1$ is less than $\delta$, $\mu\boxplus(\tau+1)\uparrow \omega^\delta$ as $\mu\uparrow \omega^\delta$. Therefore we get $$\sup_{\gamma<\alpha}\gamma\boxplus\beta = (\xi+\rho)+\omega^\delta(m+n-1)+\omega^\delta = (\xi+\rho)\omega^\delta(m+n).$$
Note that $$\alpha\boxplus\beta =(\xi+\omega^\delta m)\boxplus(\rho+\omega^\delta n+\tau)=(\xi\boxplus \rho)+\omega^\delta(m+n)+\tau,$$ so the supremum in the preceding paragraph is equal to $\alpha\boxplus\beta$ if and only if $\tau=0$, which happens if and only if every exponent in the Cantor normal form of $\beta$ is at least as large as $\delta$ (which happens iff $\varepsilon\geqslant \delta$). In other words, $$\sup_{\gamma<\alpha}\gamma\boxplus\beta +1 \leqslant \alpha\boxplus\beta,$$ with equality if and only if $\varepsilon\geqslant \delta$. Note that we did not say it this way in the $\delta=0$ case, but in the $\delta=0$ case, $\varepsilon\geqslant 0=\delta$ definitely holds, and we did have equality, so this statement is true in both $\delta=0$ and $\delta>0$ cases.
By symmetry, $$\alpha\boxplus\beta\geqslant \sup_{\delta<\beta}\alpha\boxplus\delta,$$ with equality iff $\varepsilon\leqslant \delta$. Since either $\varepsilon\geqslant \delta$ or $\varepsilon\leqslant \delta$, equality must hold for at least one of the suprema.