How do you formally define the addition algorithm for the natural numbers and then prove it?

Question

I am interested in knowing what a set theoretic definition of the standard addition algorithm for the natural numbers would be. Second, how do we know the standard algorithm gives the correct sum? Is there a gold standard for addition that we could compare it to?

It seems if you have two disjoint sets and you want to add the elements of one set to the other, you would just add one element to the receiving set and subtract one from the giving set and repeat this until the giving set is empty. Then you would just count the number of elements in the receiving set and that would be the sum. To me this would be the gold standard, but I’m not sure.

If you forget everything you know about addition and try to create a faster method of adding than the procedure above, the standard algorithm doesn’t seem very obvious to me.

Lastly, are there any writings about this topic that someone could direct me to? This is so basic and uninteresting to most people that I couldn’t find much on the topic.

I have seen one answer on here that defines the algorithm and proves it, but it was so hard to follow and I don’t think it was compared to any gold standard to make sure we get the correct answer.

I really need it dumbed down for me. It’s been awhile since I have been in school. Thank you.

Answer 1

If you accept the addition of 1-digit numbers, then you can prove how to add any-digit numbers using the "long addition" algorithm from school. The proof comes from a couple of basic facts.

The first is a definition of place-value numbering. What do I mean when I write the number $1234$? Well, in school I was taught that this means "1 thousand plus 2 hundreds plus 3 tens plus 4 ones". In a formula, that is

$$1234 = 1\times 1000 + 2 \times 100 + 3 \times 10 + 4 \times 1$$

Suppose I want to add this to the number $4321$. In full,

$$4321 = 4\times 1000 + 3 \times 100 + 2 \times 10 + 1 \times 1$$

How many thousands do I have? Well, $1+4=5$. How many hundreds? Also $5$. And $5$ tens and $5$ ones. So the answer is $5555$.

This is the essence of the proof when you don't have to do any carrying. It relies on the following facts, which can be justified from first principles.

• Every number has a place-value representation.
• Addition commutes (specifically in the following form): $$(x_1 + x_2 + \ldots + x_n) + (y_1 + y_2 + \ldots y_n) = (x_1+y_1) + (x_2 + y_2) + \ldots (x_n + y_n)$$
• Addition distributes over multiplication (so that we can say $4 \times 1000 + 1 \times 1000 = (4+1) \times 1000$).

The justification for carrying is essentially the following: $7+9 = 10+6$, so if we are in the $k$ position, we rely on the identity

$$(9+7)\times 10^{k} = (10+6)\times 10^k = 1\times 10^{k+1} + 6 \times 10^k$$ which we call "carrying the 1 to the $k+1$ position". Obviously 9 and 7 in this example can be replaced by any two digits which add to a 2-digit number.

Is this the sort of thing you're looking for? It's possible to give many more details, but it helps to know exactly which parts you want to see in more detail, and what basic justification you would be happy with.

Defining addition

You ask what a "gold standard" definition of addition might be. I interpret your attempted definition in the following way:

Let $m$, $n$ be two natural numbers. Interpret $m$ and $n$ as the cardinality (size) of two disjoint sets of objects, $X$ and $Y$. Remove one object from $Y$ and insert it into $X$. Repeat until $Y$ is empty. Count how many objects are in $X$. This is $m+n$.

That is a perfectly correct definition of $m+n$. Its correctness relies on two properties of natural numbers.

• $m+n = (m+1) + (n-1)$.
• The sequence $n, n-1, n-2, \ldots$ terminates with $0$ (or $1$, depending on whether you consider $0$ to be a natural number).

If you accept those properties, then you have an algorithm. If you don't, you have to go deeper.

Commutativity of addition

It is not obvious from the definition that the familiar fact $n+m = m+n$ is true for all natural numbers $m,n$. It is hopefully obvious when $m=0$. To prove it requires an argument by induction (which will be implicit throughout this answer). There is a good explanation on this answer.

Defining place-value notation

Place-value representation is the key to getting a fast algorithm for adding natural numbers. The definition in terms of "counting objects" does not make it obvious how to represent a given natural number. The only representation it suggests is some kind of tally, where the number we call 5 would be "11111" and 9 would be "111111111".

The idea of place-value representation is to represent a given natural number by a finite string of digits, where the position of the digits is significant. The first ten numbers are given the representations $0, 1, 2, 3, 4, 5, 6, 7, 8, 9$. We define the place-value representation of an arbitrary number by induction, as follows.

Take an arbitrary number $n$ which we already know how to write in the place-value system. Say it has $k$ digits, and label the digits $a_k a_{k-1} \ldots a_{1}$ from left to right. I want to explain how to find the place-value representation of $n+1$.

• If $a_1$ is not $9$, then replace $a_1$ by $a_1+1$ (which is also a digit).
• If $a_1=9$ but $a_2 \ne 9$, replace $a_1$ by $0$ and $a_2$ by $a_2+1$.
• If there exists a number $\ell$, less than $k$, $a_1, a_2, \ldots, a_{\ell-1}$ are all $9$, but $a_\ell \ne 9$, then replace all of $a_1, a_2 \ldots a_{\ell - 1}$ by $0$, and replace $a_\ell$ by $a_\ell + 1$.
• It there is no such $\ell$, then every digit of $n$ is $9$. We say $n+1$ has the representation $10\ldots 000$ (with $k$ zeroes).

It can be proved that the representation is unique.

A different characterisation of place value notation

I want to prove the following theorem (notice the slight change in notation to include $a_0$).

$$a_k a_{k-1} a_{k-2} \ldots a_{0} = \sum_{i=0}^{k} 10^{i} \times a_{i}$$

