In a certain town, all the men are either knights or knaves.
Knights always tell the truth, and never lie. Knaves always lie, and never tell the truth.
You meet three men, who introduce themselves:
What can you say about Allie, Billy, and Charlie?
"This sentence can never be proved"
Assume the statement is false. Then it can be proved.
Which means it can never be proved. Which means it must be true.
Obviously this is a contradiction.
Therefore the assumption is wrong, and the sentence cannot be false.
Therefore I have proved that it is true (proof by contradiction).
Therefore it can never be proved.
But I just proved it !!!
This is a paradox. Something is wrong. The problem is that "proved" is not well defined.
Suppose S is a system of mathematics that provides an explicit definition of proof (or a Turing machine that solves a particular problem).
"This sentence can never be proved using System S"
Assume the statement is false. Then it can be proved using System S.
Which means it can never be proved using System S. Which means it must be true.
Obviously this is a contradiction.
Therefore the assumption is wrong, and the sentence cannot be false.
Therefore I have proved that it is true (proof by contradiction).
Therefore it can never be proved using System S.
However, I did not prove it by using System S, but by using a different system.
This is the essence of Gödel's theorem. The critical sentence can be shown to be true, but it cannot be proved true within the system S. However, it can be proved by stepping outside the system. Thus the system S (and any logical or mathematical system) is incomplete.
Answer to knights and knaves:
No-one ever says he is a knave (a knight never lies, and a knave never tells the truth). Therefore Billy is lying, and must be a knave. Therefore Charlie is telling the truth, and must be a knight. We still don't know about Allie.
from Smullyan, R. M. (1978). What is the name of this book? Englewood Cliffs, NJ: Prentice Hall.