Difference between revisions of "Gödel's incompleteness theorems"
Karl Jones (Talk | contribs) |
Karl Jones (Talk | contribs) (→Second incompleteness theorem o) |
||
| (One intermediate revision by the same user not shown) | |||
| Line 13: | Line 13: | ||
For any such system, there will always be statements about the natural numbers that are true, but that are unprovable within the system. | For any such system, there will always be statements about the natural numbers that are true, but that are unprovable within the system. | ||
| − | == Second incompleteness theorem | + | == Second incompleteness theorem == |
The second incompleteness theorem, an extension of the first, shows that such a system cannot demonstrate its own consistency. | The second incompleteness theorem, an extension of the first, shows that such a system cannot demonstrate its own consistency. | ||
| Line 22: | Line 22: | ||
* [[Axiomatic system]] | * [[Axiomatic system]] | ||
* [[Computer program]] | * [[Computer program]] | ||
| + | * [[Kurt Gödel]] | ||
| + | * [[Gödel's completeness theorem]] | ||
| + | * [[Gödel's speed-up theorem]] | ||
| + | * [[Gödel, Escher, Bach]] | ||
* [[Hilbert's second problem]] | * [[Hilbert's second problem]] | ||
* [[Impossible Programs]] | * [[Impossible Programs]] | ||
| − | * [[ | + | * [[Löb's Theorem]] |
* [[Mathematical logic]] | * [[Mathematical logic]] | ||
| + | * [[Minds, Machines and Gödel]] | ||
| + | * [[Münchhausen trilemma]] | ||
* [[Natural number]] | * [[Natural number]] | ||
| + | * [[Non-standard model of arithmetic]] | ||
* [[Philosophy of mathematics]] | * [[Philosophy of mathematics]] | ||
| + | * [[Proof theory]] | ||
| + | * [[Provability logic]] | ||
| + | * [[Tarski's undefinability theorem]] | ||
| + | * [[Theory of everything#Gödel's incompleteness theorem]] | ||
| + | * [[Third Man Argument]] | ||
* [[Uncertainty]] | * [[Uncertainty]] | ||
Latest revision as of 13:35, 21 May 2016
Gödel's incompleteness theorems are two theorems of mathematical logic that establish inherent limitations of all but the most trivial axiomatic systems capable of doing arithmetic.
Contents
Description
The theorems, proven by Kurt Gödel in 1931, are important both in mathematical logic and in the philosophy of mathematics.
The two results are widely, but not universally, interpreted as showing that David Hilbert's program to find a complete and consistent set of axioms for all mathematics is impossible, giving a negative answer to Hilbert's second problem.
First incompleteness theorem
The first incompleteness theorem states that no consistent system of axioms whose theorems can be listed by an "effective procedure" (e.g., a computer program, but it could be any sort of algorithm) is capable of proving all truths about the relations of the natural numbers (arithmetic).
For any such system, there will always be statements about the natural numbers that are true, but that are unprovable within the system.
Second incompleteness theorem
The second incompleteness theorem, an extension of the first, shows that such a system cannot demonstrate its own consistency.
See also
- Algorithm
- Axiomatic system
- Computer program
- Kurt Gödel
- Gödel's completeness theorem
- Gödel's speed-up theorem
- Gödel, Escher, Bach
- Hilbert's second problem
- Impossible Programs
- Löb's Theorem
- Mathematical logic
- Minds, Machines and Gödel
- Münchhausen trilemma
- Natural number
- Non-standard model of arithmetic
- Philosophy of mathematics
- Proof theory
- Provability logic
- Tarski's undefinability theorem
- Theory of everything#Gödel's incompleteness theorem
- Third Man Argument
- Uncertainty
External links
- Gödel's incompleteness theorems @ Wikipedia
