Noncommutative addition

Briefly try to imagine a world in which $2+ 1 \neq 1 + 2$. Unfortunately, if we take $1$ and $2$ to be the usual natural numbers, then that world cannot exist. In solid terms, we can say that addition is "commutative" in the natural numbers. We can, however, imagine a world in which $\omega + 1 \neq 1 + \omega$ is true, as long as $\omega$ has the right properties. Since natural numbers won't work, we need to work with numbers that lie "outside" of the natural numbers. The caveat? $1$ (and every natural number) must also exist in this class. If they don't, then addition can't be defined.

So, we need two things to make this world possible. First, we need to generalize natural numbers to this class, known as ordinal numbers. As a constraint, addition between generalized natural numbers must still be commutative. Second, we have to find out what $\omega$ is, as it certainly cannot have an analog in the natural numbers.

Let's get back to the basics of addition. Take two collections of objects to be $\{ \blacksquare, \blacksquare\}$ and $\{ \blacksquare\}$. I'm using set notation here as a hint of what's about to come. Clearly, adding them together gives us $\{ \blacksquare, \blacksquare, \blacksquare\}$. This is evidently just telling us that $2+1=3$. Making things more rigorous, we can "add" the collections in two ways: one way is to take the first and append it to the end of the second, and the other is to take the second and append it to the first. Why not just take the second collection and insert it into the middle of the first? It's certainly a valid way to add them together, physically, but mathematically addition is an operation that can be done only two ways: $a+b$ or $b+a$. So we're restricting ourselves to those two specific ways collections can be "added" together.

In a sense, this means that the elements inside each collection remain completely untouched. There are no elements being inserted in between others, and there are no elements being arbitrarily rearranged. We're free to make things more precise now; let's give each element a unique identification as well. This allows us to move from working with collections to the sets of set theory, which must all have distinct elements.

How do we represent numbers as sets, then? This comes to a problem which has an easy solution, using set theory with natural numbers, and a hard solution using only set theory. We'll opt for the former. We can define a number $n$ as

$n = \{ 1_*, 2_*, 3_*, \dots, n_* \} \quad a_* \in \mathbb{N}$

Of course, $n$ is a set and $a_*$ are natural numbers. Thus, we are not defining $n$ as a natural number, but as what we'll call an ordinal number. This ends up being close to the generalization of natural numbers that we want, but we're not there yet. Applying this definition to the toy example I already gave leads to:

$\{ 1_1, 2_1\} + \{1_2\} = \{ 1_1, 2_1, 1_2\}$ $\{1_2\} + \{ 1_1, 2_1\} = \{1_2, 1_1, 2_1 \}$

