How do we define addition?

Question

I've been trying to learn naive set theory through a YouTube series by 'The Bright Side of Mathematics'. So far, I've been able to understand successor maps and the definition of $\mathbb{N}_{0}$. I have now gotten to the point where he defines addition. His definition is the following:

$$\text{Addition is a map } \mathbb{N}_{0} \times \mathbb{N}_{0} \rightarrow \mathbb{N}_{0}$$ $$(m,n) \mapsto m + n$$ He also gives the following: $$m+0:=m$$ $$m + s(n) := s(m+n)$$

I am able to understand how he gets these statements, as he works through it quite well on the video. However, to me this seems like circular reasoning. How can you define addition using the $+$ symbol, isn't that against the purpose of a definition?

Whilst doing further research I managed to find the following article: How is addition defined?. The answers on it however don't make much sense to me as a complete beginner, and I am wondering whether anyone has a definition of addition without using $+$ (or if that's even possible)?

Answer 1

The apparent circularity in this definition is in fact illusory. It is possible to prove that there exists a unique function $f:\mathbb N\times\mathbb N\to \mathbb N$ such that \begin{align} f(m,0) &= m \, , \tag{1}\label{1}\\ f(m,s(n)) &= s(f(m,n)) \, , \tag{2}\label{2} \end{align} for all $m,n\in\mathbb N$. Once we have established this fact, it makes perfect sense to define $+$ as this unique function. This is in the same way that it makes sense to define $e^x$ as the solution to the initial value problem $y'=y,\, y(0)=1$, provided we know that (a) such a solution exists, and (b) it is unique.

So how can we prove the existence and uniqueness of $f$? Since the theorem in question is so fundamental, the answer is sensitive to the foundational system you are using. If you are working in a set theory environment, then you would typically appeal to the following.

Recursion theorem. If $a$ is an element of a set $X$, and $g:X\to X$ is a function, then there exists a unique function $u:\mathbb N\to X$ such that $u(0)=a$ and $u(s(n)) =g(u(n))$ for all $n\in\mathbb N$.

A proof of the recursion theorem can be found in Halmos's book Naive Set Theory (sec. 12, p.48), and in a number of other books on mathematical logic and set theory. Almost all of the work involved in the proof goes into actually constructing the function $u$; the uniqueness assertion is just a routine induction.

Once we have the recursion theorem in hand, we can proceed as follows. For each $m\in\mathbb N$, we let $s_m:\mathbb N\to\mathbb N$ be the unique function satisfying $s_m(0)=m$ and $s_m(s(n))=s(s_m(n))$ for all $n\in\mathbb N$. Then, we define $f:\mathbb N\times\mathbb N\to\mathbb N$ by $f(m,n)=s_m(n)$. It is clear that $f$ satisfies $\eqref{1}$ and $\eqref{2}$, and an induction on $n$ shows that there is at most one function with this property. Thus, our definition of $+$ is coherent.

Answer 2

The $+$ symbol is an "infix" function definition $+: \mathbb{N}_0 \times \mathbb{N}_0 \to \mathbb{N}_0$. The only difference to a normal function is, that for $m,n \in \mathbb{N}_0$ instead of writing $+(m,n)$ we write $m + n$ (infix notation). Note that you can use any symbol other than $+$ for example just call it $\mathrm{ADD}$. Furthermore you do not need to use the infix notation.

The definition is recursive in nature. Let $m \in \mathbb{N}_0$. Say we want to calculate $m + s (0)$. Then by the definition $$ m + s(0) =s( m+ 0) = s (m). $$ In the same way (using the above equation for the second equality): $$ m+ s(s(0)) = s (m + s(0) ) = s( s(m))$$ It is not hard to understand that we can calculate $m+n$ in this way for any $n \in \mathbb{N}_0$ simply by expressing it as the $n$-th succesor of $0$. Therefore the recursively defined function $+$ is well defined.

Answer 3

