How to perform arithmetic (4-functions) on Von Neumann numbers?

Question

Using the Von Neumann representation of the non-negative integers, where the empty set corresponds to zero, and the successor function is defined as the function on a set that returns the union of the set with the set that contains the set, how do you define addition, subtraction, multiplication, and division?

Answer 1

Addition and multiplication are defined by recursion: if by $S(n)$ we denote successor of $n$, then:

$$a+0=a,a+S(b)=S(a+b)$$ $$a\cdot 0=0,a\cdot S(b)=a\cdot b+a$$

Note that in definition of multiplication we use earlier defined addition.

For subtraction, we define $a-b$ as a unique $c$ such that $a=c+b$ (if one exists). For division, $a/b$ is a unique $d$ such that $a=d\cdot b$.

It's worth noting that in terms of von Neumann natural numbers some subtractions and divisions are undefined, like $1-2,2/5,0/0$ (the last one because we require $d$ to be unique).

Answer 2

There are two main approaches.

In the first one, you start by proving that $\omega$ satisfies the (second order) Peano axioms, which allows you to prove that primitive recursive function definitions work. Then you can define addition and multiplication by the standard recursion equations from Peano Arithmetic:

$$ \begin{align} a+0 &= a \\ a+(b^+) &= (a+b)^+ \\ a\cdot 0 &= 0 \\ a\cdot(b^+) &= (a\cdot b)+a \end{align} $$

(Later on these definitions can be extended to full ordinal addition and multiplication by adding cases for limit ordinals).

The second approach is to develop a general theory of ordinals and well-orders, and then define ordinal arithmetic in general by saying:

$\alpha+\beta$ is the order type of $(\{0\}\times\alpha) \cup (\{1\}\times\beta)$ with the lexicographical order.

$\alpha\cdot\beta$ is the order type of $\beta\times\alpha$ with the lexicographical order.

(where $\times$ is the set-theoretic Cartesian products in both definitions).

You would then need to prove that these operations are closed on the finite ordinals -- that is, if $\alpha$ and $\beta$ are finite, then the lexicographical orders of the definitions are order isomorphic to a finite ordinal. That is not terribly difficult, however: both operations preserve the property that every element of the well-order is either the initial one or has an immediate predecessor, which one can show is equivalent to being finite.

In either case you would go on to define subtraction and division as the (partial) inverse operations to addition and multiplication.

Answer 3

Another approach that has not been mentioned is to use cardinality. Given a set $S$ and a von Neumann natural number $n$, we say that $S$ has cardinality $n$ iff there is a bijection between $S$ and $n$. You can prove that for any $S$, there is at most one $n$ such that $S$ has cardinality $n$; if such an $n$ exists, we say $S$ is finite. You can then prove that a union or cartesian product of two finite sets is finite. Finally, you can defined the sum $m+n$ as the cardinality of the set $m\times\{0\}\cup n\times\{1\}$ (i.e., a union of copies of $m$ and $n$ modified so that they are disjoint sets) and the product $m\cdot n$ as the cardinality of the set $m\times n$.

As the other answers have mentioned, subtraction and division are not always defined, but when they are defined they can be defined in terms of addition and multiplication.