how to construct the addition function in terms of sets 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?
(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.
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:

$0\in N$
$\forall a\in N: S(a)\in N$
$\forall a, b\in N: [S(a)=S(b) \implies a=b]$
$\forall a\in N: S(a)\neq 0$
$\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 &quot;smallest&quot; 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
   &gt;     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.