2

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.

Asaf Karagila
  • 393,674
Charles Carmichael
  • 595
  • 1
    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). – Daniel Fischer Oct 09 '14 at 13:33
  • 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 – Charles Carmichael Oct 09 '14 at 13:57
  • inductive $n+m+1 \in \mathbb{N}$ therefore $n+1 \in I$ and therefore $I=\mathbb{N}$, as desired. Is this correct? Thank you. – Charles Carmichael Oct 09 '14 at 14:01
  • @DavidC You need to tag him, otherwise he won't get the notification of your comment. – Vincenzo Oliva Oct 11 '14 at 09:24
  • @DanielFischer I've done it for you, David. Afterall, I can't verify your proof now (also because I'm not that practical) – Vincenzo Oliva Oct 11 '14 at 09:27
  • 1
    I have added ([tag:set-theory]) tag, since the question is about set-theoretical definition of natural numbers (as the smallest inductive set) based on Axiom of Infinity. – Martin Sleziak Feb 01 '15 at 11:40
  • @Martin: I've seen $\Bbb N$ defined in analysis as the smallest inductive set of $\Bbb R$. Seeing how $0$ is not a natural number here, I am very suspicious that your edit was truly in place. – Asaf Karagila Jan 09 '19 at 11:10
  • (But maybe four years later Charles can clarify what was the meaning here.) – Asaf Karagila Jan 09 '19 at 11:10
  • @AsafKaragila Fair point, I have no problem with retagged in some way. In any case, perhaps we can move further discussion elsewhere - so as not to leave here too many comments that are actually unrelated to the question. – Martin Sleziak Jan 09 '19 at 11:46
  • @Martin: First let's hear it from the OP. – Asaf Karagila Jan 09 '19 at 11:46
  • You state that "we proved the induction principle and $\forall n \in \mathbb{N} , 1\leq n$". Usually the crux of the matter is to show that two binary operations, satisfying some conditions, can be defined (uniquely) on $\mathbb{N} \times \mathbb{N}$. Also, when you say that $\mathbb{N}$ is an inductive set, the reference points is, 'yup, Peano stuff', with the expectation that $0 \in \mathbb{N}$. – CopyPasteIt Mar 17 '19 at 10:16
  • So once you have your binary operations, the questions is: How can you 'jump' outside the the carrier set of natural numbers? (unclear what you are asking). – CopyPasteIt Mar 17 '19 at 10:23
  • @AsafKaragila

    Wow, this was in my first year of my degree haha (I'm done now). Asaf is correct, this was actually from our Analysis course. Also Asaf, you were one of my favorite TA's, hope everything is going well!

     – Charles Carmichael Mar 20 '19 at 22:01
  • @Martin: I rest my case. – Asaf Karagila Mar 20 '19 at 22:13
  • @Charles: Glad to hear it. I'm doing well, I'd think. I hope you're doing alright as well. :) – Asaf Karagila Mar 20 '19 at 22:14

2 Answers2

1

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

J.G.
  • 115,835
0

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.

Dr Potato
  • 772