how to construct the addition function in terms of sets

Question

In set theory it is my understanding that all things are sets, for example, a relation can be viewed as a set of ordered pairs and a function is a special type of relation. I have seen how each natural is expressed as a set like so:

0 = {}
1 = 1∪{1}
...
n+1 = n∪{n}

However, how does one construct the addition function as a set? Similarly for multiplication. I have only seen recursive definitions like this here:

a+0=a and a+S(b) = S(a+b)

How does one define the addition function as a set?

Answer 1

(For simplicity I'm going to look just at addition of finite ordinals, i.e. natural numbers; addition of arbitrary ordinals is essentially the same, just more messy.)

This is where the recursion theorem comes in. The recursion theorem gives a way to convert a recursive description like

$$a+0=a, \quad a+S(b)=S(a+b)$$ into a genuine set-theoretic object. In fact, that's literally what it says - that recursive definitions are actually valid.

The recursion theorem is easiest to state for unary functions from $\omega$ to $\omega$:

Suppose $n\in\omega$ and $I:\omega\rightarrow\omega$. Then there is a unique function $f_{I,n}:\omega\rightarrow\omega$ such that $f(0)=n$ and $f(k+1)=I(f(k))$ for all $k\in\omega$.

For example, fixing $a\in\omega$ we can get the "addition-by-$a$" function $add_a$ from this result by setting $n=a$ and $I:x\mapsto S(x)$.

We'll want the binary version of the recursion theorem here; it's more tedious to state and prove, but not substantially different.

---

It may help to be a bit more concrete. Intuitively, the definition of addition we get looks like:

For $a,b,c\in\omega$ we have $a+b=c$ - that is, $\langle a,b,c\rangle\in GRAPH_{addition}$ - iff there is a finite sequence of finite ordinals $$\langle x_1,...,x_n\rangle$$ such that $(1)$ $x_1=a$, $(2)$ for each $i\in\{1,...,n-1\}$ we have $x_{i+1}=S(x_i)$, and $(3)$ $x_n=c$ and $n=b$.

This leans on a rigorous set-theoretic approach to sequences, and that has to be understood first. It is in the same spirit as the implementation of finite sequences in arithmetic.

---

Annoyingly, it's worth noting that there are multiple things called the recursion theorem.

Answer 2

You can construct the addition function as a set $A\subset N^3$ without using the heavy machinery of the recursion theorem as follows.

We start from Peano's Axioms:

1. $0\in N$
2. $\forall a\in N: S(a)\in N$
3. $\forall a, b\in N: [S(a)=S(b) \implies a=b]$
4. $\forall a\in N: S(a)\neq 0$
5. $\forall P\subset N: [0\in P \land \forall a\in P: S(a)\in P \implies P=N]$

Construct $N^3$. Then construct $A\subset N^3$ such that:

$\forall a,b,c: [(a,b,c)\in A \iff (a,b,c)\in N^3 $

$\land [\forall d\subset N^3:[\forall e\in N: (e,0,e)\in d $

$\land \forall e,f,g:[(e,f,g)\in d \implies (e,S(f),S(g))\in d]\implies (a,b,c)\in d]]]$

$A$ is just the "smallest" subset of $N^3$ such that:

• For all $a\in N$, we have $(a,0,a)\in A$

• For all $(a,b,c) \in A$, we also have $(a,S(b),S(c))\in A$

You would then have to prove that $A$ is function, and that it has the required properties.

• $\forall a,b \in N:\exists c\in N:[(a,b,c)\in A \land \forall d\in > N: [(a,b,d)\in A\implies d=c]]$

• $\forall a\in N: (a,0,a)\in A$

• $\forall a,b,c \in N: [(a,b,c)\in A\implies (a,S(b),S(c))\in A]$

A somewhat tedious, but straightforward exercise.

Similarly for multiplication, having constructed the addition function, we can construct $M\subset N^3$ such that:

$\forall a,b,c: [(a,b,c)\in M \iff (a,b,c)\in N^3 $

$\land [\forall d\subset N^3:[\forall e\in N: (e,0,0)\in d $

$\land \forall e,f,g:[(e,f,g)\in d \implies (e,f+1,g+e))\in d]\implies (a,b,c)\in d]]]$

You would then have to prove that $M$ is function, and that it has the required properties.