How is addition defined?

Question

I've been reading On Numbers and Games and I noticed that Conway defines addition in his number system in terms of addition. Similarly in the analysis and logic books that I've read (I'm sure that this is not true of all such books) how addition works is assumed. From what I understand the traditional method of building the number system begins with the natural numbers (and zero)

$0:=|\emptyset|$

$1:=|\{\emptyset\}|$

$2:=|\{\emptyset,\{\emptyset\}\}|$

and so forth. In this construction addition could(?) be defined as the disjoint union of the sets associated with the two numbers. Then the integers could be defined as the additive inverse and so forth. Is this the ideal way to do it though, is there a more elegant method?

Answer 1

You don't have an a priori notion of cardinality, so you cannot really say things like "$0:=|\emptyset|$". In fact, before you can define cardinals you usually define ordinals, and usually the definition of the naturals precedes the definition of the ordinals.

The set-theoretic method begins by using the Axiom of Infinity, which states that there exists at least one inductive set; a set $X$ is inductive if and only if (i) $\emptyset\in X$; and (ii) For all $x$, if $x\in X$, then $s(x) = x\cup\{x\}\in X$.

So, let $X$ be any inductive set. Then we define $$\mathbb{N} = \cap\\{ A\subseteq X\mid \text{$A$ is inductive}\\}.$$ One can then prove that $\mathbb{N}$ is well defined (it does not depend on the choice of $X$) and satisfies "Peano's Axioms":

1. $\emptyset \in\mathbb{N}$.
2. If $x\in\mathbb{N}$, then $s(x) \in\mathbb{N}$.
3. For all $x\in\mathbb{N}$, $s(x)\neq\emptyset$.
4. For all $x,y\in\mathbb{N}$, if $s(x)=s(y)$, then $x=y$.
5. If $S\subseteq \mathbb{N}$ is inductive, then $S=\mathbb{N}$.

(In fact, 3 and 4 are just consequences of the definition of $s(x)$). We then define "$0$" to mean $\emptyset$, "$1$" to mean $s(0)$, "$2$" to mean $s(1)=s(s(0))$, etc.

Alternatively, you can begin with Peano's Axioms. Here, there is a primitive notion called "natural number", and a primitive symbol called $0$. We also have a primitive function $s$. The Peano Axioms would be:

1. $0$ is a natural number.
2. If $n$ is a natural number, then $s(n)$ is a natural number.
3. For all natural numbers $n$, $s(n)\neq 0$.
4. For all natural numbers $n$ and $m$, if $s(n)=s(m)$, then $n=m$.
5. Axiom Schema of Induction. If $\Phi$ is a predicate such that $\Phi(0)$ is true, and for all $n$, $\Phi(n)\Rightarrow \Phi(s(n))$, then for all natural numbers $k$, $\Phi(k)$.

(You can also begin with $1$ instead of $0$; I use $0$ because it then parallels the set-theoretic construction). We then define "$1$" to mean $s(0)$; and "$2$" to mean $s(1)=s(s(0))$, etc.

We then need the Recursion Theorem:

Recursion Theorem. Given a set $X$, an element $a\in X$, and a function $f\colon X\to X$, there exists a unique function function $F\colon\mathbb{N}\to X$ such that $F(0)=a$ and $F(s(n)) = f(F(n))$ for all $n\in\mathbb{N}$.

Once we have these definitions and theorem, we can start defining addition. Fix $n\in\mathbb{N}$. I'm going to define "add $n$", $+_n\colon \mathbb{N}\to\mathbb{N}$ by letting \begin{align*} +_n(0) &= n,\\\ +_n(s(m)) &= s(+_n(m)). \end{align*} Or, in usual notation, \begin{align*} n+0& = n,\\\ n+s(m) &= s(n+m). \end{align*}

With these definitions, we have:

Theorem. For all $n\in\mathbb{N}$, $n+0=0+n=n$.

Proof. Let $S=\{n\in\mathbb{N}\mid n+0=0+n=n\}$. Note that $0\in S$, since $0+0 = 0$ by the definition of addition. Now assume that $k\in S$; that means that $k+0 = 0+k = k$. Then $0+s(k) = s(0+k) = s(k)$ (first equality by the definition of addition with $0$, second by the induction hypothesis). And by the definition of addition with $s(k)$, we have $s(k)+0 = s(k)$. Therefore, $k\in S$ implies $s(k)\in S$. Thus, $S=\mathbb{N}$, as desired. QED

Theorem. For all $n\in\mathbb{N}$, $s(n)=n+1$

Proof. Let $S=\{n\in\mathbb{N}\mid s(n)=n+1\}$. First, $0\in S$, since $s(0) = 1 = 0+1$, by the previous theorem. Assume that $k\in S$; that means that $s(k)=k+1$. Then $s(s(k)) = s(s(k)+0) = s(k)+s(0) = s(k)+1$. So $k\in S$ implies $s(k)\in S$, hence $S=\mathbb{N}$. QED

Theorem. For all $\ell,n,m\in\mathbb{N}$, $\ell+(m+n) = (\ell+m)+n$.

Proof. Fix $\ell$ and $m$. Let $S=\{n\in\mathbb{N}\mid \ell+(m+n)=(\ell+m)+n\}$. We have $0\in S$, since $$\ell + (m+0) = \ell + m = (\ell+m) + 0.$$ Now assume that $k\in S$; that means that $(\ell+m)+k = \ell+(m+k)$. We prove that $s(k)\in S$. We have: $$(\ell+m)+s(k) = s((\ell+m)+k) = s(\ell+(m+k)) = \ell+s(m+k) = \ell+(m+s(k)).$$ Thus, if $k\in S$ then $s(k)\in S$. Hence, $S=\mathbb{N}$. QED

Lemma. For all $n\in\mathbb{N}$, $1+n = n+1$.

Proof. Let $S=\{n\in\mathbb{N}\mid 1+n=n+1\}$. Then $0\in S$. Suppose that $k\in S$, so that $1+k = k+1 = s(k)$. Then we have: $$1+s(k) = s(1+k) = s(k+1) = s(k+s(0)) = s(s(k+0)) = s(s(k)) = s(k)+1.$$ Thus, $S=\mathbb{N}$. QED

Theorem. For all $n,m\in\mathbb{N}$, $n+m=m+n$.

Proof. Fix $m$, and let $S=\{n\in\mathbb{N}\mid m+n=n+m\}$. First, $0\in S$, since $m+0=0+m$. Also, $1\in S$ by the previous lemma. Now assume that $k\in S$. Then $m+k=k+m$. To show that $s(k)\in S$, we have: \begin{align*} m+s(k) &= s(m+k) = s(k+m) = (k+m)+1 = k+(m+1) = k+(1+m)\\\ &= (k+1)+m = s(k)+m. \end{align*} Thus, $S=\mathbb{N}$. QED

And so on. We can then define multiplication similarly, by fixing $n$ and defining \begin{align*} n\times 0 &= 0\\\ n\times s(m) &= (n\times m) + n, \end{align*} and prove the usual properties of multiplication inductively. Then we can define exponentiation also recursively: fix $n$; then \begin{align*} n^0 & = 1\\\ n^{s(m)} &= n^m\times n. \end{align*} We later define the order among the natural numbers by $$a\leq b\Longleftrightarrow \exists n\in\mathbb{N}(a+n=b),$$ and prove the usual properties.

Later, we can construct $\mathbb{Z}$ from $\mathbb{N}$, $\mathbb{Q}$ from $\mathbb{Z}$, $\mathbb{R}$ from $\mathbb{Q}$, $\mathbb{C}$ from $\mathbb{R}$, etc. See for example my answer to this previous question.

Answer 2

Jacob, there are two ways of defining addition of natural numbers in set theory.

The first is the one you indicate: The sum of two numbers is the size of their disjoint union. In general, you define cardinal addition this way: If $\kappa$ and $\lambda$ are cardinals (sizes of sets), say $\kappa=|A|$ and $\lambda=|B|$, then $\kappa+\lambda=|A\sqcup B|$, where $\sqcup$ denotes disjoint union.

The second way is to define ordinal addition, considering natural numbers as ordered sets: $0=\emptyset$, $1=\{0\}$, $2=\{0,1\}$, etc, with $n=\{0,\dots,n-1\}$ ordered in the usual way, which actually corresponds to membership: $a<b$ iff $a\in b$. Here we identify two linearly ordered sets if they are order isomorphic. The relevant notion here is that of sum of ordered sets: If $(A,<)$ and $(B,\prec)$ are linear orders, their sum $A+B$ is the set $A\sqcup B$ ordered by $a$ is less than $b$ iff $a,b\in A$ and $a<b$, or $a,b\in B$ and $a\prec b$, or $a\in A$ and $b\in B$.

One can check that these two notions coincide when $A$, $B$ are finite sets (i.e., when we look at $n+m$ for $n,m$ finite). One has to be careful, because the notions are different in general for infinite sets. For example, if $\aleph_0=|{\mathbb N}|$, then $\aleph_0+1=1+\aleph_0=\aleph_0$. However, if we think of $\aleph_0$ as the ordered set $\{0<1<\dots\}$, then $1+\aleph_0=\aleph_0$ (remember, we identify sets if they are order isomorphic). However, $\aleph_0+1$ is strictly larger than $\aleph_0$ as ordered sets.

There is a third option in the context of arithmetic: All we need is the notion of successor. The successor of 0 is 1, of 1 is 2, etc. Denote by $S(n)$ the successor of $n$ (in general, $S(n)=n+1$, of course). Note that "successor of $n$" is an order-theoretic notion: The smallest number larger than $n$. Then we define $n+m$ recursively: $n+0=n$, and $n+S(m)=S(n+m)$.

---

We can go on, and define, for example, multiplication and exponentiation in these three ways as well. Cardinal multiplication is the size of the Cartesian product. Cardinal exponentiation $|A|^{|B|}$ is the size of the set of functions from $B$ to $A$.

Ordinal multiplication $\alpha\beta$ means: "$\beta$ copies of $\alpha$". So $\aleph_02=\aleph_0+\aleph_0$ while $2\aleph_0=\aleph_0$.

Ordinal exponentiation is a bit trickier to define: For ordered sets $\alpha,\beta$ such that $\alpha$ has a minimum $0$, define $F(\alpha,\beta)$ as the set consisting of those functions $f:\beta\to\alpha$ such that there are only finitely many $\xi$ such that $f(\xi)\ne0$.

For functions $f,g$ in $F(\alpha,\beta)$ set $f\triangleleft g$ iff $f(\xi)<g(\xi)$ (in the order of $\alpha$) for $\xi$ largest (in the order of $\beta$) such that $f(\xi)\ne g(\xi)$.

Then $\alpha^\beta$ is defined as the order type of $(F(\alpha,\beta),\triangleleft)$.

Again, these notions coincide for finite numbers, but differ wildly for infinite sets.

The recursive definitions are given by $n\cdot 0=0$ and $n\cdot S(m)=nm+n$, and $n^0=1$ (even if $n=0$) and $n^{S(m)}=n^m\cdot n$.

Answer 3

An extremely elegant way of defining numbers I want to mention does not use sets but lambda calculus, i.e. functions and function application. The system used there is called Church encoding.

The idea goes the following: Two, for example, means doing something for two times.

More precisely, when we have some operation (a function) and a value, we apply this function twice on this value. In lambda notation

$$ 2 \equiv \lambda f\,x \mapsto f (f\,x) $$

So generally, any number $n$ is defined as a function that takes another function and returns it's $n$th iterate.

Now we can simply define addition as a function composition. We first apply the function $n$ times, then $m$ times and thus we got a total of $n+m$ applications.

$$ n + m \equiv \lambda f\,x \mapsto n f (m f x)$$

For example, we end up with

$$ 2 + 3 \equiv \lambda f\,x \mapsto f (f (f (f (f\,x)))) \equiv 5 $$