19
$\begingroup$

I'm looking at basic ordinal arithmetic at the moment, and I am aware that in general, $\alpha+\beta\neq\beta+\alpha$ and $\alpha.\beta\neq\beta.\alpha$ for ordinals $\alpha,\beta$.

My question is: are there any nice necessary and sufficient conditions on $\alpha,\beta$ for commutativity to hold?

For example, if they are of the form $\gamma.n$ and $\gamma.m$ ($n,m<\omega$) then addition will commute. Is this necessary?

$\endgroup$
  • 1
    $\begingroup$ The Cantor normal form may help you think about this in a more structured way. $\endgroup$ – Lord_Farin Apr 22 '13 at 17:30
10
$\begingroup$

We shall make use of the following facts:

  1. For any ordinals $\alpha<\beta$ we have $\omega^{\alpha}+\omega^{\beta}=\omega^{\beta}$
  2. If $\beta_n>\cdots>\beta_1>0,\alpha$ are ordinals and $l_i$ natural numbers, then $(\omega^{\beta_n}\cdot l_n+\cdots \omega^{\beta_1}\cdot l_1+l_0)\cdot \omega^{\alpha}=\omega^{\beta_n+\alpha}$; which is easy to prove by induction on $\alpha$ using $(1)$.

As Lord_Farin pointed out, to prove a necessary and sufficient condition you need only use the Cantor normal form, so you get the following condition:

$\alpha+\gamma=\gamma+\alpha$ iff there are ordinals $\beta_n >\ldots>\beta_1$ and nonzero natural numbers $l_0,\ldots,l_n,r_n$ such that $\alpha=\omega^{\beta_n}\cdot l_n+\cdots+\omega^{\beta_1}l_1+l_0$ and $\gamma=\omega^{\beta_n}\cdot r_n+\cdots+\omega^{\beta_1}l_1+l_0$

$(\Leftarrow)$ Using $(1)$ $n$ times we obtain $\alpha+\gamma=\omega^{\beta_n}\cdot (l_n+r_n)+\cdots+\omega^{\beta_1}l_1+l_0$ and $\gamma+\alpha=\omega^{\beta_n}\cdot (r_n+l_n)+\cdots+\omega^{\beta_1}l_1+l_0$, so that $\alpha+\gamma=\gamma+\alpha$.

$(\Rightarrow)$ Let $\omega^{\alpha_n}\cdot l_n+\cdots+\omega^{\alpha_1}\cdot l_1+l_0$ and $\omega^{\gamma_m}\cdot r_m+\cdots+\omega^{\gamma_1}\cdot r_1+r_0$ be the normal forms of $\alpha$ and $\gamma$ respectively. Put $\alpha'=\omega^{\alpha_{n-1}}\cdot l_{n-1}+\cdots+\omega^{\alpha_1}\cdot l_1+l_0$ and $\gamma'=\omega^{\gamma_{m-1}}\cdot r_{m-1}+\cdots+\omega^{\gamma_1}\cdot r_1+r_0$.

If $\alpha_m\neq \gamma_n$ we may assume WLOG that $\alpha_n<\gamma_m$, then if $k<n$ is such that $\alpha_k\leq \gamma_m$, then using $(1)$ $\gamma+\alpha=\alpha$ and $\alpha+\gamma=\omega^{\alpha_n}\cdot l_n+\cdots+\omega^{\alpha_k}\cdot l_k+\omega^{\gamma_m}\cdot r_m+\cdots+\omega^{\gamma_1}\cdot r_1+r_0$, thus by the uniqueness of the Cantor normal form we get that $\alpha+\gamma\neq \gamma+\alpha$; $r_m\neq 0$. Now if $\alpha'\neq \gamma'$ but $\alpha_m= \gamma_n$, then by $(1)$ $\alpha+\gamma=\omega^{\alpha_n}\cdot(l_n+r_n)+\gamma'$ and $\gamma+\alpha=\omega^{\alpha_n}\cdot(r_n+l_n)+\alpha'$, but by the uniqueness of the Cantor normal form this implies $\alpha+\gamma\neq \gamma+\alpha$.

Now we prove another result:

Let $\omega^{\alpha_n}\cdot l_n+\cdots+\omega^{\alpha_1}\cdot l_1+l_0$ and $\omega^{\gamma_m}\cdot r_m+\cdots+\omega^{\gamma_1}\cdot r_1+r_0$ be the normal forms of $\alpha$ and $\gamma$ respectively. Then $\alpha\cdot\gamma=\gamma\cdot\alpha$ iff $m=n$, $r_k=l_k,\alpha_n+\gamma_k=\gamma_n+\alpha_k$ for $1\leq k\leq n$ and $\alpha\cdot r_0=\gamma\cdot l_0$.

$(\Rightarrow)$ Using $(2)$ we have $$\alpha\cdot \gamma=\alpha\cdot\omega^{\gamma_m}\cdot r_m+\cdots+\alpha\cdot\omega^{\gamma_1}\cdot r_1+\alpha\cdot r_0$$$$=\omega^{\alpha_n+\gamma_m}\cdot r_m+\cdots+\omega^{\alpha_n+\gamma_1}\cdot r_1+\alpha\cdot r_0(3),$$ similarly $$\gamma\cdot\alpha=\omega^{\gamma_m+\alpha_n}\cdot l_n+\cdots+\omega^{\gamma_m+\alpha_1}\cdot l_1+\gamma\cdot l_0,(4)$$ then since for any ordinals $\alpha',\beta',\gamma'$ we have $(\beta'<\gamma')\longrightarrow (\alpha'+\beta'<\alpha'+\gamma')$ and $\alpha\cdot\gamma=\gamma\cdot\alpha$, it follows by the uniqueness of the Cantor normal form that $2m=2n$, i.e., $m=n$, and $\gamma_n+\alpha_k=\alpha_n+\gamma_k,r_k=l_k$ for all $k$ and $\alpha\cdot r_0=\gamma\cdot l_0$.

($\Leftarrow$) Easy using the identities $(3)$ and $(4)$.

$\endgroup$
  • $\begingroup$ In the proof about addition you have two $\alpha$'s. From from the existence, and one from the addition. Is it the same $\alpha$? $\endgroup$ – Asaf Karagila Apr 23 '13 at 13:23
  • $\begingroup$ Thank you, this is very comprehensive! $\endgroup$ – caesianrhino Apr 23 '13 at 16:22
  • $\begingroup$ @Isaac Henrion, you're welcome $\endgroup$ – Camilo Arosemena-Serrato Apr 23 '13 at 19:44
  • $\begingroup$ The second result is wrong. If $r_0,l_0>0$, note that the lengths of the Cantor normal forms are each $m+n$, not $2n$ and $2m$, so you do not get $m=n$. Note for instance that $\omega+1$ and $(\omega+1)^2=\omega^2+\omega+1$ commute but do not satisfy your criterion. $\endgroup$ – Eric Wofsey May 31 '19 at 2:27
  • $\begingroup$ It does work if $r_0=l_0=0$ (both ordinals are limits), though, because then the Cantor normal forms have length $m$ and $n$ and so $m=n$ and everything works. There is also an easy answer if $r_0>0$ and $l_0=0$ (one is successor and the other is limit), since then one Cantor normal form has length $m+n$ and the other has length $n$ so $m=0$ and so $\gamma$ is finite, and then it is easy to see that $\alpha$ and $\gamma$ cannot commute unless $\gamma=1$ or $\alpha=0$. $\endgroup$ – Eric Wofsey May 31 '19 at 3:22
0
$\begingroup$

This answer is to correct an error in Camilo Arosemena-Serrato's answer and also reinterpret some of his results. His criterion for commutativity of multiplication works only for limit ordinals; for successors, his argument is incorrect since he incorrectly computed the lengths of the Cantor normal forms of the product and the conclusion is incorrect.

Before we turn to the correct statement for successors, let me first reinterpret his criterion for commutativity of addition. I claim the following:

Let $\alpha$ and $\gamma$ be ordinals. Then $\alpha+\gamma=\gamma+\alpha$ iff there exists an ordinal $\beta$ and natural numbers $i, j$ such that $\alpha=\beta\cdot i$ and $\gamma=\beta\cdot j$.

Proof: This condition is obviously sufficient. For necessity, note that if $\alpha=\omega^{\beta_n}\cdot l_n+\cdots+\omega^{\beta_1}l_1+l_0$ and $\gamma=\omega^{\beta_n}\cdot r_n+\cdots+\omega^{\beta_1}l_1+l_0$ as in the criterion in the other answer, we can take $\beta=\omega^{\beta_n}+\cdots+\omega^{\beta_1}l_1+l_0$, $i=l_n$, and $j=r_n$.

Remarkably, a similar criterion applies for multiplication of successor ordinals.

Let $\alpha$ and $\gamma$ be infinite successor ordinals. Then $\alpha\gamma=\gamma\alpha$ iff there exists an ordinal $\beta$ and natural numbers $i,j$ such that $\alpha=\beta^i$ and $\gamma=\beta^j$.

