16
$\begingroup$

After reading a question made here, I wanted to ask "Why do we do mathematical induction only for positive whole numbers?"

I know we usually start our mathematical induction by proving it works for $0,1$ because it is usually easiest, but why do we only prove it works for $k+1$?

Why not prove it works for $k+\frac12$, assuming it works for $k=0$.

Applying some limits into this, why don't we prove that it works for $\lim_{n\to0}k+n$?

I want to do this because I realized that mathematical induction will only prove it works for $x=0,1,2,3,\dots$. assuming we start at $x=0$, meaning it is unknown if it will work for $0<x<1$ for all $x$.

And why not do $k-1$? This way we can prove it for negative numbers as well, right?

What's so special about our positive whole numbers when doing mathematical induction?

And then this will only work for real numbers because we definitely can't do it for complex numbers, right?

And what about mapping values so that it becomes one of the above? That is, change it so that we have $x\to x/2$? Then proving for $x+1$ becomes a proof for all $x$ that is a multiple of $\frac12$!?

$\endgroup$
  • 3
    $\begingroup$ There wouldn't be any reason to do $k+\frac{1}{2}$. Then, you would be proving the statement for the set $0, 0.5, 1, 1.5, 2, 2.5, 3, 3.5...$. In other words, numbers of the form $\frac{n}{2}$ for natural $n$. But then you could use normal induction on $n$. $\endgroup$ – MathematicsStudent1122 Dec 25 '15 at 15:16
  • 2
    $\begingroup$ Related from the site blog $\endgroup$ – Daniel R Dec 25 '15 at 17:36
  • 6
    $\begingroup$ Basically, because you haven't yet studied enough math to run into other, more interesting forms of induction. $\endgroup$ – Ilmari Karonen Dec 25 '15 at 22:01
  • $\begingroup$ @IlmariKaronen Oh, you bet. $\endgroup$ – Simply Beautiful Art Dec 25 '15 at 22:19
  • $\begingroup$ Look up structural induction for a more general perspective on where it works. $\endgroup$ – Gone Dec 26 '15 at 4:05
32
$\begingroup$

Let's forget about natural numbers for a while and take a look at what mathematical induction is proving. At the base step, it's proven that a property, say $P$, holds for some special object, say $a$. At the induction step, it's proven that if $P$ holds for some fixed object, say $x$, then it holds for some other object related to $x$ in some way, which can be translated mathematically to: for some function $S$, $P$ holds for $S(x)$. Now, since we know that $P$ holds for $a$, we conclude that $P$ holds for $S(a)$, and then for $S\big(S(a)\big)$, and so on: $$a\quad\to\quad S(a)\quad\to\quad S\big(S(a)\big)\quad\to\quad S\Big(S\big(S(a)\big)\Big)\quad\to\quad\dots$$ this leads to a sequence of objects defined like this: $$a_0=a$$ $$a_{n+1}=S(a_n)$$ $$a_0\quad\to\quad a_1\quad\to\quad a_2\quad\to\quad a_3\quad\to\quad\dots$$ and $P$ holds for every element of this sequence. If we look at the indices, we find natural numbers. So natural numbers appear naturally in inductive proofs! It may be useful to note that having only the basis and the inductive step, the objects mentioned above are the only objects that we have proven to have the property $P$.

Now, the standard starting object is $0$ and the standard successor function is $S(x)=x+1$. But putting any other objects in a sequence, you can use induction for giving a proof. Note that even in that case, you can define a sequence like we did before, and use the standard induction! So there is no real difference between them. For example, letting $a=0$ and $S(x)=x-1$, you can prove a property for every nonpositive integer. In this case we have $a_n=-n$. So you can use mathematical induction twice to prove a property for all integers; once with $a=0$ and $S(x)=x+1$, and once with $a=0$ and $S(x)=x-1$.

Finally, it may be useful to note that not every set of objects can be represented as a sequence. For example, real numbers can't be listed in a sequence and so you can't use this kind of induction for them.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ I have read some links in other comments noting that you can do inductive proofs without using the natural numbers. I can't understand it though. $\endgroup$ – Simply Beautiful Art Dec 25 '15 at 15:29
  • $\begingroup$ In fact there are other kinds of induction which are stronger than what I talked about (for example you can search about transfinite induction, well-ordered sets, ordinal numbers and well-founded sets to find some information, but they may look rather difficault to understand. @drhab has posted an answer related to these). That's why I wrote "this kind of induction" in the last paragraph. Your question is related to the relation between natural numbers and induction, which is mostly related to what I said. $\endgroup$ – Mohsen Shahriari Dec 25 '15 at 15:36
  • $\begingroup$ @SimpleArt Induction requires either a proof that induction is applicable, or an axiom of induction declaring it to always be so. You are right that there's ways to do it without natural numbers, but whatever system you use does need to have some axiom that permits induction. Peano arithmetic happens to have an axiom of induction, so it is trivial to demonstrate that induction works for natural numbers. $\endgroup$ – Cort Ammon Dec 26 '15 at 5:42
  • $\begingroup$ Is it essential that $S$ be injective? $\endgroup$ – Jeremy Roach Dec 27 '15 at 14:01
  • $\begingroup$ @JeremyRoach Not in a general sense. In that case, the sequence $a_n$ will contain finitely many distinct elements. $\endgroup$ – Mohsen Shahriari Dec 28 '15 at 4:18
