How has mathematics gotten so abstract?
What's the meaning of "numbers" and "arithmetic operations"? We consult Georg Cantor's turtles and look at Giuseppe Peano's code.
Today, mathematics is regarded as a supremely abstract science. On forums such as Stack Exchange, trained mathematicians sneer at newcomers who ask for intuitive explanations of esoteric mathematical concepts. Indeed, persistent attempts to relate the foundations of math to reality have become the calling card of online cranks.
I find this ironic: for millennia, mathematics was more or less a natural science. We had no philosophical explanation for why 2 + 2 should be equal to 4. We simply looked at what was happening around us and then tried to distil the rules. Abstractions were important, but they needed to be rooted in objectivity. It wasn’t enough for our axioms to be consistent: the angles of your hypothetical triangle needed to line up with the real world.
That said, even in antiquity, the reliance on intuition would at times appear untenable. A particular cause for concern were the outcomes of thought experiments that involved repeating a task without end. The most famous example is Zeno’s paradox of motion. If you slept through that class, imagine the scenario of Achilles racing a tortoise:
We can reason that after a while, Achilles will catch up to the turtle’s original position (red dot); however, by the time he gets there, the animal will have moved some distance forward (yellow dot):
Next, consider the time needed for Achilles to reach the yellow dot; once again, before he gets there, the turtle will have moved forward a tiny bit. This process can be continued indefinitely; the gap keeps getting smaller but never goes to zero, so we must conclude that Achilles can’t possibly win the race.
Ironically, the problems caused by infinity lingered on the periphery of mathematics for centuries, taking the center stage only after we attempted to fix them with calculus. Calculus gave us a rigorous solution to the ancient puzzle: an infinite sum of time slices can be a finite number, so Achilles does catch up to the tortoise. But to arrive at that result, the new field relied on the purported existence of infinitely small numbers (infinitesimals). Its founders struggled to explain how to construct such entities, where to find them on the real number line (you can’t), and whether they’re safe to mix with real number algebra in the first place.
Over time, this prompted some mathematicians to try and build a more general model of mathematics, starting from the ground up — that is, from the principles of formal logic. In particular, one prominent faction of the movement sought to define numbers and arithmetic operations in a way that was fully independent of the physical realm.
By golly, Mr. Peano, it all adds up
In the late 19th century, Giuseppe Peano successfully answered this call. His system posits the existence of a single initial number — conventionally, zero — and then defines a successor function S(…). The function doesn’t do anything specific; it has a couple of basic properties defined, but for the most part, it’s just a way to signal that each subsequent number has some directional relationship to the previous one.
This allows us to define numbers — really, just a collection of labels — solely in terms of a succession relationship from zero:
The operator “:=” means “is defined as”; we’ll use it to distinguish first-order definitions from the results we derive down the line.
Again, don’t get hung up on what S(…) means. It just tells us that “1” is formed from “0”, “2” is formed from “1”, and so on. To use a crude metaphor, we’re not describing how babies are made; we’re just saying “this is a parent” and “this is a child”.
While this might seem mundane, the scheme reduces many other problems to the process of induction and recursion. For example, to solve 2 + 2, a visitor from outer space wouldn’t need any a priori knowledge of what “2” and “+” mean. We can teach them the concept of addition using the following two rules:
This notation may appear abstract, so to tease it out, let’s role-play a spacefaring alien and try to calculate 2 + 2.
Because the second operand is non-zero, we can’t apply the first rule just yet. That said, from the construction of Peano numbers, we know that the label “2” means the same thing as S(1). In light of this, we can rewrite 2 + 2 in a way that lets us use the second rule:
At this point, we’ve shown that 2 + 2 is the same as S(2 + 1). To solve the original equation, we still need to find the value of the nested addition: 2 + 1. This can be done by applying the same substitution technique once more:
We have restated 2 + 2 as S(2 + 1), and then 2 + 1 as S(2 + 0). Lo and behold — the addition nested in that last expression lets us invoke the earlier rule #1. The rule says that a + 0 = a, so 2 + 0 = 2; it follows that S(2 + 0) is the same as S(2).
Further, from the construction of Peano numbers, we know that our chosen label for S(2) is 3; hence, 2 + 1 = 3. With this sorted out, we go back to the initial step where we expressed 2 + 2 as S(2 + 1). We substitute 2 + 1 with 3 and get the final answer:
If you work with software, you might appreciate the following C code that implements roughly the same logic (demo):
#include <stdio.h> struct number { char* label; struct number* next; } five = { "5", NULL }, four = { "4", &five }, three = { "3", &four }, two = { "2", &three }, one = { "1", &two }, zero = { "0", &one }; struct number* succ(struct number* num) { return num->next; } struct number* pred(struct number* num) { struct number* ret = &zero; while (succ(ret) != num) ret = succ(ret); return ret; } struct number* add_numbers(struct number* num_a, struct number* num_b) { if (num_b == &zero) return num_a; return succ(add_numbers(num_a, pred(num_b))); } int main() { printf("2 + 3 = %s\n", add_numbers(&two, &three)->label); }
In this program, instead of relying on built-in integers, we start with a unidirectional linked list of strings: “0” → “1” → “2” → “3” → “4” → “5”. This data structure encodes the successor relationship between the labels without giving them any further meaning.
Next, we define a trivial helper called succ(x), which returns the successor of x, along with a slightly more complicated function called pred(x), which finds the element to which x is the successor. Finally, add_numbers(a, b) is a straightforward implementation of a pair of recursive rules for Peano addition, as outlined earlier on.
Again, the merit of this approach is that it lets us model arithmetic without any external assumptions about the nature of numbers, the significance of the addition operator, and so forth. We used familiar labels (0, 1, 2, 3, 4, …), but we could’ve used some other ordered collection of abstract symbols (🥔, 🎵, 🐸, 🌀, 🐱, …). If so, we’d have gotten an equivalent model of math in which 🐸 + 🐸= 🐱.
Of course, Peano arithmetic is too cumbersome for everyday tasks; instead, it serves as a minimal model for theoretical work. It is used similarly to how computer scientists use Turing machines; no one wants to browse the internet on a Turing-style computer, but if you proved that P = NP for a Turing machine, this would have implications for more practical computing architectures too.
Numbers from sets
The approach outlined above was revolutionary and led to breakthroughs such as the Gödel incompleteness theorem; however, it still didn’t offer a particularly good model of infinite quantities. For that, mathematicians needed to turn to an even more exotic framework: set theory.
In set theory, numbers are conventionally defined as labels for specific, ordered sets. To get started with the construction process, we only need an empty set ({}), the existence of which we take as an axiom. For the purpose of constructing numbers, we label this set “zero”:
To define the successor number, we add an element to the set. To avoid inventing arbitrary new elements, we can simply embed the previously-conjured number zero in the successor set:
If this seems confusing, you can think of sets as boxes. We started with an empty box with zero items inside; we then sealed the box and placed it in a larger container, so the larger box now contains a single element. For this tally, the contents of that smaller, sealed box are of no consequence.
After that, we can’t define the next successor as {0, 0}; this is because in standard set theory, every set element must be unique. That said, as discussed earlier, a “naked” element n is distinct from a box containing that element (i.e., a new set {n}), so we can do this:
Note that the second element of this new set — {0} — is the same as what we’ve constructed to represent “1”. In other words, this construction method is equivalent to saying that 2 = {0, 1}.
To get to the third successor, we need to put one more element in the set. At this point, we can’t reuse 0 or 1, but we can embed the recently-created set representing 2:
This process can continue for as long as we’d like, e.g.:
In set theory, the labels we’re creating are called ordinals. Note that every ordinal is a set of all the preceding ordinals, and that the set never contains itself.
If you’re seeing parallels to the iterative construction of Peano numbers, this is not an accident; the two approaches are conceptually similar, it’s just that in this instance, the underlying mathematical structure of each number is spelled out more explicitly. The general algorithm is that we build number n + 1 by combining the contents of the preceding set n with a copy of n encased in a new set. The set-joining operation is known as union (∪), so we can formalize a Peano-like successor function for ordinals as:
To infinity… and beyond
Almost all mathematicians accept the existence of infinite sets, the prototypal example of which is the set of all natural numbers, ℕ. Every natural number itself is finite, but there is no upper limit on how large these numbers can get; whenever you pick some n, I can always best you by shouting “n + 1”.
The ordered set of all natural numbers looks like the product of our method for constructing ordinals — that is, if we allowed the process to continue without end:
It’s tempting to ask if the set can function as an infinite ordinal — i.e., an infinite number — and if yes, what numerical properties does it have?
Well, we can say right off the bat that the ordinal we’re talking about wouldn’t be a member of ℕ: every element of ℕ is finite. By extension, we can conclude that the ordinal must not be a successor to any natural number: if n is a member of ℕ, then so is n + 1, so the presence of a successor relationship between a finite number and an infinite number would lead to the same contradiction.
Can such an unmoored, infinite ordinal exist? Well, that’s up to us to decide: conjuring it doesn’t lead to any outright paradoxes and opens up some weird but occasionally useful math.
We can name this ordinal ω; again, its set-theoretic representation is just:
Of course, inventing a symbol isn’t much of an accomplishment; the big question is whether, under the axioms of set theory, we can derive any useful arithmetic for this mysterious entity.
In school, you might have been exposed to notation along the lines of:
In an earlier article, I quipped that this notation is just a glorified calculator error message — all it tells us is that the result is too large for reals:
That said, if you’re accustomed to this way of thinking about infinity, it’s tempting to assume that the rule should apply to actual infinite numbers — i.e. that ω should be the same as ω + 1. Let’s test that hypothesis.
In line with the usual Peano rules, we can express the ω + 1 sum as ω + S(0); this expression, in turn, is equivalent to S(ω + 0) = S(ω). As a reminder, the set-theoretic successor function takes the original infinite set of natural numbers (ω = ℕ) and then embeds that set as a new element to construct the next ordinal. We get:
We have previously established that ω itself cannot be a member of ℕ, because that would make it a natural number, and therefore, a finite quantity. Yet, the newly-constructed set corresponding to ω + 1 evidently does contain that element; this tells us that the set is categorically different from ℕ. We must conclude that ω ≠ ω + 1. More specifically, because ω + 1 contains ω, it sits higher in the rank of ordinals, a relationship we can write as ω < ω + 1.
If you’re still unpersuaded that the sets are qualitatively different, there are two additional observations we can make. First, the set ω had no greatest element, but ω + 1 evidently does. Second, ω contained just one element that wasn’t a successor to a natural number (0), but ω + 1 contains two (0 and ω). In other words, if infinite sets exist, ω and ω + 1 differ in several important ways.
But lest we get too cozy with this new reality: addition involving infinite ordinals is not necessarily commutative! Consider the following sum: 1 + ω. Strictly speaking, we can’t use the earlier approach to find the solution: the second operand is not a successor of any natural number, which stops us from making the initial substitution required by the Peano ruleset. I offer a more rigorous approach in a comment below this post; that said, very informally, we can intuit that the addition of ω boils down to incrementing the first operand forever:
Recall that we defined the ordinal 1 as a single-element set containing zero: {0}. Starting from that set and applying the successor function, we end up constructing ordinal 2 — another name for {0, 1}. The next application of the nets us 3, aka {0, 1, 2}:
If we repeat this operation forever, we obtain an infinite set { 0, 1, 2, 3, 4, … }. The element ω is not a successor of any natural number, so in contrast to the earlier ω + 1 case, it can’t make it into the set through the repeated application of S(…). Upon closer inspection, the ordinal representing 1 + ω appears to be indistinguishable from ℕ. We know that ω is also just another name for ℕ, so we can write the following equality: 1 + ω = ω. Few paragraphs earlier, we showed that ω < ω + 1. This leads to a surprising result: 1 + ω < ω + 1.
One might ask if non-commutative addition is a violation of one of the axioms of standard arithmetic. It isn’t, on a technicality: the rules apply only to finite numbers, such as the members of ℕ. Luckily for us, ω isn’t invited to that club.
Before we wrap up, let’s have a look at another interesting corner case: ω + ω (aka ω · 2). Again, very informally, we can analyze this as starting with ω = { 0, 1, 2, 3, 4, … } and then iteratively extending the set through the successor operation that goes on forever. We first append ω, then ω + 1, then ω + 2, and so on:
The tail end of this ordered set is an infinite sequence of successors to ω; as in all the earlier cases, ω · 2 can’t be a member of itself, so ω · 2 must not be reachable by incrementing ω. This is analogous to how ω couldn’t be reached by incrementing any finite number; the discontinuity repeats for each multiple of ω.
Cardinal sins
It’s tempting to say that each of our set-theoretic numbers describes the element count of the underlying set:
Yet, in the realm of the infinite, this statement is suspect. If we start counting elements from one, we can never get to ω or above because there’s no successor relationship between counting numbers and infinite ordinals. By this method, the size of any infinite set appears to be incalculable.
Luckily, there are several ways to reason about set sizes without resorting to a tally. The simplest approach is to declare that set A is smaller than B if A is a strict subset of B. For example, we may assert that { 🐱, 🥔} is smaller than { 🐱, 🥔, 🐸 }.
We could also consider two sets to be of equivalent “magnitude” if we can map their elements one-to-one. This is known as bijection. It doesn’t matter which element gets mapped to which, as long as there are no orphaned members on either side:
This particular measure of equivalency on the basis of a one-to-one mapping is called cardinality.
The concepts are dead simple for finite sets, but consider the set of natural numbers next to the set of every even number — let’s call it E. Obviously, E is a strict subset of natural numbers, so by our first rule, we ought to say that E is smaller than ℕ. It’s also clear that if we construct the most obvious mapping — every number e in E to the same number n in ℕ — we’ll end up with an infinite set of unpaired odd numbers on the ℕ side; because of this, it’s tempting to conclude that the size of these sets doesn’t align.
Yet, the following one-to-one mapping is fine:
This works because the sets are infinite but only contain finite numbers. For any finite n picked from ℕ, n multiplied by two is also finite and therefore can be found in E. Because at least one viable bijection exists, we say that the set of natural numbers has a specific infinite cardinality — aleph-null, ℵ0 — and that the cardinality of the set of even numbers is the same.
Do any other infinite cardinalities exist? The answer, as demonstrated by Georg Cantor, appears to be yes! Assume the existence of some arbitrary one-to-one mapping between every natural number and every infinite decimal sequence representing reals between 0 and 1, e.g.:
The values are chosen for illustration purposes, but the particulars are unimportant; we’re just assuming that some kind of a 1-to-1 map can exist. Our objective is to see if this general assumption can hold.
To show that it can’t, let’s construct the decimal representation of a new real number, d. We start by looking at the first row above:
We take the underlined (first) decimal digit of the sequence and then choose any value other than this one for the corresponding digit in d. In this case, the offending digit is 1, so we can pick 0, 2, 3, 4, 5, 6, 7, 8, or 9. Let’s go with 6:
We then proceed to the second row, this time looking at at the second decimal digit — essentially, following the diagonal pattern underlined in the assignment diagram. Once again, for the second decimal digit of d, we choose any value other than the actual digit marked in row 2; since the highlighted value is 5, we can pick 2 instead:
In row three, we can replace 9 with 1; in row four, let’s substitute 5 with 4. For row five, we trade 1 for 3; in row six, we use 8 instead of 7. We keep following the diagonal pattern to infinity:
What’s special about this result? Well, by construction, d is not associated with any integer because it differs by at least one digit from every decimal sequence in the map. For example, it can never match row 1 because the first decimal digit is 6 instead of 1; it also doesn’t match row 2 because the second decimal digit is 2 instead of 5. At the same time, d is a decimal sequence and thus a member of ℝ; the fact it’s not associated with an integer contradicts the possibility of a 1-to-1 mapping between the two sets, even if we just limit ourselves to the real interval of 0 to 1.
A good way to think about the result is that the mapping can’t exist because you can’t successively enumerate all real numbers even if the list goes on forever. You can always point to a missing element. In other words, ℝ is “unenumerable” — more properly, uncountable — and its cardinality (cardinality of the continuum) is greater than that of ℕ (ℵ0).
Are there any cardinalities in between ℕ and ℝ? Mathematicians don’t think so, but this hypothesis is provably undecidable within the traditional axioms of set theory.
“I don’t like this”
Georg Cantor’s work caused great consternation and controversy at the turn of the century. The author had to put up with persistent bullying by another, more prominent mathematician — Leopold Kronecker — and struggled with profound depression later in life. Today, Cantor’s results are accepted by most mathematicians, but they continue to cause flare-ups on online forums and personal blogs.
The most primal objection to Cantor’s argument is that there ought to be just one kind of infinity; how can there be several flavors of “repeats without end”? Of course, if you’ve made it this far, you know that if we permit the existence of the infinite set of natural numbers, we organically end up with a hierarchy of distinct ordinal infinities. Cantor’s cardinalities are just a cherry on top.
Another common but shallow criticism is that the notion of cardinality doesn’t align with other conceivable methods of measuring set size. As we’ve discussed, this is true, but it’s not as profound as it seems: cardinality is just one of several possible size hierarchies, and for infinite sets, you can’t get these hierarchies to agree.
The remaining objections tend to be procedural. For example, neither the mapping between ℕ and ℝ, nor the construction of d, can be completed in finite time — so do these mathematical objects even exist? The question is fair but circular: we started with the premise that ℕ exists, even though this set can’t be produced by a finite procedure. If we reject the notion of infinite objects, there’s no ℕ, no ℝ, and no cardinalities.
A more interesting procedural concern is whether there might be something counterintuitive about infinite decimal sequences. The argument presented earlier essentially treats decimals as strings, but we know that there are some gotchas with that: for example, 0.999… = 1, so not every distinct sequence of digits maps to a distinct real. We can easily sidestep this issue by limiting the digits we use for the construction of d, but fundamentally — if ℝ is our only intuitive example of a higher-cardinality set, maybe we’re making a subtle reasoning error somewhere along the way?
Instead of dwelling on decimals, we can take ℝ out of the picture and lean on the concept of power sets. A power set, denoted by a fancy script 𝒫, is just a collection of all possible subsets of some other set. For example, if we take X = {A, B, C}, then 𝒫(X) contains the following eight subsets:
To enumerate these subsets, we just count in binary; for each of the three elements, we’re making a binary choice to include or not include it, resulting in 23 possible outcomes:
If ℕ exists, it seems uncontroversial to also permit the existence of its power set, 𝒫(ℕ). Infinite power sets are not a mathematical necessity, but there’s no obvious reason to allow one and not the other.
If we allow 𝒫(ℕ), we must conclude that it has a cardinality higher than ℕ. To show this, we start by assuming the existence of an arbitrary one-to-one mapping between each element n of ℕ and each element x of 𝒫(ℕ). An example of this is shown on the left:
The mechanics of the assignments don’t concern us; as before, the question we’re trying to answer is whether any contradiction-free mapping can exist.
The boxes on the right are included as a visual aid: they provide a notionally infinite, bitmap-style overlay; the boxes in each row indicate which elements of ℕ appear in subset x on the left.
Given this mapping, we construct a new set D by following the underlined, diagonal pattern in the bitmap view. We include number n in D if and only if the underlined square is empty — that is, if n itself doesn’t appear in the subset it’s paired with. To illustrate, in the first row, the number n = 1 is not included in x = {2, 5}, so we put n in D; this situation repeats in rows 2 and 5. In contrast, in rows 3 and 4, n shows up in x, so we skip it. The result is:
As before, set D is evidently not paired with an integer because it differs from each x by at least one element. At the same time, D is clearly just a collection of natural numbers, so it ought to appear in the power set 𝒫(ℕ). Thus, we have a contradiction. You can’t successively enumerate every member of 𝒫(ℕ) to build the mapping. The cardinalities differ; bijection between ℕ and 𝒫(ℕ) can’t exist.
As a parting shot, let’s ponder what stops us from mapping naturals to naturals and then using the diagonal argument to show that the cardinality of ℕ is different from ℕ. The distinction is that ℝ can be thought of as a collection of all infinite decimals (e.g., ⅓ = 0.333…). In the same vein, 𝒫(ℕ) is a collection of all infinite binary sequences. In these cases, any new infinite sequence produced by traversing an infinite diagonal is guaranteed to be in the set. In contrast, every member of ℕ is finite, even if the set itself never ends. It follows that a newly-conjured infinite sequence of digits can’t be assumed to correspond to a member of ℕ. And if the constructed sequence is not in ℕ, then it doesn’t disprove anything.
Is any of this real?
Maybe? If infinity lurks in some dark corners of the physical universe, we probably have no way of ascertaining its numerical properties. In the absence of this, we have a toolkit for creating weird worlds that restate the rules of formal logic in increasingly mind-bending ways — and sometimes help prove a theorem or two.
Because the behavior of infinite sets is bizarre, there is a school of mathematics that rejects their existence on philosophical grounds. Heck, there is a small number of mathematicians who reject infinity altogether. The difficulty is that such decisions require discarding vast amounts of useful math — or at the very least, tossing out an explanation of why we’re doing that math in a particular way.
On some level, this might not be a big deal: calculus is usually still taught without providing a rigorous justification for limits or infinitesimals. On the flip side, as almost any calculus student will attest, it’s an intellectually unsatisfying approach.
Just as important, without all these wonderfully confusing notions of infinity, how do you keep the riff-raff out of math?
👉 Reader exclusive: for an essential Peano arithmetic calculator, click here.
Further reading in the series:
I write well-researched, original articles about geek culture, electronic circuit design, algorithms, and more. If you like the content, please subscribe.
Footnotes, part #1:
1) The reason I describe the "increment forever" method of calculating 1 + ω as "very informal" is that it doesn't give us solid intuition about cases such as 1 + (ω + ω). Are we incrementing 1 for "one forever" (= ω) or "two forevers" (= ω · 2)? I didn't want to cram too much detail into a single article, but if you're interested in a more principled approach, see this comment:
https://lcamtuf.substack.com/p/how-has-mathematics-gotten-so-abstract/comment/216119337
2) You often hear about "cardinal numbers", but they're not a part of the same hierarchy as ordinals and they play by different rules. One obvious difference is that cardinals are not labels for a specific set; each of them is a label for an entire class of sets.
3) There are multiple infinite ordinals that will have the same cardinality. For example, ℵ₀ (the cardinality of ℕ) covers ω, ω + 1, ω · 2, and so forth; ω is the "smallest" ordinal in the ℵ₀ class.
4) If we construct a set of all the countable ordinals (0, 1, 2, ..., ω, ω + 1, ..., ω·2, ..., ω², ...), we can imagine an uncountable ordinal that's strictly greater and therefore can't be possibly "counted to" using these countable infinities. As with ω, there is no mathematical necessity for it to exist, but it's a thought experiment that unlocks even more weird math. This uncountable ordinal is called ω₁ and is associated with a new cardinal ℵ₁. We can't prove or disprove that ℵ₁ is the same as the cardinality of ℝ.
5) If you're rattled about the loss of commutativity for infinite numbers, it's often the first thing to go when we start messing around with numbers, even without infinity. For example, quaternion algebra (https://lcamtuf.substack.com/p/complex-numbers-2-a-world-in-3d) is non-commutative.
6) If you read https://lcamtuf.substack.com/p/09999-1, you might be wondering if the arithmetic of infinite hyperintegers is different from infinite ordinals. The basic meaning of ω is the same, but there are some functional differences in how arithmetic operations are defined.
7) In addition to folks who object to the concept of infinity, there is a small number of mathematicians and philosophers who dislike set theory. For example, one prominent philosopher believes it's nonsensical to make a distinction between x and a set of containing x: https://ontology.buffalo.edu/04/AgainstSetTheory.pdf
PS. Thanks to Christopher Sahnwaldt for correcting a subtle mistake in #4. More notes in the comments attached to this one.
HN endorsements, for posterity:
"Why read this? Why be exposed to this slop?"
"A watered down Intro to Mathematics 101"
If I could read these comments, I would be very upset