5
$\begingroup$

Using the induction method:

$(\forall P)[[P(0) \land ( \forall k \in \mathbb{N}) (P(k) \Rightarrow P(k+1))] \Rightarrow ( \forall n \in \mathbb{N} ) [ P(n) ]]$

Why this proof is wrong?

$P(x)\equiv (\displaystyle\lim\limits_{a \to x}\sum_{i=0}^{a}\frac{1}{i!}\in\mathbb{Q})$

Basis

$P(0)\equiv$ True ?

$P(0)\equiv(1\in\mathbb{Q})\equiv True$

Induction

$k \in \mathbb{N}$

$P(k)\equiv$ True $\implies P(k+1)\equiv$ True?

$P(k+1)\equiv$ $(\displaystyle\lim\limits_{a \to k}\sum_{i=0}^{a+1}\frac{1}{i!}\in\mathbb{Q}) \implies (\displaystyle\lim\limits_{a \to k}\sum_{i=0}^{a}\frac{1}{i!}+\lim\limits_{a \to k}\frac{1}{(a+1)!}\in\mathbb{Q})\implies (P(k)+\frac{1}{(k+1)!} \in \mathbb{Q})\implies$ True

So, $P(x)$ is true for all $x \in \mathbb{N}$.

But,

$\lim\limits_{x \to \infty}{P(x)}\equiv (\displaystyle\lim\limits_{x \to \infty}\lim\limits_{a \to x}\sum_{i=0}^{a}\frac{1}{i!}\in\mathbb{Q})\equiv \lim\limits_{x \to \infty}\sum_{i=0}^{a}\frac{1}{i!}\in\mathbb{Q}\implies e \in \mathbb{Q}$. But we know $e$ don't belongs $\mathbb{Q}$.

So I would like to know, why this fake proof doesn't work, why run through all integers in $x$ until the last one, infinity, the formula fails.

Edit: I had include limits to extend the discussion.

  • 13
    Part of what may be misleading you is the idea of infinity as "the last integer". There is no last integer, every integer has a successor; and infinity is not an integer; in particular, it has no integer predecessor from which $P(\infty)$ could be deduced by induction.2012-04-13
  • 3
    It is a very common error to try to use induction to prove the infinite case. Note that you get the truth of $P(k)$ by knowing that $P(k-1)$ is true and using $P(n)\implies P(n+1)$, so if you want to get "$P(\infty)$" (where this makes sense), you need to know $P(\infty-1)$ (which really doesn't make sense) first. This isn't really a mathematical explanation of why it fails, joriki has already given that really, but it seems to be a pedagogically helpful explanation.2012-04-13
  • 1
    Right, there's nothing whatsoever wrong with the proof. The error is the belief that the limit of a sequence has *any property at all* in common with *any* member of the sequence. For example: (3, 3.1, 3.14, 3.141, ... ) is a sequence of rationals. Its limit, pi, is an irrational number. There's no contradiction there; the limit isn't even a member of the sequence, so why would a property in common to all the members also apply to the limit, a non-member?2012-04-13
  • 0
    @joriki, this is a interesting point, but I don't know, I'm not sure if I'm asking so much, but maybe I need a argument came of the *logic* field. This question bothers me about two years, so I decided share with the comunity. I hope this discussion grows and have a nice end.2012-04-13
  • 0
    @EricLippert, I changed the question a little to put limits to all statements.2012-04-13
  • 0
    OK, so now the error in the proof is the statement again that the limit of P(x) as x goes to infinity is in Q just because every P(x) is in Q. Again: there is no reason whatsoever to believe that just because a thing is true of every member of a sequence, that the same thing is true of the limit of that sequence.2012-04-14
  • 1
    Here is a closely related question: http://math.stackexchange.com/questions/98093/why-doesnt-induction-extend-to-infinity-re-fourier-series2012-05-31

3 Answers 3

20

No, your statement is true and the proof does work; it's just that rationality isn't preserved in the limit. The key is that the statement is only for $n \in \mathbb{N}$, whereas $\infty \notin \mathbb{N}$ -- induction only proves things about natural numbers, each one of which is finite (even though there are an infinite number of them).

  • 1
    Interesting point Vandermonde. Well, $\infty$ is a hard thing to define and I would like appreciate a Cantor's help on this ^^. But my question is, $\infty$ really don't belongs $\mathbb{N}$? Even the *last* natural number. Say infinity is not natural I think is a correct statement, but say no one infinity belongs naturals sounds incorrect (because we have several infinity types, with diferent cardinalities). What we can say abou that?2012-04-13
  • 2
    @GarouDan Look into [ordinals](http://en.wikipedia.org/wiki/Ordinal_number). The natural numbers are the ordinal $\omega$, and the next ordinal $\omega+1$ has this 'number' infinity that lies after ever natural number. The problem is that 'infinity' is a limit ordinal, while all the ordinals prior to it are successor ordinals. To prove statements about limit ordinals you need [transfinite induction](http://en.wikipedia.org/wiki/Transfinite_induction).2012-04-13
  • 1
    @GarouDan "Even the last natural number" There is no last natural number, that's what it means for there to be infinitely many of them. And you're correct, infinity is not a natural number. I'm afraid I don't understand what you have written after "but say no".2015-03-09
1

I would like to suggest a different perspective on the error in the argument - because it occurred to me, not because anything already said about induction and infinity is wrong.

If you construct the Real Numbers using Dedekind Sections you will see that every Real Number is the limit of a sequence of rational numbers. Real Numbers are useful in Analysis partly because they are closed under taking appropriate limits, while the Rational Numbers aren't. So one way of looking at the problem with the proof is that a limit has been taken in an inappropriate context.

  • 0
    (-1) for "error in the proof".2012-04-13
  • 0
    Mark Bennet, your perspective is interesting. Passed to my mind consider $1=0.9999\dots$ and to this representation of 1, a trasnformed P(x) will hold, because, of course, 1 is rational.2012-04-13
0

You did prove $P(x)$ is true for all positive integers $x$. However that does not allow you to conclude that $P(\infty)$ is also true. Your example is a testament to this invalid conclusion, since it is known that $e$ is not rational.