Gödel's incompleteness theorems

From Wikipedia, the free encyclopedia
Jump to: navigation, search

Gödel's incompleteness theorems is the name given to two theorems, proved by Kurt Gödel in 1931. They are theorems in mathematical logic.

In a formal system, there are axioms. All axioms are assumed to be true, at any rate for the purpose of the logic. A theorem then comes up with other true statements from the axioms, using certain rules. A sequence of such statements is called a proof of a statement, because it shows that the statement is true, given the axioms.

Ideally, it should be possible to construct all true statements in the formal system in that manner. A system that has this property is called complete; one that does not is called incomplete. Another thing wanted of a theory is that there should be no contradictions. This means that it is not possible to prove that a statement is true and false at the same time. A system that does not include theories that allow this is called consistent.

Gödel said that every non-trivial formal system is either incomplete or inconsistent: [1]

  1. For a given (non-trivial) formal system, there will be statements that are true in that system, but which cannot be proved to be true inside the system.
  2. If a system can be proved to be complete using its own logic, then there will be a theorem in the system that is contradictory.

Most people think this shows that Hilbert's program to find a complete and consistent set of axioms for all of mathematics is impossible. This would give a negative answer to Hilbert's second problem.

References[change | change source]

  1. Nagel, Ernest; Newman, James Roy & Hofstadter, Douglas [1958] 2002. Gödel's proof, revised ed. ISBN 0-8147-5816-9 [1]