Why induction can't work for infinite number?

Question

Loosely speaking, there is no such number n+1= infinity.

Is there any way to prove that induction can not work for infinite numbers in formal way?

Answer 1

Induction is defined, in general, on well-founded structures. More specifically, we can talk about inductions on ordinals which are a very good extension of the natural numbers.

So some inductions can be extended beyond the natural numbers. However it's not something of "$\infty+1$". It has more details, crafted more carefully. And I am not going to get into that here.

But we can prove that if $n$ is a natural number then $n+1$ is a natural number, simply because the axioms of the natural numbers tell you that if $n$ is a natural number, then $n+1$ is another natural number. Induction has nothing to do with that.

Answer 2

Look up transfinite induction.

You start by defining ordinal numbers. These come in two sorts: successors, those ordinals $\alpha$ for which there is an ordinal $\beta$ such that $\alpha=\beta+1$, and limits, for which there is no such ordinal. (Thus $0$ is technically a limit.) They can be formed using a sort of notion of supremum: $\omega$, the smallest non-finite limit, cannot be reached in a finite amount of steps, but is obtained by taking the set of all finite ordinals. (I'm very much not being precise here: look up ordinals on Wikipedia for the actual definitions.)

Now, transfinite induction is similar to ordinary induction for zero and for successors, but there is a new notion of when something holds for a limit ordinal: we have to show that $P$ holds for a limit $\alpha$ if it holds for every ordinal less than $\alpha$.

Answer 3

Let's prove by induction that all sets are finite.

Basis: The empty set is finite.

Induction step: If every set of size $n$ is finite, then so is every set of size $n+1$.

---

One hopes you see a flaw in this argument. The way to show that induction can prove that something is true of all (infinitely many) finite cardinal numbers but cannot prove the same is true of an infinite cardinal number is by exhibiting counterexamples. What you see above is a counterexample. Below I describe another counterexample.

---

Say you've show that the intersection of two open sets is open. That will be the basis for induction, to prove this:

The intersection of $n$ open sets is open.

Proof (just the induction step:) Let $G_1,\ldots,G_n,G_{n+1}$ be open sets. By the induction hypothesis $G_1 \cap\cdots\cap G_n$ is open. Then $$ G_1\cap\cdots\cap G_{n+1} = \Big( G_1\cap\cdots\cap G_n\Big)\cap G_{n+1} $$ and that is an intersection of two open sets, since the induction hypothesis has told us that the set inside the $\Big(\text{big parentheses}\Big)$ is open. Therefore it is open. $\qquad\blacksquare$

Now how about an infinite sequence of open sets. Let $G_n$ be the open ball of radius $1/n$ about a point $x$, i.e. the set of all points whose distance from $x$ is less than $1/n$. The intersection of all of those open balls contains only $x$, and that is not an open set.

---

All that said, I will now add that there is a particular kind of induction that goes beyond finite numbers and works on "ordinal" numbers in the sense in which that term is used in set theory. In that kind of induction, one has an induction hypothesis that says the proposition is true of all cases before the $n$th case, and $n$ may be an infinite ordinal number, and may not have an immediate predecessor. One peculiarity of this form of induction is that no basis for induction need be proved. If the statement is shown to be true of $n$ whenever it's true of all predecessors of $n$ (immediate or not), the automatically it's true of $0$ because $0$ has no predecessors. But this form of induction should be learned only after you're clear on what ordinals are.

Answer 4

The opposite is true. Induction can be generalized beyond the positive integers, in that it is possible to formally define what it means to have an argument where a property can propagate from basic cases to more complicated ones in a way that eventually covers all possibilities. When the formalization is carried out, certain "infinite numbers" (ordinals) inevitably appear as the basic ingredients from which inductive structures are built, and they serve as a measuring scale in which any induction argument can be described as equivalent in complexity to some ordinal.

Answer 5

$S_{_N}=\displaystyle\sum_{n=1}^N\frac1{n^2}$ is rational for all natural N. However, letting $N\to\infty$, we have $S_\infty=\dfrac{\pi^2}6\not\in$ Q.