Why do we do mathematical induction only for positive whole numbers?

Question

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\frac x2$? Then proving for $x+1$ becomes a proof for all $x$ that is a multiple of $\frac12$!?

Answer 1

$ \def \t {\quad \rightarrow \quad} $ 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 \t S ( a ) \t S \big( S ( a ) \big) \t S \Big( S \big( S ( a ) \big) \Big) \t \dots $$ this leads to a sequence of objects defined like this: $$ a _ 0 = a $$ $$ a _ { n + 1 } = S ( a _ n ) $$ $$ a _ 0 \t a _ 1 \t a _ 2 \t a _ 3 \t \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.

Answer 2

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.

Answer 3

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

Answer 4

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

Answer 5

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.

Answer 6

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