Problem understanding a proof by induction for 2 variables

inductionreal numbersreal-analysis

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?

Best Answer

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.

Related Question