First-order logic and Peano Arithmetic paradox I'm working through the Stanford Introduction to Logic course, and seem to have proved that all natural numbers are equal to zero: Ax.(x = 0). Obviously, this is incorrect, but I can't see how. My proof is by induction:


Base case: 0 = 0 by premise
Inductive case: Ax.((x = 0) -&gt; (s(x) = 0))


If we assume that all natural numbers equal zero: x = 0
Then, since all natural numbers equal zero, the successor of any natural number also equals zero: s(x) = 0 by simple substitution

Conclusion: Ax.(x = 0)


I worked this up formally in Stanford's Fitch editor as well:



Can anyone explain my error? Thank you.
When you write &ldquo;If we assume that all natural numbers equal zero&rdquo;, you are assuming the thing that you want to prove.

A proof by induction would be as follows:


first you prove that the assertion holds when $x=0$ (as you did);
then you prove that if the statement holds for $x$, then it also holds for $s(x)$.


And it's here where the problem lies, because one of the Peano axioms states that $0$ is never of the form $s(x)$.
David C. Ullrich had the most useful answer, which I'll repeat here: The Universal Introduction on line 3 is invalid because x is free in the active assumption x = 0. Thank you for finding the error!