Undecidable

A statement in formal logic is called undecidable if there is no proof or disproof of the statement in formal logic. A common misconception is that undecidable statements have no truth value, but this statement is not true. For example, many set theorists now believe that the continuum hypothesis (which is known to be undeciable in Zermelo-Fraenkel set theory) is actually false.

As a more concrete example, suppose we had a "theory of colored shapes" <math>T</math> where the objects were colored shapes (red triangles, blue squares, etc), and the possible atomic sentences were of the form "shape <math>S</math> is a square." Since we do not have the language to state "shape <math>S</math> is red" then any statement of this form is undecidable in <math>T</math>, though it could be true or false in some larger theory <math>T'</math>.

Famous Undecidable Statements

• Axiom of Choice
• Banach-Tarski paradox
• Church-Turing thesis
• Continuum hypothesis
• Existence of large cardinals
• Halting problem
• König's lemma
• Lefschetz principle
• Liar's paradox
• Ramsey theory involving infinite sets
• Russell's paradox
• Zeno's paradox