Noncommutative addition

Briefly try to imagine a world in which 2+11+2 2+ 1 \neq 1 + 2 . Unfortunately, if we take 11 and 22 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 ω+11+ω\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? 11 (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=32+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+ba+b or b+ab+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 nn as

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

Of course, nn is a set and a a_* are natural numbers. Thus, we are not defining nn 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:

{11,21}+{12}={11,21,12} \{ 1_1, 2_1\} + \{1_2\} = \{ 1_1, 2_1, 1_2\} {12}+{11,21}={12,11,21} \{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=32+1 = 3 and 1+2=31 +2 = 3, we immediately run into a problem. From our definition above, 3 3 must be {1,2,3}\{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 {11,21,12},{12,11,21}\{ 1_1, 2_1, 1_2\}, \{1_2, 1_1, 2_1 \} and {1,2,3}\{1_*, 2_*, 3_*\} represent the same ordinal. More generally,

a+b={11,21,,a1}+{12,22,,b2}={11,21,,a1;12,22,,b2}{1,2,,c}=ca+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=ca_* + 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,,n}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:{11,21,,a1;12,22,,b2}{1,2,,c} F: \{ 1_1, 2_1, \dots, a_1; 1_2, 2_2, \dots, b_2\} \to \{ 1_*, 2_*, \dots, c_*\} F:a+bc F: a + b \to c

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

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

Where (un) (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:

uF(u)111a1a12(a+1)b2(a+b)=c \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):

F1(un)=(u)1 if ua1;(ua1)2 otherwise 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+ba+b to cc and vice-versa. Similarly, we can define a function G:a+bb+aG: a+b \to b + a where a<ba<b by:

G(un)={u2, if n=1(u+a)2, if n=2 and uba(u+ab)1, otherwise  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 nn:

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

In addition, the function G(u)G(u) which maps a+ba+b to b+ab+a is the only thing allowing them to commute. This means that a+bb+aa + 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 ω+11+ω \omega + 1 \neq 1 + \omega, then we need it constructed in a way that G(u)G(u) cannot exist.

Let's take a slight step back and look at ordinals as a whole. For any natural number aa there is a distinct natural number 1+a1+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+ω=ω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

ω={1,2,3,4,} \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)G(u) . With 1+ω1+ \omega we can define

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

Which maps 1+ωω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 ω+1 \omega + 1 to ω \omega. If we try, this is what we find:

F(un)={(un) if n=1(un+ω) otherwise 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 un+ωu_n+ \omega cannot be defined in any meaningful way. The immediate consequence is that they must occupy different ordinal classes, or ω+1ω \omega +1 \neq \omega . So we finally have

1+ω=ωω+1 1+ \omega = \omega \neq \omega + 1

While we can think of 1+ω 1 + \omega as simply shifting the elements of ω\omega by 11, ω+1\omega + 1 doesn't have the same effect. Instead, it's "shifting" the sole element of 11 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.

Some examples of transfinite ordinals: \text{Some examples of transfinite ordinals:} ω2,ω5+1,ωω+4+4 \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. :)

Note by Levi Walker
1 year, 9 months ago

No vote yet
1 vote

  Easy Math Editor

This discussion board is a place to discuss our Daily Challenges and the math and science related to those challenges. Explanations are more than just a solution — they should explain the steps and thinking strategies that you used to obtain the solution. Comments should further the discussion of math and science.

When posting on Brilliant:

  • Use the emojis to react to an explanation, whether you're congratulating a job well done , or just really confused .
  • Ask specific questions about the challenge or the steps in somebody's explanation. Well-posed questions can add a lot to the discussion, but posting "I don't understand!" doesn't help anyone.
  • Try to contribute something new to the discussion, whether it is an extension, generalization or other idea related to the challenge.
  • Stay on topic — we're all here to learn more about math and science, not to hear about your favorite get-rich-quick scheme or current world events.

MarkdownAppears as
*italics* or _italics_ italics
**bold** or __bold__ bold

- bulleted
- list

  • bulleted
  • list

1. numbered
2. list

  1. numbered
  2. list
Note: you must add a full line of space before and after lists for them to show up correctly
paragraph 1

paragraph 2

paragraph 1

paragraph 2

[example link]( link
> This is a quote
This is a quote
    # I indented these lines
    # 4 spaces, and now they show
    # up as a code block.

    print "hello world"
# I indented these lines
# 4 spaces, and now they show
# up as a code block.

print "hello world"
MathAppears as
Remember to wrap math in \( ... \) or \[ ... \] to ensure proper formatting.
2 \times 3 2×3 2 \times 3
2^{34} 234 2^{34}
a_{i-1} ai1 a_{i-1}
\frac{2}{3} 23 \frac{2}{3}
\sqrt{2} 2 \sqrt{2}
\sum_{i=1}^3 i=13 \sum_{i=1}^3
\sin \theta sinθ \sin \theta
\boxed{123} 123 \boxed{123}


There are no comments in this discussion.


Problem Loading...

Note Loading...

Set Loading...