9
$\begingroup$

Induction really only requires that we can always make some sort of path between our base case and the cases we want to prove. The normal form of induction makes a path that looks like: $$\rightarrow 0\rightarrow 1 \rightarrow 2 \rightarrow 3 \rightarrow 4 \rightarrow \ldots$$ where each arrow represents an implication - that the case for $n$ implies the one for $n+1$. I include an arrow to $0$ to remind us that that case must be proven. It's perfectly okay to replace this path by any other one - so $$\rightarrow 0\rightarrow \frac{1}2\rightarrow 1\rightarrow \frac{3}2\rightarrow 2\rightarrow \ldots$$ works just as well or starting from a negative $$\rightarrow-1\rightarrow 2\rightarrow 3 \rightarrow 4\rightarrow 5\rightarrow\ldots$$ or going in both directions $$\begin{align*} & \downarrow & \\\ldots\leftarrow-3\leftarrow -2\leftarrow -1 \leftarrow &\,\,0\rightarrow1\rightarrow 2 \rightarrow 3\rightarrow\ldots\end{align*}$$ so long as we can provide a proof corresponding to each of the arrows.

A notable thing about this is that we can use something called "structural induction" where we think of discrete mathematical structures (like graphs or groups) and prove some property of them by reducing the problem to a smaller case (in a way that, enough such reductions bring us to some base case), and these could have quite complex diagrams if plotted as I've been doing. The main point of these pictures is that induction requires making some sort of linking.

In the abstract sense, what induction requires is that we order all the cases we wish to prove it on in a special way called a "well-order" which means that every non-empty set has a minimal element (i.e. an element $x$ so that there is no $y<x$ in the set). Then, we need to prove, for any element $x$ a proof that, if our desired proposition holds for all $y<x$, it holds for $x$ as well. What we then find is that, if there were a counterexample, there would be a minimal counterexample - some $x$ such that for all $y<x$, the statement held. But this is impossible since the statement holding for all $y<x$ suffices to show the proposition.

Ordinary induction uses the ordinary order on the natural numbers - and we note that we are required to prove that the case of $0$ holds assuming it holds for all $x<0$ - of course, there are no such $x$ in our domain, which explains why the base case needs separate proof. Similarly, we can induct on the set $\frac{1}2\mathbb N$ using the normal order. And, the induction on $\mathbb Z$ I depicted comes from the (partial) order defined as normal on the positives and defined as $-n<-m$ on negatives exactly when $n<m$ for $n,m\in\mathbb N$ (where we do not say that $1<-1$ or $-1<1$ - we never need to compare them as neither is used in the proof of the other).

The ordinary order on $\mathbb R>0$ does not satisfy this. However, if one can prove that if the statement holds for $x$ then it holds for $x+k$ for all $k\in (0,\varepsilon]$ for a fixed $\varepsilon$, then one may order the set by saying that $x<y$ whenever $x+\varepsilon$ is less than $y$ in the usual order, and this is a well order, so we can use induction. This does, however, require us to prove infinitely many implications, and one really doesn't see it that much.

| cite | improve this answer | |
$\endgroup$
7
$\begingroup$

Induction works on a set $A$ that is equipped with a relation $R\subseteq A\times A$ such that every non-empty subset $B$ of $A$ contains an element $b\in B$ with $\{x\in A\mid x \mathrel{R} b\}\cap B=\varnothing$.

A relation that satisfies this is by definition "well-founded".

Let $\mathcal P$ be some property of elements of $A$ that is "inherited" from $R$-predecessors.

This in the sense that: if $\mathcal P(b)$ for all $b\in A$ with $b \mathrel{R} a$ then also $\mathcal P(a)$.

Then it can be shown that $\mathcal P(a)$ is true for each $a\in A$.

To prove this assume that the statement is not true. Then the set $B:=\{a\in A\mid\neg\mathcal P(a)\}$ is not empty. Let $b\in B$ with $\{x\in A\mid x \mathrel{R} b \}\cap B=\varnothing$. Then $\mathcal P(c)$ for $c\in A$ with $c \mathrel{R} b$ and consequently $\mathcal P(b)$. A contradiction is found, and we are ready.

So the essential question here is:

are we dealing with a well-founded relation on a set?

The answer is "yes" if you are working with e.g. $\langle\mathbb N,<\rangle$ or $\langle\{\frac12n\mid n\in\mathbb N\},<\rangle$ or $\langle-\mathbb N,>\rangle$, but is "no" if you are working with e.g. $\langle\mathbb R,<\rangle$, $\langle\mathbb Z,<\rangle$ or $\langle\mathbb N,>\rangle$ .

| cite | improve this answer | |
$\endgroup$
2
$\begingroup$

All of the contexts in which you propose to apply induction are implicitly using the positive integers anyway.

