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.

$\endgroup$
7
  • 13
    $\begingroup$ 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. $\endgroup$
    – joriki
    Commented Apr 13, 2012 at 15:14
  • 3
    $\begingroup$ 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. $\endgroup$
    – mdp
    Commented Apr 13, 2012 at 15:17
  • 1
    $\begingroup$ 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? $\endgroup$
    – Eric Lippert
    Commented Apr 13, 2012 at 22:31
  • $\begingroup$ @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. $\endgroup$
    – GarouDan
    Commented Apr 13, 2012 at 23:01
  • 1
    $\begingroup$ Here is a closely related question: math.stackexchange.com/questions/98093/… $\endgroup$
    – Jonas Meyer
    Commented May 31, 2012 at 9:57

3 Answers 3

Reset to default
20
$\begingroup$

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).

$\endgroup$
3
  • 1
    $\begingroup$ 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? $\endgroup$
    – GarouDan
    Commented Apr 13, 2012 at 22:54
  • 2
    $\begingroup$ @GarouDan Look into ordinals. 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. $\endgroup$
    – SL2
    Commented Apr 13, 2012 at 23:49
  • 1
    $\begingroup$ @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". $\endgroup$
    – Shufflepants
    Commented Mar 9, 2015 at 17:55
1
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ (-1) for "error in the proof". $\endgroup$
    – TMM
    Commented Apr 13, 2012 at 17:20
  • $\begingroup$ 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. $\endgroup$
    – GarouDan
    Commented Apr 13, 2012 at 22:57
0
$\begingroup$

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.

$\endgroup$

You must log in to answer this question.

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