1
$\begingroup$

I will start by giving a background to the problem. In the book I am reading, the existence of the unit element $e$ for the multiplication operation on real numbers is given by axioms assumed for reals. Then, we have the positive integers which till now have not been defined as a subset of reals but rather as natural numbers used for counting purposes. Now, the aim is to identify these natural numbers as real numbers.

We define a mapping $f:Z^+ \to R$ inductively as, $f(1)=e$ and assuming that $f(n)=ne$ has been defined, $f(n+1)=ne+e$.

We want to prove that $(m+n)e=me+ne$ for positive integers $m,n$. The proof given uses induction on $n$. The base case where $n=1$ follows from the definition of $f$. Then assuming proved for all positive integers $ \le n$ and all m, we have $$(m+n+1)e=(m+1+n)e=(m+1)e+ne=me+e+ne=me+(n+1)e$$

What I don't know is how do you justify that it has been proved for all positive integers $m,n$? Intuitively, I can see that we know $f(n+1)=ne+e$ for any positive integer $n$ and so all we have to prove is we can have any positive integer other than $1$ in the expression. In this sense, it's a proof in only one variable but is there a better way to justify us doing induction only on $n$?

Also, in the proof, why has the assumption been made for all positive integers $\le n$? Isn't it enough to assume it just for any positive integer $n$ and show it holds for the next integer as we normally do?

$\endgroup$
1
  • 1
    $\begingroup$ You're assuming nothing special about $m$, so the proof works for every $m$. $\endgroup$
    – egreg
    Commented Jun 4, 2019 at 12:06

1 Answer 1

2
$\begingroup$

You're applying induction on the formula with the free variable $n$

for every natural number $m$, $(m+n)e=me+ne$

which you want to be able to prepend “for every natural number $n$”. Call $P(n)$ that formula.

It seems that your natural numbers start at $1$ (not clear why), so the induction scheme is

  1. prove “$P(1)$”;
  2. prove “for every natural number $n$, if $P(n)$ then $P(n+1)$”.

The axiom on induction then says that you have proved “for every natural number $n$, $P(n)$” that can be so translated into

for every natural number $n$, for every natural number $m$, $(m+n)e=me+ne$

Does it make sense, now?

  1. For $n=1$ we get $(m+1)e=me+e=me+1e$, by definition.
  2. Suppose $(m+n)e=1$; then $(m+n+1)e=(m+n)e+e=me+ne+e=me+(n+1)e$.

Proved.

Your textbook is apparently using strong induction, which doesn't seem necessary here, but the idea is the same; the formula with the free variable $n$ becomes

for every natural number $m$, for every natural number $k$, if $k\le n$ then $(m+k)e=me+ke$

and the induction scheme is the same.

$\endgroup$
7
  • $\begingroup$ I understand your proof but this is different than the proof I have mentioned in the question, and I am not able to understand that. My doubt is that, in that proof, the induction hypothesis is that it is true for all positive integers $\le n$ and all $m$. I don't understand the need to assume it for all positive integers $\le n$. I am also not able to get over the fact that it is assumed it to be true for all $m$. Your proof doesn't have either of these problems as we are proving for a 'general' $m$ and assuming $P(n)$ only for the previous integer to prove for the next. $\endgroup$
    – ModCon
    Commented Jun 4, 2019 at 13:30
  • 1
    $\begingroup$ @NiketParikh The text uses “strong induction”, which is not really necessary here. But the methods are equivalent. $\endgroup$
    – egreg
    Commented Jun 4, 2019 at 14:14
  • $\begingroup$ Right, so strong induction hypothesis isn't necessary. The other thing I am not comfortable with in the proof is that induction hypothesis assumes the statement is true for all $m$. It has also been used in the proof when $(m+1+n)e$ is written as $(m+1)e+ne$ (this can be split like this because it holds for all $m$ including $m+1$ and for $n$). How can one assume it to be true for all $m$? Shouldn't we be proving this for 'an' $m$ and since there is no special assumption about $m$, conclude it holds for every $m$. Isn't it wrong to assume statement holds for all $m$ before proving it does? $\endgroup$
    – ModCon
    Commented Jun 4, 2019 at 14:31
  • $\begingroup$ @NiketParikh There is no “assumption of truth”, actually: you just deduce. $\endgroup$
    – egreg
    Commented Jun 4, 2019 at 14:42
  • $\begingroup$ Could you please elaborate? $\endgroup$
    – ModCon
    Commented Jun 4, 2019 at 15:48

You must log in to answer this question.

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