Gödel's first incompleteness theorem:
"To every ω-consistent recursive class κ of formulas, there correspond recursive class-signs r such that neither (vGenr) nor Neg(vGenr) belongs to Flg(κ), where v is the free variable of r" (Gödel 1931).
I don't have much to say on this one so let's take a look at a more understandable version found in Wikipedia, quoted from Kleene 1967, p. 250 (Stephen Cole Kleene, 1967, Mathematical Logic. Reprinted by Dover, 2002. ISBN 0-486-42533-9.):
"Any effectively generated theory capable of expressing elementary arithmetic cannot be both consistent and complete. In particular, for any consistent, effectively generated formal theory that proves certain basic arithmetic truths, there is an arithmetical statement that is true, but not provable in the theory."
Now, I will make an attempt to outline the proof in the perspective of a machine.
Assuming that there is a truth machine capable of determining the truth of every statement S recognizable by the machine. Let tM be this truth machine, and let tM(S) denote the truth of a statement S given as an input to tM. In this case, tM(S) will return either "true" or "false". It will return "true" if the statement is true, and "false" if the statement is false. Let LtM denote the set of statements recognized by machine tM; in this case, S ∊ LtM.
Now, what if we are given this statement:
G = "tM will never say G is true", G ∊ LtM.
- If tM(G) = "true", then this means that statement G does not hold, and G is therefore false. In this case, tM has just returned the wrong answer.
- In order for tM to be correct about G, tM should not return "true" for statement G. It therefore follows that what is being stated in G is the truth that tM cannot return "true" for statement G. This makes statement G true, but tM cannot say that it is true.
The explanation above shows that there exists a true statement in which tM cannot say that it is true. Relating this to the paraphrased version of the theorem above, tM represents the formal theory, and G corresponds to a true but not provable arithmetical statement in the theory.
This theorem has controversial philosophical consequences since it follows that not all true statements in a particular formal system are provable under that system. Extend this to mathematics as a formal system, and you might realize that not all true mathematical statements are provable under mathematics. Similarly, if you consider courtroom language as a formal system, then there exists true statements in the witness stand that are not provable using the courtroom language. However, Gödel's first incompleteness theorem doesn't exactly mean that there are certain truths that are not provable, since essentially it only exposes limitations in the "proving power" of formal systems. At least, one can see that in the attempt of proving everything that are considered true poses the risk of facing the infinite and confronting the limitations of the human mind (that is the case if you consider the human mind as a formal system).
If you think there is something wrong with the above's attempt, just ignore this article and check this reference instead:
Rudy Rucker, 2004, Infinity and the Mind: The Science and Philosophy of the Infinite (Princeton Science Library).