Obviously even the statement of this theorem requires some notion of multiplication. So let's cover that...

Definition of multiplication

In the same way that $n+m = (n+1) + (m-1)$ gives us a definition of addition, the following gives us a definition of multiplication.

$$n\times m = (n+n) \times (m-1) $$

If you apply this repeatedly $m$ times, then you end up with a natural number which we call $n \times m$.

Commutativity of multiplication

As with addition, this is a standard exercise in induction. There is another answer on this site with a reasonable explanation.

This means we can interpret $m \times n$ either as "$m$ added to itself $n$ times", or "$n$ added to itself $m$ times".

Multiplication distributes over addition

It is another familiar fact that $a \times (b+c) = a \times b + a \times c$. Again, this is a standard exercise (Note that where they say $S(a)$, we would just say $a+1$. They're the same thing.)

Multiplication by 10 and place value

The theorem I said before is now not that hard to prove. Take your number $n = a_{k} a_{k-1} \ldots a_{1} a_{0}$. Then we have

\begin{align*} n &= a_{0} + a_{1}0 + a_{2}00 + a_{3}000 + \ldots \end{align*}

Now $a_{0} = (1+1+ \ldots +1)$ (where there are $a_{0}$ ones) by definition.

It is hopefully intuitive that $a_{1}0 = (10 + 10 + \ldots + 10)$. You can prove it by checking the cases $a_{1} = 1,2,3, \ldots 9$ separately.

Similarly for $a_{2}00 = a_{2} \times 100$, and so on. This can be made precise by induction. Hence, we have

$$n = a_{0} \times 1 + a_{1} \times 10 + a_{2} \times 100 + \ldots = \sum_{i=0} a_{i} \times 10^{i}$$

Answer 2

Your procedure for "adding" two numbers is a fine algorithm if implemented correctly, however, it does not constitute a true additive function $\omega\times\omega\to\omega$ without making your procedure more precise.

The following theorem is hopefully an easily accessible proof of the existence and uniqueness of the addition function on the natural numbers.

Some Preliminaries:

Definition: $\omega$ is the set of natural numbers, defined to be the smallest inductive set (see the axiom of infinity or any intro to set theory article for more on how to construct $\omega$).

Definition: A relation $f\subseteq X\times Y$ is a function from $X$ to $Y$ provided that $\forall x\in X\exists!y\in Y:(x,y)\in f$. The unique $y$ corresponding to each $x$ is denoted $f(x)$.

Successor Function: There exists a function $s:\omega\to\omega$. Take $s=\{(x,y)\in\omega\times\omega:y = x\cup\{x\}\}$ and show that this is indeed a function with $s(x)=x\cup \{x\}$ (this encapsulates the idea of adding one to $x$).

I assume you have knowledge of the principle of induction and how to follow an inductive proof.

Theorem: There exists a unique function $+:\omega\times\omega\to\omega$ satisfying $$\forall x\in\omega:x+0 = x\tag{i}$$ $$\text{ and }$$ $$\forall x,y\in\omega:x+s(y) = s(x+y)\tag{ii}$$

Proof: Call a subset $A$ of $\omega^3$ additive if $$\forall x\in\omega:(x,0,x)\in A\tag{a}$$ $$\text{and}$$ $$\forall x,y,z\in\omega:(x,y,z)\in A\implies (x,s(y),s(z))\in A\tag{b}$$

Note that this definition is not so restrictive that no subset of $\omega^3$ satifies these conditions, since trivially, $\omega^3$ is additive.

Set $$\mathcal{A}=\{A\in\mathcal{P}(\omega^3):A\text{ is additive }\}$$ and define $+=\bigcap\mathcal{A}$. Our current goal is to show that $+$ is additive (that is, $+$ satisfies (a) and (b)) and that $+$ is a function.

(a) For $x\in\omega$, $(x,0,x)\in A$ for all $A\in\mathcal{A}$ hence $(x,0,x)\in +$.

(b) For $x,y,z\in\omega$, if $(x,y,z)\in +$, then $(x,y,z)\in A$ for all $A\in\mathcal{A}$, hence $(x,s(y),s(z))\in A$ for all $A\in\mathcal{A}$, thus $(x,s(y),s(z))\in+$.

Since $+$ satisfies (a) and (b), then $+$ is additive and is the smallest additive subset of $\omega^3$.

We now show that $+$ is a function via induction. Fix $x\in\omega$ and define $$N_x=\{y\in\omega:\exists!z\in\omega:(x,y,z)\in +\}$$ I leave it to you to show that $0\in N_x$. Now suppose that $y\in N_x$ for some $y\in\omega$. Then there exists a unique $z\in\omega$ such that $(x,y,z)\in+$. As $+$ is additive, then $(x,s(y),s(z))\in+$. If $z'\in\omega$ satisfies $(x,s(y),z')\in +$, then $+\setminus\{(x,s(y),z')\}$ is an additive subset, contradicting minimality of $+$, hence $s(y)\in N_x$. This completes the induction.

It now follows that for all $(x,y)\in\omega\times\omega\exists!z\in\omega:(x,y,z)\in+$, that is, $+$ is a function from $\omega\times\omega$ to $\omega$.

It is clear that $+$ is unique since any other function satisfying (i) and (ii) must be an additive subset of $\omega^3$. You may also check that $+$ indeed satisfies (i) and (ii). $\square$

Properties (i) and (ii) uniquely characterize addition on the natural numbers in the way we are all familiar with, and we have simply constructed a function from the ground up which satisfies the characteristic properties of addition on the natural numbers. This gives you an algorithm to add any two natural numbers based in standard set theory by recursively applying the successor function and the relations $+$ satisfies .