3
$\begingroup$

I'm re-learning real analysis and decided to start from Tao's books (sorry Rudin) and Tao left a remark stating we can prove the sum of two natural numbers is again a natural number by the Peano Axioms; specifically we only need these components:

Axiom 2.1 $0$ is a natural number.

Axiom 2.2 If $n$ is a natural number, then $n++$ is also a natural number.

Definition 2.1.3. We define $1$ to be the number $0++$, $\,2$ to be the number $(0++)++$, and so on.

Axiom 2.5 (Principle of mathematical induction) Let $P(n)$ be any property pertaining to a natural number $n$. Suppose the $P(0)$ is true, and suppose that whenever $P(n)$ is true, $P(n++)$ is also true. Then $P(n)$ is true for every natural number n.

Definition 2.2.1 (Addition of natural numbers). Let $m$ be a natural number. To add zero to $m$ , we define $0+m:=m$. Now suppose inductively that we have defined how to add $n$ to $m$. Then we can add $n++$ to $m$ by defining $(n++)+m:=(n+m)++$.


Proof.

Let $n$ and $m$ be natural numbers.

This will be a proof by mathematical induction; we shall induct on the variable $n$, with the base case $n=0$. Since $m$ is a natural number by the hypothesis, our only cases are either $n =0$ and $m=0$ $or$ $n=0$ and $m\neq 0$. Suppose first that $n=0$ and $m=0$. Then $n+m = 0+0 = 0$. We know $0$ is a natural number by Axiom 2.1. Now suppose $n=0$ and $m \neq 0$. By Definition 2.2.1, the sum $n+m =0+m=m$. We know $m$ is a natural number by the hypothesis. Since we get natural numbers in both base cases, we have have proved the base case.

Now suppose we have shown inductively that the sum $n+m$ is a natural number. We need to show $(n++)+m$ is also a natural number.

By Definition 2.2.1, $(n++)+m = (n+m)++$, and since $n+m$ is a natural number by the inductive hypothesis, $(n+m)++ = (n++)+m$ is also a natural number by Axiom 2.2. Thus, $n+m$ must be a natural number by the principle of mathematical induction, closing the induction.


Proof complete, with the help of ultralegend5385 and Rob Arthan.

$\endgroup$
3
  • 2
    $\begingroup$ Your proof looks good to me. Stylistically, it would be better if you made the distinction between the two parts of the inductive proof clearer (Base case: ... Inductive step: ...). $\endgroup$
    – Rob Arthan
    Jul 14, 2021 at 1:07
  • $\begingroup$ thank you for the proof. I am not sure why it is necessary to split the base case ($n=0$) into two sub-cases: (i) $m=0$ or (ii) $m\neq 0$. For the base case, my argument is simply that $0+m:=m$ (by Definition 2.2.1.) and $m$ is a natural number by assumption. But then I am not sure where to use Axiom 2.1 in the proof. To my understanding, $m$ can be $0$ in Definition 2.2.1. Thank you for your help! $\endgroup$
    – Sean
    Nov 4, 2023 at 16:20
  • $\begingroup$ @Sean you are correct - we do not need to split the base case if we just keep $m$ fixed and induct on $n$, and we do not need Axiom 2.1. $\endgroup$
    – Paul Ash
    Dec 4, 2023 at 6:44

1 Answer 1

1
$\begingroup$

You have written a good proof, although as @RobArthan said in comments, you must highlight the parts of your induction, and also saying explicitly that you are using induction on $n$, which is unclear as of now. Some suggestions for lines:

[We will use induction on $n$ to show this]

[For the base case, when $n=0$,]

[We assume, for the sake of induction that]

It is always better to define a statement $P(n)$ for induction proofs, but it is your choice after all.

Another important thing, your proof never showed that $0+0$ is a natural number. Think about that and edit it accordingly.

Hope this helps. Ask anything if not clear :)

$\endgroup$
1
  • 2
    $\begingroup$ Thank you for your response. I was working all week...haven't had time to come back here. I edited the proof based on your feedback. Much appreciated. $\endgroup$
    – Paul Ash
    Jul 22, 2021 at 0:49

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .