How to prove that if m and n are natural numbers than m+n is also a natural number?

Question

Problem sounds easy enough - prove that if $m$ is in set of all natural numbers (let's call it $\mathbb N$) and so is $n$ than $m+n$ also must be there. Probably it should be done using induction. But how to do it formally? I mean I could tell that $\mathbb N$ is a set $\{1, 1+1, 1+1+1, \dotso\}$ and $m$ is $m$ ones and $n$ is $n$ ones so $m+n$ is $m+n$ ones so it's still in $\mathbf N$ but I doubt that my professor would accept such a proof. It's so intuitive that I don't even know where to start. What should I do?

Answer 1

If you are using Peano axioms, induct on $n$ with $m$ fixed.

Note: $n^+$ is the sucessor of $n$.

Axiom 1. $0 \in \mathbf N$.

Axiom 2. if $n \in \mathbf N$ then $n^+ \in \mathbf N$.

Definition 3 (Adition). $m + 0 := m$ and $m + n^+ := (m + n)^+$.

Proof. Induct on $n$ (keeping $m$ fixed). Consider the case base $n = 0$. Since by hypothesis we have $m \in \mathbf N$, then $m + 0 = m \in \mathbf N$ by Definition 3. Now suppose inductively that $m + n \in \mathbf N$; we now have to show that $m + n^+ \in \mathbf N$. By Definition 3, we have $m + n^+ = (m + n)^+$. By Axiom 2, since $m + n \in \mathbf N$, we conclude $(m + n )^+ = m + n^+ \in \mathbf N$. Thus $m + n \in \mathbf N$ for every $m, n \in \mathbf N$. This close the induction.

Answer 2

There are different versions of the Peano's Axioms. The most commonly used version (with 5 axioms) does not define any add or multiplication function. You must construct these functions using the axioms of set theory. You can prove there exists a unique + function such that

$\forall a,b \in N:a+b\in N$

$\forall a \in N:a+0=a$

$\forall a,b \in N:[a+S(b)=S(a+b)]$

where $S:N\to N$ is the usual successor function defined in the axioms.

A first-order version (with 9+ axioms) gives you this theorem as an initial definition.