We can define it in a similar way to how we define $\mathbb{N}_0$—as the smallest set having certain properties. Let \begin{align} \varphi(u) &= (\forall x \in \mathbb{N}_0) (x, 0, x) \in u\\ &\quad \wedge (\forall xyz \in \mathbb{N}_0)((x, y, z) \in u \to (x, s(y), s(z)) \in u), \end{align} and let $\delta(y) = \varphi(y) \wedge \forall z (\varphi(z) \to y \subseteq z)$. We can then use the axioms of set theory to prove $\exists! y \, \delta(y)$, which justifies defining the symbol $+$ by $y = {+} \leftrightarrow \delta(y)$. We then adopt the shorthand, $x + y = z$ to mean $(x, y, z) \in {+}$.

In words, the above definition says that $+$ is the smallest set of ordered triples of natural numbers such that $(x, 0, x) \in {+}$ for every natural number $x$, and, whenever $(x, y, z) \in {+}$, we also have $(x, s(y), s(z)) \in {+}$.

Using the shorthand notation, the verbal description is even clearer. In that case, $+$ is the smallest set of ordered triples of natural numbers such that $x + 0 = x$ for every natural number $x$, and, whenever $x + y = z$, we also have $x + s(y) = s(z)$.

Answer 4

This is a recursive definition (closely related to proofs by induction).

To be well-defined, it requires two parts: a base case ($m + 0 := m$) and a recursive case ($m + s(n) := s(m + n)$). If we only had the recursive case, then this would indeed be a circular definition. But the presence of the base case provides a "stopping point", to which any application will ultimately resolve. Note that the base case has no $+$ operator in the defining right-hand expression.

Taking the simplest possible example, consider applying this to $1 + 1$. Knowing the definitions of $s(0)= 1$ and $s(1) = 2$, we see: $1 + 1 = 1 + s(0) = s(1 + 0) = s(1) = 2$. Note that we applied the base case in the first step, recursive in the second, and base case again the third.

Other applications would be longer chains of reasoning, but would involve recursively decomposing the addend in a similar way, with the decomposition stopping once all the units are expressed in terms of $s(0)$, and then recursively recombining. Note that this effectively formalizes the childhood strategy of addition by "counting on".

Answer 5

The other answers are not technically wrong but are in fact conceptually quite misleading when it comes to foundations of mathematics. The reason is that if you do not already have a model of PA⁻ (discrete ordered semi-ring axioms), and claim to be able to construct such a model, such as starting from some structure $N$ with an element $0$ and an injective successor function $s$ on $N$ whose output is never $0$, then you must be working in some sufficiently strong foundational system already. If for example you are working in ZFC set theory, then you would get such an initial structure $⟨N,0,s⟩$ from the Infinity axiom and Specification axiom (schema). In particular, much of the power is hiding in the Infinity axiom; it was added entirely to ensure that we could construct such an initial structure.

And that is actually a big problem from a careful philosophical viewpoint. Note that the Infinity axiom literally says (by fiat) that there exists a set $I$ that includes $∅$ and is closed under $s$ where $s(x) = x∪\{x\}$ for every (set) $x$. We can conceptually imagine this set $I$ as long as we accept that we can indefinitely iterate this operation $s$ and collect together all the results we get. This is not an issue if we accept that we can concatenate arbitrary finite strings (say from a finite alphabet) indefinitely, starting from single-symbol strings. But there does not seem to be any other way of justifying such a conceptual construction! And it turns out that the very idea that there is a set of finite strings that includes "0" and "1" and is closed under concatenation already yields a model of PA⁻ under very weak assumptions.

So it is conceptually circular to define natural number addition using recursion, because the recursion theorem itself cannot be justified without relying on assumptions stronger than merely assuming that ℕ obeys PA⁻. ZFC proves the recursion theorem, of course, but it would not be wrong to say that we would be extremely unlikely to accept any foundational system (whether ZFC or not) that is not capable of constructing a model of PA⁻. In other words, addition on ℕ is a requirement and we would design our foundational system in order to be able to obtain that. Same for multiplication on ℕ.

Even in the field of mathematical logic, PA⁻ has a much more special place than Peano's axioms (without addition and multiplication), and is considered to be the most suitable base theory for many investigations into weak foundations of mathematics. There is a weaker base theory called Robinson's Q, but even Q has both addition and multiplication inbuilt! I hope that the above explanation has given you some insight into why addition and multiplication are more like fundamental assumptions that we must have than concepts that we can define in absence of equally strong assumptions.