1
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ First you need the definition of addition and multiplication. Then prove by induction for any fixed $m\in\mathbb{N}$ that $\{n\in\mathbb{N} : n+m \in\mathbb{N}\} = \mathbb{N}$ (and similarly for the product). $\endgroup$ – Daniel Fischer Oct 9 '14 at 13:33
  • $\begingroup$ Hi Daniel, can you verify this proof? Proof: Let there be $m \in \mathbb{N}$. We will define the set I={$n \in \mathbb{N} | n+m \in \mathbb{N}$ } So we want to prove that $ I = \mathbb{N}$ , from the definition of I we derive $I \subset \mathbb{N}$ so we have to prove that $\mathbb{N} \subset I $ . We will prove this with induction. Basis for the induction: n=1 . Since $m \in \mathbb{N}$ and $\mathbb{N}$ is inductive, $m+1 \in \mathbb{N}$ and therefore $1 \in I$. Induction Hyp:$n \in I$ , we will prove that $n+1 \in I$ Induct Step: If $n \in I$ then $n+m \in \mathbb{N}$ since $\mathbb{N}$ is $\endgroup$ – Charles Carmichael Oct 9 '14 at 13:57
  • $\begingroup$ inductive $n+m+1 \in \mathbb{N}$ therefore $n+1 \in I$ and therefore $I=\mathbb{N}$, as desired. Is this correct? Thank you. $\endgroup$ – Charles Carmichael Oct 9 '14 at 14:01
  • $\begingroup$ @DavidC You need to tag him, otherwise he won't get the notification of your comment. $\endgroup$ – Vincenzo Oliva Oct 11 '14 at 9:24
  • 1
    $\begingroup$ I have added (set-theory) tag, since the question is about set-theoretical definition of natural numbers (as the smallest inductive set) based on Axiom of Infinity. $\endgroup$ – Martin Sleziak Feb 1 '15 at 11:40
0
$\begingroup$

How are sum/product operations in $\mathbb{N}$ defined in your context?

Let $n,m\in\mathbb{N}$.

Write $s(n)=n\cup \{n\}$. Observe $s(n)\in\mathbb{N}$ by definition of inductive set, and recall $$m\neq 0 \implies \ \exists l\in\mathbb{N} \big(m=s(l)\big).$$

Both addition and multiplication are binary operations in $\mathbb{N}$ defined recursively as follows:

Addition (or "sum"):

  • If $m=0$, then $n+ m := m$
  • If $m\neq 0$, then $n+ m := s(n+l)$

Multiplication (or "product"):

  • If $m=0$, then $n\cdot m = 0$
  • If $m\neq 0$, then $n\cdot m = n\cdot l + n$

Thus, by this definition and using induction, the result of both sum and product are also natural numbers.

$\endgroup$
0
$\begingroup$

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$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.