I wanted to prove that the sum and the product of two natural numbers is a natural number. Intuitively it's clear to my why that is true, however I couldn't prove it.
So our lecturer first defined what an inductive set is. Then he defined the Natural numbers as the intersection of all inductive sets. Then we proved the induction principle and $\forall n \in \mathbb{N} , 1\leq n$ .
So this is the information we have so far. But I am having difficulty proving that the sum/product of two natural numbers is a natural number. Can someone give me a clue how to prove this?
I am trying to prove this with the definition of a Natural numbers, but it's not working so far…
Thank you.
Best Answer
I'm going to do something I rarely do, namely defining $\Bbb N$ to include $0$ as an element. It makes the treatment herein a little easier or at least a little more Peano-conventional; feel free to adjust it, as an exercise, to start $\Bbb N$ at $1$.
From $$0\in\Bbb N,\,\forall n\in\Bbb N (Sn\in\Bbb N),\,a+0=a,\,a+Sb=S(a+b),\,a\times 0=a,\,a\times Sb=a\times b+a$$and $$\varphi(0)\land\forall n(\varphi(n)\to\varphi(n+1))\to\forall n\in\Bbb N(\varphi(n))$$we'll prove $\forall a,\,b\in\Bbb N(a+b\in\Bbb N)$, and as a separate theorem $\forall a,\,b\in\Bbb N(a\times b\in\Bbb N)$. For both proofs we'll induct on $b$.
First, addition. The case $b=0$ is trivial because $a+0=a\in\Bbb N$. Now we just need the inductive step; if it works when $b=k$ then $a+k\in\Bbb N\implies a+Sk=S(a+k)\in\Bbb N$.
Next, multiplication; the addition result is actually needed in the inductive step. Again, $b=0$ is trivial because $a\times 0=0\in\Bbb N$. Now the inductive step, assuming $a\times k$ exists; then $a\times Sk=(a\times k)+a$ is the sum of two elements of $\Bbb N$, completing the proof by the above result.
You may also wish as an exercise to use this result about multiplication to in turn prove $a^b\in\Bbb N$ using $a^0=1,\,a^{Sb}=a^b\times a$.