Proof: Sufficiency is again obvious. For necessity, let $\alpha$ and $\gamma$ have Cantor normal forms $$\alpha=\omega^{\alpha_n}\cdot l_n+\cdots+\omega^{\alpha_1}\cdot l_1+l_0$$ and $$\gamma=\omega^{\gamma_m}\cdot r_m+\cdots+\omega^{\gamma_1}\cdot r_1+r_0.$$ Assume without loss of generality that $n\geq m$. We have $$\alpha\gamma=\omega^{\alpha_n+\gamma_m}\cdot r_m+\cdots+\omega^{\alpha_n+\gamma_1}\cdot r_1+\omega^{\alpha_n}\cdot l_nr_0+\omega^{\alpha_{n-1}}\cdot l_{n-1}+\dots + l_0 $$ and $$\gamma\alpha=\omega^{\gamma_m+\alpha_n}\cdot l_n+\cdots+\omega^{\gamma_m+\alpha_1}\cdot l_1+\omega^{\gamma_m}\cdot r_ml_0+\omega^{\gamma_{m-1}}\cdot r_{m-1}+\dots + r_0$$ (these are equations (3) and (4) in the other answer with the final parts $\alpha\cdot r_0$ and $\gamma\cdot l_0$ also expanded out).

Let $d=\gcd(m,n)$ and $$\beta=\omega^{\alpha_d}\cdot l_n+\omega^{\alpha_{d-1}}\cdot l_{d-1}+\dots+l_0$$ (note the first coefficient). I claim that $\alpha=\beta^i$ and $\gamma=\beta^j$ where $i=n/d$ and $j=m/d$. Expanding out $\beta^i$, this means we need to prove $\alpha_{xd+y}=\alpha_d\cdot x+\alpha_y$ when $0<y\leq d$, $l_{xd+y}=l_y$ if $0<y<d$, and $l_{xd}=l_nl_0$ if $0<x<i$, and similar statements for $\gamma$.

Let us start with the exponents. Comparing the terms of $\alpha\gamma$ and $\gamma\alpha$, we see that $\alpha_k=\gamma_k$ for $k\leq m$, $\alpha_{m+k}=\alpha_m+\alpha_k$ for $k\leq n-m$, and $\alpha_n+\alpha_{k}=\alpha_m+\alpha_{n-m+k}$ for $k\leq m$. Writing $\alpha_n=\alpha_m+\alpha_{n-m}$, the last equation tells us $$\alpha_{n-m}+\alpha_k=\alpha_{n-m+k}$$ after cancelling $\alpha_m$. Let us say that $a\leq n$ is good if $\alpha_{a}+\alpha_k=\alpha_{a+k}$ for all $k\leq n-a$; we know $m$ and $n-m$ are good, and if we prove $d$ is good we will have proved everything we need about the exponents. But good numbers are closed under subtraction of numbers that add to at most $n$ (if $a<b$ are good with $a+b\leq n$ we can show $\alpha_{b-a}+\alpha_k=\alpha_{k+b-a}$ by splitting $\alpha_k=\alpha_{a}+\alpha_{k-a}$ if $a\leq k\leq n-b+a$ and by cancelling $\alpha_a$ from $\alpha_b+\alpha_k=\alpha_{k+b}$ if $k\leq n-b$), and using the Euclidean algorithm we conclude that $\gcd(m,n-m)=d$ is good.

The coefficients work similarly. Comparing $\alpha\gamma$ and $\gamma\alpha$ again, we see that $l_k=r_k$ for $0\leq k< m$ and $l_m=r_ml_0$, $l_{m+k}=l_k$ for $1\leq k<n-m$ and $l_nr_0=l_{n-m}$, and $r_{m-k}=l_{n-k}$ for $0\leq k<m$. Letting $l'_k=l_k$ for $k\neq 0,n$ and $l'_k=l_nl_0$, we see that the $l'_k$ are both $m$-periodic and $(n-m)$-periodic (the latter since $l'_{m-k}=l'_{n-k}$ via $r_{m-k}$), and hence $d$-periodic using the Euclidean algorithm. This gives us exactly what we need for the coefficients.


This leaves a few remaining loose ends: what happens if $\alpha$ or $\gamma$ is finite, or if only one of $\alpha$ and $\gamma$ is a successor ordinal. If $\alpha$ and $\gamma$ are both finite they of course commute. If $\alpha$ is finite and $\gamma$ is infinite, it is easy to see that they do not commute unless $\alpha$ is $0$ or $1$. Finally, if $\alpha$ is a successor and $\gamma$ is a limit and they commute, comparing the number of terms in the Cantor normal forms of $\alpha\gamma$ and $\gamma\alpha$ shows that $\alpha$ must be finite (if $\alpha$ has $n+1$ terms in its Cantor normal form and $\gamma$ has $m$, then $\alpha\gamma$ will have $m$ terms and $\gamma\alpha$ will have $m+n$ terms). It then follows easily that either $\alpha=1$ or $\gamma=0$.

$\endgroup$

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.