Eli5: How define arithmetic operations from scratch with set theory?
In: 2
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.
Latest Answers