Eli5: How define arithmetic operations from scratch with set theory?

83 views

Eli5: How define arithmetic operations from scratch with set theory?

In: 2

2 Answers

Anonymous 0 Comments

Start with [Peano arithmetic](https://en.wikipedia.org/wiki/Peano_axioms). The *natural numbers* {0, 1, 2, …} can be represented as follows:

* 0 is a natural number.
* Every natural number N has a unique *successor* S(N) which is also a natural number.

You can read “S(N)” as “the successor of N”. So, 1 is the successor of 0, so it’s S(0).

This lets you represent the naturals like this:

* 0 is 0
* 1 is S(0)
* 2 is S(S(0))
* 3 is S(S(S(0)))
* … and so forth.

Peano arithmetic turns out to be enough to do quite a lot. You can derive addition and then multiplication from these basic axioms. Here’s addition:

* X + 0, or 0 + X, is just X.
* S(X) + Y is the same as X + S(Y).

2 + 3 is represented as S(S(0)) + S(S(S(0))). By applying the last rule repeatedly, you can move all the S’s over to one side, giving S(S(S(S(S(0))))). Which is 5.

Multiplication of natural numbers is just repeated addition, so we can construct that similarly:

* X · 0, or 0 · X, is just 0.
* S(X) · Y is the same as (X · Y) + Y.

Notice that these rules imply that X · 1 is the same as X. We don’t need to have a separate rule for multiplying by 1; that happens automatically because X · 1 is the same as X · S(0) which is the same as (X · 0) + X which is the same as 0 + X which is the same as X.

You can represent Peano arithmetic in any other system that gives you the concepts of “zero” and “distinct successor”. For instance, Peano arithmetic can be represented in set theory as follows:

* 0 is represented as the null set {}, also called the empty set.
* For every natural number N, its successor is represented as {N, {}} (the set whose elements are N and the null set).

Which gives these examples:

* 0 is {}
* 1 is {{}, {}}
* 2 is {{{}, {}}, {}}
* 3 is {{{{}, {}}, {}}, {}}
* … and so forth.

For any number, you can construct its successor by making a set containing the number and the null set.

Since we already know how to do addition and multiplication on Peano numbers, we can adapt that to work on these numbers too.

Anonymous 0 Comments

All of this is after von Neumann and Peano, whose constructions are the standard ones in modern math (although many others are possible).

—–

You start by defining the non-negative integers. There are lots of ways to do that, but a simple way to start is to say that the symbol 0 represents the empty set {}. In a moment, we’ll make the symbol 1 represent the set containing the empty set, {{}}, the symbol 2 represent the set containing the empty set and the set containing the empty set, {{}, {{}}}, and so on, but those aren’t definitions yet.

Next, we need to be able to “add 1” or “count”. To do that, we define an operation s(n) called the *successor* operation. Again, there are many options here, but we’ll define s(n) = n (union) {n}. So s(0) = {} union {{}}, or just {{}}. We’ll use the symbol “1” for the successor of “0”, so 1 = {{}}.

Similarly, s(1) = {{}} union {{{}}}, or the set {{}, {{}}}. It’s confusing when we write it in brackets, but it may help to recognize that the two elements of this set are {} (that is, 0) and {{}} (that is, 1), so s(1) = {0,1}. We’ll denote this set by “2”. Similarly, s(2) = {0,1,2} and is denoted by “3”, s(3) = {0,1,2,3} and is denoted by “4”, and so on. While we’re not defining it this way yet, for intuition’s sake, it becomes clear that that natural number N ends up represented by the set {0, 1, 2, 3, … N-2, N-1}.

With me so far? If not, pause until you are, or post a reply and we can backtrack.

—–

Now, with the successor operation on sets established, we define the set of natural numbers. We’d like to do this with induction, but we can’t do that, because we don’t have natural numbers to induct on yet!

Instead, we define the set of natural numbers by taking all the sets S that are closed under the successor operation (that is, if a set x is in S, then s(x) is also in S) and contain the empty set, and taking their intersection. Intuitively, what we’re doing here is saying “we have to have the empty set, and therefore the successor (and the successor of the successor of the successor etc) of the empty set, but nothing else”. There is some set theoretic trickiness here, because “all the sets S satisfying a property” is a dangerous sort of statement to make, but we’ll skim over that for this explanation. (Alternately, you can [just take it as an axiom](https://en.wikipedia.org/wiki/Axiom_of_infinity), as standard set theory does, that the set we’d like to be the naturals exists.)

Since the set {0, 1, 2, 3, …} contains the empty set (0) and is closed under successors, the natural numbers must contain this set (since it’s one of the elements in the intersection that made the set of natural numbers at all). And similarly, no smaller set can be closed under the successor operation, so the intersection can’t be smaller than that. So it follows that the set of naturals is exactly the set {0, 1, 2, 3, …} or, equivalently, the set of all values that can be written as s(s(s(s(…s(0))))) for some level of nesting of the s’s.

This last property is important: **any natural number except 0 is a successor of another natural number**. If it weren’t, we could remove it from our set without breaking closure under the successor operation. More formally, if S is closed under the successor operation and contains the empty set, suppose x in S is not the empty set and is not a successor of any y in S. Then S{x} is closed under successors and contains the empty set as well. That means *x* can’t possibly appear in the intersection of all such sets, so S cannot have been the intersection of all such sets in the first place (because x is in S). Thus, no such S can ultimately be our set of naturals N.

Similarly, equality of natural numbers is just equality of sets, with its usual set-theoretic definition.

—–

Cool, we’ve got natural numbers. Now let’s add.

Define the operation + on natural numbers (which, remember, are really sets, but we’ll cease thinking about them as such now) by the following two properties:

* a + 0 = a for all a in N.
* a + s(b) = s(a+b) for all a, b in N.

Note that because any non-zero value may be written as s(b), this is a complete definition of addition. For example, 3 is s(2), so a + 3 = s(a + 2) = s(s(a + 1)) = s(s(s(a + 0))) = s(s(s(a))).

Multiplication can be similarly defined as:

* a * 0 = 0.
* a * s(b) = a + a*b

And again, the definition is complete because every non-zero value is a successor.