37
$\begingroup$

I am trying to understand why induction is valid. For instance why would this 'proof' not be valid under the principle of proof by induction ? :

$$ \sum_{k=1}^{\infty} \frac{1}{k} \lt \infty$$ because using induction on the statement $$S(n) = \sum_{1}^{n} \frac{1}{k} \lt \infty$$ - "$S(1) < \infty$ is true and "$S(n) < \infty$" implies "$S(n+1) < \infty$" since $S(n+1) \lt S(n) + \frac{1}{n}$

|cite|improve this question
$\endgroup$
  • 49
    $\begingroup$ Read the principle of mathematical induction again. The conclusion only says $P(n)$ is true for every integer $n$, which is very different from $P(\infty)$ being true. $\endgroup$ – dezdichado Dec 21 '16 at 4:01
  • 12
    $\begingroup$ This is one of my favourite mathematical errors. A thing and its limit need not have anything in common. You can build a hollow house out of solid bricks. $\endgroup$ – Eric Lippert Dec 21 '16 at 11:03
  • 1
    $\begingroup$ Maybe not quite a duplicate, but strongly related Why doesn't induction extend to infinity?. $\endgroup$ – Marc van Leeuwen Dec 21 '16 at 11:45
  • 4
    $\begingroup$ The question, and in particular the final line, is (also) confused about whether $S(n)$ designates a value or a proposition. $\endgroup$ – Marc van Leeuwen Dec 21 '16 at 11:49
  • 1
    $\begingroup$ You also need to make very sure that you're not treating infinity like a number just because it is on the right of an inequality. By "the infinite sum is less than infinity" we are not actually comparing two numbers. This is just a convenient shorthand for there exists a number b (for "bound") such that every finite sum is less than b. $\endgroup$ – Eric Lippert Dec 21 '16 at 23:00
69
$\begingroup$

With induction, you can only prove $S(n)$ is true for all positive integers $n$. However, even though $S(n)$ is true for arbitrarily large $n$, the statement "$S(\infty)$" does not follow from induction because $\infty$ is not a positive integer.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ Also the statement $S(n)$ is meaningless for finite $n$; $<\infty$ does not say anything at all about a finite sum of real numbers. $\endgroup$ – R.. Dec 22 '16 at 23:33
  • $\begingroup$ It's not meaningless, it's just TRUE. $\endgroup$ – Tom Church Jan 11 '17 at 18:50
  • $\begingroup$ @R..: “$<\infty$ ” does not say anything in any notation with which I am familiar. More pertinent is that the definition of $ S(\infty) $ is not the same as the definition of $ S(n) $ for $ n \in \mathbb N $. And in the latter case, of course, as Tom Church says, $S(n)$ is true. $\endgroup$ – PJTraill Oct 12 '17 at 19:34
54
$\begingroup$

The same proof shows that the set of all positive integers is finite:

\begin{align} & \{1\} \text{ is finite.} \\ & \{1,2\} \text{ is finite.} \\ & \{1,2,3\} \text{ is finite.} \\ & \{1,2,3,4\} \text{ is finite.} \\ & \qquad \vdots \\ & \text{and so on.} \\ \text{Therefore } & \{1,2,3,4,\ldots\} \text{ is finite.} \end{align}

|cite|improve this answer
$\endgroup$
  • 13
    $\begingroup$ This is a good start of an answer but I think you need to elaborate a little more on why it doesn't work. $\endgroup$ – Q the Platypus Dec 21 '16 at 6:11
  • 4
    $\begingroup$ This still creeps me out because of the time when I was stupid enough to try to reason with an anti set theory crank. $\endgroup$ – Carsten S Dec 21 '16 at 15:07
  • $\begingroup$ I see what you're going for, but your claim doesn't match your proof. You have shown through induction that for n > 0, {1, ..., n} has a cardinality of n. $\endgroup$ – Kjata30 Dec 21 '16 at 19:34
  • 3
    $\begingroup$ @Kjata30 : I'm not following you. The idea is that if you add one more element to a finite set, you get a finite set; therefore every initial segment of the set of all positive integers is finite. $\endgroup$ – Michael Hardy Dec 22 '16 at 18:35
24
$\begingroup$

By induction you have proved that for all $n\in\mathbb Z^+$, $\displaystyle\sum_{k=1}^n\frac 1 k$ is finite, which is true. This is not the same as proving that $\displaystyle\sum_{k=1}^\infty\frac 1 k$ is finite...

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

I would add to the other comments that when you take the limit $<$ changes into $\le$. So by taking the limit you would get $\sum_{k=1}^\infty\frac{1}{k}\le\infty$, which is not particularly useful.

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

Other answers make the valid point that you can only deduce $( \forall n \in \mathbb N :P(n) )$ by induction, but not $ P(\infty) $ (though see footnote1). There is, however, another problem in your case:

Your “$ P $” does not have the same meaning in “$ P(n)$” (where $ n\in \mathbb N $) as it does in “$ P(\infty) $”.

This is confusing, as the notation is the same, but an infinite sum is defined as a limit while a finite sum is defined inductively. Because of this, induction tells us nothing about $ P(\infty) $.

1 You can sometimes deduce $P(\omega)$ when using transfinite induction, but that is a different technique and a different story.

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

A lot of people are talking about the meaning of $P(\infty)$, which I believe is something of a red herring: usually the symbol $\infty$ is a notational convenience, and has no meaning as a formal object.

In particular:

  • $\sum_{n=0}^\infty x_n$ means $\lim_{m\rightarrow\infty}\sum_{n=0}^m x_n$, where again, the limit towards $\infty$ has a precise mathematical meaning not involving the symbol $\infty$.

  • $x<\infty$ simply means that there is some $C\in\mathbb{R}$ such that $x<C$. Alternately, for an increasing sequence $x_n$, $\lim_{n\rightarrow\infty}x_n<\infty$ means that there is a $C\in\mathbb{R}$ such that $x_n<C$ for every $n$.

Now if you try to prove that there is some $C$ such that for every $m$, $\sum_{n=0}^m \frac{1}{n}<C$, you'll run into trouble: certainly there is some such $C$ for each $m$, but there is no $C$ that works uniformly for every $m$. Indeed, if $x<C$, then $x+\frac{1}{m}$ could very well be above $C$.

|cite|improve this answer
$\endgroup$
  • 1
    $\begingroup$ $\lim_{n\to \infty}$ is the same as any other limit if you consider $\infty$ as an element in the one-point compactification of ${\bf N}$. You can do very similar things with nets. Personally, I think when we have a fixed sequence under consideration, it is enough to write $\lim_n$ without using the symbol $\infty$. $\endgroup$ – tomasz Dec 23 '16 at 0:29
  • 1
    $\begingroup$ The same is true about $\lim_{n\to \infty} x_n<\infty$ -- you just need to consider ${\bf R}$ as a subset of its two-point compactification. If you don't, $x<\infty$ is completely meaningless: any number is less than infinity. $\endgroup$ – tomasz Dec 23 '16 at 0:31
  • $\begingroup$ It's true that $\infty$ can be given meaning with enough (not that much) work, in a similar way that $dy/dx$ can be seen as an actual fraction in certain settings. I'm not sure that introducing limits in the context of the one-point compactification of $\mathbb{N}$ is the right pedagogical move though. $\endgroup$ – cody Dec 23 '16 at 14:25

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.