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