2

I know that induction works only for the natural numbers $\mathbb{N}$. We first have to prove the base case. And we then prove that if the statement $p(k)$ holds then $\color{blue}{\textbf{p(k+1)}}$ also holds.

Now what if we want to prove a statement about naturals that have a gap bigger than $1$.Maybe we just want to prove a statement for all even natural numbers so we want to prove $\color{green}{\textbf{p(k+2)}}$ .

I mean can we generalize induction in case where we are not interested in proving $\color{blue}{\textbf{p(k+1)}}$ . We are just interested in proving $\color{purple}{\textbf{p(k+n)}}$ . Can we change that and will it still work ?

Now for real numbers, I know that mathematical induction doesn't work because $\mathbb{R}$ is not countable. But what if we want to prove a statement about $\mathbb{R^+}$. Why can't we prove the base case normally with $r=0$ and then we assume $p(r)$ works then we try to do prove that $\color{brown}{\textbf{p(r+ $\epsilon$)}}$

One last question, Why is induction not valid for integers, negative integers,countable sets in general ?

alkabary
  • 6,214

3 Answers3

3

The most general case where induction works for a claim $P$ on elements of a set $X$ is:

  • You have a set of base cases where you can prove the claim directly, that is, a set $S_0\subset X$ so that you can prove in some way that $P(x)$ for all $x\in S_0$.
  • You have a set of provable induction rules telling you that if the condition is true in any set $A$ of a certain form, then you can deduce that it also is true for the members of a set $B\not\subset A$, that is $(\forall x\in A, P(x))\implies (\forall x\in B, P(x))$.
  • By starting with the initial set $S_0$, you can cover the complete set $X$ by successive application of the induction rules. That is, by starting with the set $S_0$, you can always find at least one induction rule that is applicable by the rules you found so far, and for each element of $X$, you can find a sequence of induction rules so that the induction rules ultimately prove $X$.

In the case of the usual induction over the natural numbers (assuming the definition including $0$):

  • $S_0=\{0\}$, and the prove is typically by a simple check.
  • either $A=\{n\}$ for any $n\in\mathbb N$, or $A=\{0,1,\ldots,n\}$, and $B=\{n+1\}$.
  • Peano's axioms (or the axioms of set theory) guarantee that by repeatedly adding $1$, you'll eventually reach any natural number.

However that's not the only possible way. For example, a statement might also be proved for all positive integers as follows:

  • Prove it for $1$ (that is, $S_0=\{1\}$)
  • Prove that if it is true for any number $n$, then for any prime $p$ it is true for $pn$ (that is, $A=\{n\}$, $B=\{pn: p \text{ prime}\}$).
  • The fact that every positive integer has a prime decomposition guarantees that you'll get all of them.$

A statement for all of $\mathbb Z$ can be proven by induction as follows:

  • Start with proving for $0$.
  • Prove two induction rules, one going from $n$ to $n+1$, and one going from $n$ to $n-1$.
  • Since you can reach each integer starting from $0$ by successive addition or subtraction of $1$, you've the proven it for all of $\mathbb Z$.

A statement for $\mathbb R^+$ could be proven as follows:

  • As induction start, prove it for every positive number $x\le 1$, that is, $S_0 = (0,1]$.
  • As induction step, prove that if it is true for $x$, then it is true for $x+1$.
  • Since every positive real number can be written as sum of a natural number and a number from the interval $(0,1]$, you've now proven it for all positive real numbers.
celtschk
  • 43,384
0

if you are interested in $p(k+n)$ with always the same $n$ a renumbering will do, of course -- this way you can, of course, prove statements for all $m\in \{ k_0+ rn: r\in \mathbb{N}\}$, say.

For the other question, as an example, check wikipedia for 'transfinite induction' as a possible extension.

Thomas
  • 22,361
0

These are very good questions, in that they directly address the question of why induction works.

For your first question concerning p(k+n). If the based case is n=1, then induction can be used to prove p(k+1), p(2k+1), p(3k+1). For example, if k=5 and p(x) means "leaves a remainder of 1 when divided by 5", then you could use induction to prove p(5k+1) is true for all k. But as not all numbers can be represented in the form 5k+1, p(n) is not generally true.

So lets move onto the meatier part of the question - induction over sets which are not N. In order to see what the issues are going to be, its worth thinking about why induction works over N.

Induction can be stated as : If we know something is true of p(1), and if p(k) then p(k+1) is true, then p(n) is true for all n. This is because we know p(1) is true, so we can work out p(2) is true, so we can work out p(3) is true, etc.

So the proof works because we can step through 1,2,3... and eventually reach all elements of N (all positive integers). Because we can step through in this manner N is said to be well-ordered.

So to use induction over sets other than n, we need to identify a base case and show we can step through every other case.

The base case needn't be one, one might not even appear in the set. It must be in some sense the smallest (first) object, you can pick whatever rule you want for "smallest". And the order doesn't have to be the normal arithmetic order.

This ability to always pick the "smallest" number in a set is called the Axiom of Choice, and sets which adhere to this are called "well ordered". All countable sets are well ordered, and other sets may be as well.

Lets consider induction style proofs over rationals, a countable set. They can be well-ordered,

![countable-rationals][1]

from http://www.homeschoolmath.net/teaching/rational-numbers-countable.php which shows an ordering of positive rationals. The base case would be 1 (the first number), next case 2, then 1/2, etc. This sequence of numbers can be expressed as a formula. But they jump around wildly - its very hard to see what property you could prove about the (n+1)th term knowing that some property was true of the nth term. This isn't so much of a problem using induction over N, as we only have to prove that if its true for n, its true for n+1. With induction over rationals, we have to prove that its true for nth term in the sequence, its true for the (n+1)th term in the sequence, and seeing as how they have a complicated relationship, this is much harder. I don't know of any induction proofs over countable sets which work this way, but its theoretically possible they do, and if anybody knows of any I would be interested.

Now for the slightly thornier case of uncountable sets like R.

In your explicit question, if you prove the base case with r=0 and then prove the "induction" step as p(r+c) for arbitrary c, then all the "induction" step is doing is proving p(c) for all c, which is what you are trying to do in the first place. It doesn't help.

For a fuller explanation, deep breath. Whether we can do induction on Reals depends on a whether they can be well-ordered. If we assume the Axiom of Choice, they can be. (This is called transfinite induction). In fact they can be well-ordered in an uncountably infinite number of ways. So you would think in principle you could find the first Real (according to some rule), a second Real, and by some process in principle step through all Reals and hence solve for all Reals. There are however some problems. Firstly, the Reals would jump about wildly like the Rationals did, making any arithmetic rule which applies to one Real in the sequence very difficult to apply to the next Real. Secondly, the Axiom of Choice tells us that such an ordering exists, but it doesn't tell us what it is. In fact we don't know of a well ordering of the Reals, and an explicit ordering would be impossible with a finite length rule, so there would seem to be no opportunity to use induction to prove arithmetic rules about Reals. But the principle behind induction - well ordering - is very useful for proving many other (set theoretic) things about Reals.

[1]: https://i.stack.imgur.com/glICq.gif from http://www.homeschoolmath.net/teaching/rational-numbers-countable.php

Peter Webb
  • 839