Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
3  
A nitpick: In the set-theoretic construction of natural numbers, 0, 1, 2, and so on are not defined as the cardinalities of the sets you mentioned, but as the sets themselves. I don't think disjoint union will work in this case, as you may end up with a set that does not represent a number. –  Rahul Dec 30 '10 at 0:58
    
Ah, okay. My logic professor mentioned it to me once in passing and I never read it on my own. I meant to add something about whether or not I was correct in remembering the construction. –  JSchlather Dec 30 '10 at 3:11

3 Answers 3

up vote 18 down vote accepted

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.

share|improve this answer
3  
Arturo, one does not need the axiom of infinity to define the natural numbers, or their operations (of course, one cannot then ensure the existence of ${\mathbb N}$, but it and addition can be defined as classes). In fact, one can show that the theory resulting from taking ZFC and replacing the axiom of infinity with its negation (stated as "there are no limit ordinals") is bi-interpretable with PA (i.e., it is precisely the axiom of infinity what separates set theory from first order arithmetic). –  Andres Caicedo Dec 30 '10 at 2:26
    
@Andres: Thanks for the information. –  Arturo Magidin Dec 30 '10 at 3:15
    
Ah, okay makes sense. –  JSchlather Dec 30 '10 at 3:19
    
@Andres: Without the axiom of infinity can't you still talk about the natural numbers as a definable class? –  Asaf Karagila Dec 30 '10 at 5:55
    
@Asaf: Yes, of course. But existence means that there is a set. –  Andres Caicedo Dec 30 '10 at 5:58

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$.

share|improve this answer
    
(To formalize some of the above we either talk about "order types", identifying sets that have the same order, as I did or, more commonly once one introduces the notion of well-ordering, we pick canonical representatives of each well-ordering, the ordinals, and work with them rather than order types.) –  Andres Caicedo Dec 30 '10 at 1:09
    
Also good to know. –  JSchlather Dec 30 '10 at 3:19

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 $$

share|improve this answer
    
I cannot not +1 when I see lambda calculus and λ. Church encoding is beautiful. –  Kazark Mar 13 '12 at 15:24

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.