For instance, suppose we have a property $P$, and we prove that $P(x)\implies P(x+\frac 1 2)$. Then if we know $P(0)$, we can prove $P(0.5)$, $P(1)$, $P(1.5)$, etc. But you're implicitly using the natural numbers here. You're proving that if $P(n\frac 1 2)$ holds, then $P((n+1)\frac 1 2)$ holds, and thus concluding that $P(n\frac 1 2)$ holds for all $n$.

Or suppose we prove that $P(x)\implies P(x-1)$. Then from $P(0)$ we could deduce $P(n)$ for any negative $n$. But here you're implicitly proving that if $P(-n)$ holds then $P(-(n+1))$ holds and thus proving that $P(-n)$ holds for all positive $n$.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Yes, but it is not normal to see induction occur this way, at least not in schooling. $\endgroup$ – Simply Beautiful Art Dec 25 '15 at 16:49
1
$\begingroup$

Proof by induction "works" because the inductive step is :

for any $n$, if $P(n)$ holds, then $P(n+1)$ holds.

The key feature here is that for any $n$ we have a successor : $n+1$.

If we move to e.g. rational numbers with the "usual" ordering, we have no successor; what us the successor of $k + \frac 1 2$ ? Is it $k+1$ ? Why not $k + \frac 3 4$ ?


See Mathematical induction :

Mathematical induction is a mathematical proof technique, most commonly used to establish a given statement for all natural numbers, although it can be used to prove statements about any well-ordered set.

Thus, in order to apply to e.g. rationals you have to rely on the well-ordering of $\mathbb Q$, and this is not $\le$.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ What makes it work though? What if we mapped $n+1\rightarrow n+1/2$? Can we? $\endgroup$ – Simply Beautiful Art Dec 25 '15 at 14:43
  • $\begingroup$ Are you saying I can't prove it works for $/frac x2$, even if I prove it works for $x$ and then mapped it? $\endgroup$ – Simply Beautiful Art Dec 25 '15 at 14:52
  • 1
    $\begingroup$ @SimpleArt - see this post for discussion on how to use induction "backwards" or with different steps. $\endgroup$ – Mauro ALLEGRANZA Dec 25 '15 at 14:59
  • $\begingroup$ Thank you. I will go over that. $\endgroup$ – Simply Beautiful Art Dec 25 '15 at 15:01
1
$\begingroup$

If you let $P$ be your initial proof, and $ind : PROOFS \to PROOFS$ be your induction step, then the set $PP$ of all the proofs you can inductively prove from them is $\{P,ind(P),ind(ind(P)),...\}$. If you define $X : PROOFS \to (PROOFS \to PROOFS) \to \mathbb{N} \to PROOFS$ such that $X(P,ind,0) = P$ and $X(P,ind,n) = ind(X(P,ind,n-1))$, then you can set $ind' = X(P,ind)$ and rewrite $PP$ as $\{ind'(0),ind'(1),...\}$.

Since you can always reduce any mathematical induction to an induction over the integers, you can assume the latter without loss of generality. Nothing is keeping you from defining induction over another countable set, however you must beware that, discounting proofs of infinite size, you can never inductively prove a property for all real $x$ such that $0 < x < 1$, since they do not form a countable set.

Edit: Sorry, I didn't realize the answers above already covered much of the ground, it's just a really good question and I got carried away ^^ If you want to learn more about what makes whole numbers special, I suggest you read about Gödel numberings, which establish interesting relations between the natural numbers and proof objects themselves. With such a numbering, you can freely replace $PROOFS$ by $\mathbb{N}$ in my earlier answer, perhaps making it much clearer.

Regarding the notion of countable set, it's just a fancy word for "a set whose elements can be listed", or equivalently "a set for which there is a bijection with the positive integers". Examples of such sets are $\mathbb{N}$, $\mathbb{Z}$, $\mathbb{Q}$, and the set $PROOFS$ of all mathematical proofs used above. Examples of non-countable sets include $\mathbb{R}$ and $\mathbb{C}$ (see Cantor's diagonal argument for an intuitive proof of that last claim), and of course any nonempty interval $]a,b[$ in $\mathbb{R}$, since it can be bidirectionally mapped to $\mathbb{R}$ itself using the function $f(x) = tan(\frac{\pi (2x-a-b)}{2(b-a)})$, whose inverse is $f'(x) = \frac{a+b}{2} + \frac{2(b-a)arctan(x)}{2\pi}$. Hence my earlier claim that the real interval $]0,1[$ isn't countable.

| cite | improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ This question is old and has well accepted answer. You are contributing nothing new. $\endgroup$ – Shailesh Dec 25 '15 at 23:51
  • 9
    $\begingroup$ @Shailesh Relax, the question is barely ten hours old and the accepted answers, while very informative, said nothing about treating proofs like first-class objects. I was just trying to add a little language theory to the mix, albeit a bit abruptly. $\endgroup$ – Some Guy Dec 26 '15 at 0:40
  • $\begingroup$ Thanks for the Edits. Now it makes much more sense and I see your point. $\endgroup$ – Shailesh Dec 26 '15 at 1:37
  • $\begingroup$ Nice answer. +1. $\endgroup$ – YoTengoUnLCD Dec 29 '15 at 6:02

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.