How is addition defined?
Solution 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":
- $\emptyset \in\mathbb{N}$.
- If $x\in\mathbb{N}$, then $s(x) \in\mathbb{N}$.
- For all $x\in\mathbb{N}$, $s(x)\neq\emptyset$.
- For all $x,y\in\mathbb{N}$, if $s(x)=s(y)$, then $x=y$.
- 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:
- $0$ is a natural number.
- If $n$ is a natural number, then $s(n)$ is a natural number.
- For all natural numbers $n$, $s(n)\neq 0$.
- For all natural numbers $n$ and $m$, if $s(n)=s(m)$, then $n=m$.
- 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.
Solution 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$.
Solution 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 $$