39
$\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}$

$\endgroup$
7
  • 53
    $\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
  • 14
    $\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$ Dec 21 '16 at 11:03
  • 1
    $\begingroup$ Maybe not quite a duplicate, but strongly related Why doesn't induction extend to infinity?. $\endgroup$ 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$ 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$ Dec 21 '16 at 23:00
76
$\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.

$\endgroup$
3
  • $\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$ Dec 22 '16 at 23:33
  • 1
    $\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}

$\endgroup$
4
  • 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$ 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$ Dec 22 '16 at 18:35
25
$\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...

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

$\endgroup$
0
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.

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

$\endgroup$
3
  • 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
  • 1
    $\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

This site is temporarily in read only mode and not accepting new answers.

Not the answer you're looking for? Browse other questions tagged .