Claim: If $n$ belongs to $\mathbb{N}$, and $p$ and $q$ are natural numbers with maximum $n$, then $p=q$.

Let $S$ be the subset of the natural numbers for which the claim is true. $1$ belongs to $S$, since if $p$ and $q$ belong to $N$ and their maximum is $1$, then $p=q=1$. Now assume $k$ belongs to $S$, and that the maximum of $p$ and $q$ is $k+1$. Then the maximum of $p-1$, $q-1$ is $k$. But $k$ is in $S$, so $p-1=q-1$, thus $p=q$ and $k+1$ is in $S$, so the assertion is true for all $n$ in $N$.

  • 1
    $\begingroup$ Subtracting 1 can take p and q out of the natural numbers (which I gather you are starting at 1). $\endgroup$
    – lulu
    Jul 19 '15 at 12:00
  • $\begingroup$ This question is also the same as one of the answers provided here on the thread Fake Induction Proofs. $\endgroup$ Jul 19 '15 at 16:13

By natural number I assume you mean positive integer. The error in the proof occurs when $k+1=2,p=2,q=1$. Then $q-1 =0$, not a natural number, so there is no case with $p-1$ and $q-1$.


Not the answer you're looking for? Browse other questions tagged or ask your own question.