Where I used the asterisks as a way to distinguish sets (they're arbitrary outside of that). Since this is representing $2+1 = 3$ and $1 +2 = 3$, we immediately run into a problem. From our definition above, $3$ must be $\{1_*, 2_*, 3_*\}$. Instead we got two different answers, neither of which agree. They make matters worse on their own, too, as they break the constraint that addition must be commutative for "ordinalized" natural numbers. Something's missing.

Let's address these two issues at the same time. We must have that $\{ 1_1, 2_1, 1_2\}, \{1_2, 1_1, 2_1 \}$ and $\{1_*, 2_*, 3_*\}$ represent the same ordinal. More generally,

$a+b = \{ 1_1, 2_1, \dots, a_1\} + \{ 1_2, 2_2, \dots, b_2\} = \{ 1_1, 2_1, \dots, a_1; 1_2, 2_2, \dots, b_2\} \to \{ 1_*, 2_*, \dots, c_*\} = c$

Where $a_* + b_* = c_*$, and the semicolon was added for emphasis. Strict equality is impossible, but instead we can talk about "equivalence classes" - a family of sets where $n = \{ 1_*, 2_*, 3_*, \dots, n_* \}$ acts as a representative.

An immediate guess is that we can base this equivalence class on the cardinality (number of elements) of each set, but it turns out to be too broad such that nothing interesting happens. So we want cardinality to be a necessary, but not sufficient, condition for equivalency. We also want to be able to confirm whether two sets are in the same equivalency class without having to reference the representative. Our candidate now is to look at bijective functions between sets of an equivalence class. Bijective is the key word here, it's what ensures that every set in the equivalence class has the same cardinality. To get us started, we need to find a function

$F: \{ 1_1, 2_1, \dots, a_1; 1_2, 2_2, \dots, b_2\} \to \{ 1_*, 2_*, \dots, c_*\}$ $F: a + b \to c$

The indices become useful here because they allow us to define this function piecewise

$F(u_n) = (u_n)_* \text{ if } n=1 ; \quad (u_n+a_1)_* \text{ otherwise}$

Where $(u_n)_*$ is just a relabeling operation. Keep in mind that the indices are arbitrary, any relabeling of them just translates to a trivial redefinition of the mapping function. We can check that this function gives us the right values:

$\begin{matrix} u & F(u) \\ 1_1 & 1_* \\ a_1 & a_* \\ 1_2 & (a + 1)_* \\ b_2 & (a+b)_*=c_* \\ \end{matrix}$

And that this function has an inverse (i.e. is bijective):

$F^{-1}(u_n) = (u_*)_1 \text{ if } u_* \le a_1; \quad (u_*-a_1)_2 \text{ otherwise}$

We've thus made a bijective function which maps $a+b$ to $c$ and vice-versa. Similarly, we can define a function $G: a+b \to b + a$ where $a<b$ by:

$G(u_n) = \begin{cases} u_2, & \text{ if } n=1 \\ (u + a)_2, & \text{ if } n=2 \text{ and } u \le b - a \\ (u + a - b)_1, & \text{ otherwise } \end{cases}$

With a visualization to help give a better idea of how that function was defined.

We can continue this process to find more functions between arbitrary members of a congruence class. I'm not going to show how, but the idea is the same as what we've already done. What's important is that we now have a complete definition of an ordinal $n$:

Definition: $n$ is an ordinal number if and only if there is a bijective function $F: n \leftrightarrow n_0$ where $n_0 = \{ 1_*, 2_*, 3_*, \dots, n_* \} \quad a_* \in \mathbb{N}$

In addition, the function $G(u)$ which maps $a+b$ to $b+a$ is the only thing allowing them to commute. This means that $a + b \neq b + a$ will be true whenever this function is (or cannot) be defined.

These last two observations are crucial: If we want to find an ordinal $\omega$ such that $\omega + 1 \neq 1 + \omega$, then we need it constructed in a way that $G(u)$ cannot exist.

Let's take a slight step back and look at ordinals as a whole. For any natural number $a$ there is a distinct natural number $1+a$. We can also define ordinals that corresponds to both. If we want ordinals to be a larger class of numbers, then we have to get creative. We can define a new ordinal $\omega$ such that $1+ \omega = \omega$. There is no natural number which has this property, so it must be a completely new "number". In fact, it's not hard to see that this is essentially an infinite number. In better terms, we can call $\omega$ a transfinite ordinal. It can be represented as

$\omega = \{1_*, 2_*, 3_*, 4_* ,\dots \}$

Or as an ordinal number with no endpoint (the smallest one, in fact). To justify this, let's go back to the problem of defining $G(u)$. With $1+ \omega$ we can define

$F(u_n) = \begin{cases} (u_n)_* & \text{ if } n=1 \\ (u_n+1)_* & \text{ otherwise} \end{cases}$

Which maps $1+ \omega \to \omega$ and is clearly defined. Qualitatively, this is more or less "shifting" the elements of $\omega$ one to the right. However, this is where things get strange. We can't define a function which maps $\omega + 1$ to $\omega$. If we try, this is what we find:

$F(u_n) = \begin{cases} (u_n)_* & \text{ if } n=1 \\ (u_n+ \omega)_* & \text{ otherwise} \end{cases}$

This doesn't work because $\omega$ doesn't have a representation among natural numbers, meaning that $u_n+ \omega$ cannot be defined in any meaningful way. The immediate consequence is that they must occupy different ordinal classes, or $\omega +1 \neq \omega$. So we finally have

$1+ \omega = \omega \neq \omega + 1$

While we can think of $1 + \omega$ as simply shifting the elements of $\omega$ by $1$, $\omega + 1$ doesn't have the same effect. Instead, it's "shifting" the sole element of $1$ infinitely to the right. This shift is ill-defined since "infinitely" doesn't mean anything in the realm of natural numbers. To the ordinals, however, it's a building block of what's called the transfinite ordinals, a class of unique ordinal numbers that can be derived from adding, multiplying, and exponentiating $\omega$.

$\text{Some examples of transfinite ordinals:}$ $\omega ^ 2, \: \omega \cdot 5 + 1, \: \omega^{\omega + 4} + 4$

Surprisingly enough, there are other transfinite ordinals out there which cannot be written in terms of $\omega$. I won't show you how to construct them here, but I plan on writing a post about that topic very soon. :)