2
$\begingroup$

All positive integers are equal, that is, for each $n \in \mathbb{N}$ the assertion $P(N): 1 = \cdots = n$ is true.

(i) $P(1)$ is true because $1 = 1$

(ii) Suppose that $P(n)$ is true, then $1 = \cdots = n - 1 = n$. Summing $1$ on each member of the equality, it follows that $n = n + 1$, hence $1 = \cdots = n - 1 = n = n + 1$ therefore $P(n+1)$ is true.

By the principle of mathematical induction it follows that $P(n)$ is true for all n $\in \mathbb{N}$

Can I say that n = n + 1 is a contradiction to show that this demonstration is wrong? If not, what is wrong in it?

$\endgroup$
1
  • 2
    $\begingroup$ Cut it off specifically at $P(1)\implies P(2)$. Because once $P(2)$ is true all of the other propositions do follow and the other implications are all valid (a model for them would be the trivial ring). $\endgroup$ – anon Mar 20 '13 at 2:15
3
$\begingroup$

The problem is, in your second step, there may be only one number, i.e. $1=1$. Therefore, you cannot add both sides by $1$ and get $1=1+1$. In the other words, in your induction hypothesis $n-1=n$, the $n-1$ term may not exist (when $n=1$ because your base case start at $1$).

$\endgroup$
3
  • 2
    $\begingroup$ This is similar to Polya's proof that there's no horse of a different color. In any set of $n$ horses, they're all of the same color if $n=1$. And the induction step is easy. When one challenges the student to find the error, one doesn't explicitly call attention to the induction step in the case $n=1$. That step works when $n\ge2$, but is problematic when $n=1$. $\endgroup$ – Michael Hardy Mar 20 '13 at 2:36
  • $\begingroup$ @MichaelHardy Right. If it works for $n=2$, which means any two horses are of the same color, then indeed there's no horse of a different color. $\endgroup$ – NECing Mar 20 '13 at 2:39
  • 2
    $\begingroup$ In colloquial language, if any two horses are of the same color, then all horses are of the same color. $\endgroup$ – Michael Hardy Mar 20 '13 at 2:41
1
$\begingroup$

There is a meta-argument that most fallacious induction tricks have to work the same way that this one does.

How can an induction proof go wrong but not transparently wrong?

  1. The base case is defective. As the smallest case, it is usually easy to verify and hard to disguise. Sometimes, using the empty set can create enough confusion.

  2. The step $n \to n+1$ is defective for most $n$. Bad algebra and statements that are wrong for almost all $n$ are hard to disguise. Maybe it can be argued based on examples of the first few $n$ that the induction step works, where the next case would fail. But this is less likely than...

  3. The step from $n$ to $n+1$ is correct for almost all $n$, but wrong at one (or a very small number of) special value. Here you have only to conceal one error, for a value at least slightly larger than the base case.

The last is the easiest to obfuscate, and so the most efficient disproof technique when confronted with a false induction is to look for a small case where the induction step breaks.

$\endgroup$

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.