In Mathematical logic is a discipline within mathematics, studying formal systems in relation to the way they encode intuitive concepts of proof and computation as part of the foundations of mathematics. Although the layperson may think that mathematical logic is the logic of mathematics, the truth is rather that it more... mathematical logic, Gödel's incompleteness theorems are two celebrated theorems proved by Kurt Gödel [ kurt gøːdl], ( April 28, 1906 – January 14, 1978) was a logician, mathematician, and philosopher of mathematics. He was born in Brünn in Moravia, Austria-Hungary (now Brno in the Czech Republic), became a Czechoslovak citizen at age 12 when the... Kurt Gödel in 1931 is a common year starting on Thursday. Events January-March January 4 - Female aviator Elly Beinhorn begins her flight to Africa January 6 - Thomas Edison submits his last patent application. January 22 - Sir Isaac Isaacs sworn in as the first Australian-born Governor-General of Australia January 25 - Mohandas... 1931. Somewhat simplified, the first theorem states:

In any In mathematical logic, a formal system is said to be consistent if it doesnt contain a contradiction, or, more precisely, for no proposition are both and provable. A consistency proof is a formal proof that a formal system is consistent. The early development of mathematical proof theory was driven... consistent In logic, mathematics, and computer science, a formal system is a formal grammar used for modelling purposes. Formalization is the act of creating a formal system, in an attempt to capture the essential features of a real-world or conceptual system in formal language. For example, in some colleges the... formal system that is sufficiently strong to In epistemology, an axiom is a self-evident truth upon which other knowledge must rest, from which other knowledge is built up. Not all epistemologists agree that any axioms, understood in that sense, exist. In mathematics, an axiom is not a self-evident truth but rather, a formal logical expression... axiomatize the Natural number can mean either a positive integer (1, 2, 3, 4, ...) or a non-negative integer (0, 1, 2, 3, 4, ...). Natural numbers have two main purposes: they can be used for counting (there are 3 apples on the table), or they can be used for ordering (this is... natural numbers – that is, sufficiently strong to define the operations that collectively define the natural numbers – one can construct a true statement that can neither be proved nor disproved within the system itself.

This theorem is one of the most famous outside of mathematics, and one of the most misunderstood. It is a theorem in formal logic, and as such is easy to misinterpret. There are many statements that sound similar to Gödel's first incompleteness theorem, but are in fact not true, see misconceptions about Gödel's theorems below.

Gödel's second incompleteness theorem, which is proved by formalizing part of the proof of the first within the system itself, states:

No consistent system can be used to prove its own consistency.

This result was devastating to a philosophical approach to mathematics known as Hilbert's program. David Hilbert David Hilbert (January 23, 1862 – February 14, 1943) was a German mathematician born in Wehlau, near Königsberg, Prussia (now Znamensk, near Kaliningrad, Russia) who is recognized as one of the most influential mathematicians of the 19th and early 20th centuries. His own discoveries alone would have... David Hilbert proposed that the consistency of more complicated systems, such as Real analysis is that branch of mathematical analysis dealing with the set of real numbers and functions of real numbers. It can be seen as a rigorous version of calculus and studies concepts such as sequences and their limits, continuity, differentiation, integration and sequences of functions. The presentation of real... real analysis, could be proven in terms of simpler systems. Ultimately, the consistency of all of mathematics could be reduced to basic arithmetic. Gödel's second incompleteness theorem shows that basic arithmetic cannot be used to prove its own consistency, so it certainly cannot be used to prove the consistency of anything stronger.

Meaning of Gödel's theorems

Gödel's theorems are theorems in First-order predicate calculus or first-order logic (FOL) is a theory in symbolic logic that permits the formulation of quantified statements such as there is at least one X such that... or for any X, it is the case that..., where X is an element of a set called... first-order logic, and must ultimately be understood in that context. In formal logic, both mathematical statements and proofs are written in a symbolic language, one where we can mechanically check the validity of proofs so that there can be no doubt that a theorem follows from our starting list of axioms. In theory, such a proof can be checked by a computer, and in fact there are computer programs that will check the validity of proofs (this is called Automated theorem proving (currently the most important subfield of automated reasoning) is the proving of mathematical theorems by a computer program. Depending on the underlying logic, the problem of deciding the validity of a theorem varies from trivial to impossible. For the frequent case of propositional logic, the problem is... automated reasoning).

To be able to perform this process, we need to know what our axioms are. We could start with a finite set of axioms, such as in In mathematics, Euclidean geometry is the familiar kind of geometry on the plane or in three dimensions. Mathematicians sometimes use the term to encompass higher dimensional geometries with similar properties. Euclidean geometry sometimes means geometry in the plane which is also called plane geometry. Plane geometry is the topic of... Euclidean geometry, or more generally we could allow an infinite list of axioms, with the requirement that we can mechanically check for any given statement if it is an axiom from that set or not (an axiom schema). In computer science, this is known as having a In computability theory a countable set is called recursive, computable or decidable if we can construct an algorithm which terminates after a finite amount of time and decides whether a given element belongs to the set or not. A more general class of sets are called recursively enumerable sets. For... recursive set of axioms. While an infinite list of axioms may sound strange, this is exactly what's used in the usual axioms for the natural numbers, the In mathematics, the Peano axioms (or Peano postulates) are a set of first-order axioms proposed by Giuseppe Peano which determine the theory of Peano arithmetic (also known as first-order arithmetic). This theory constitutes a fundamental formalism for arithmetic, and the Peano axioms form a basis for the formalisation... Peano axioms: the inductive axiom is in fact an axiom schema - it states that if zero has any property and the successor of any natural number has that property, all natural numbers have that property - it does not specify which property and the only way to say in first-order logic that this is true of all properties is to have an infinite number of statements.

Gödel's first incompleteness theorem shows that any such system that allows you to define the natural numbers is necessarily incomplete: it contains statements that are neither provably true nor provably false.

The existence of an incomplete system is in itself not particularly surprising. For example, if you take In mathematics, Euclidean geometry is the familiar kind of geometry on the plane or in three dimensions. Mathematicians sometimes use the term to encompass higher dimensional geometries with similar properties. Euclidean geometry sometimes means geometry in the plane which is also called plane geometry. Plane geometry is the topic of... Euclidean geometry and you drop the In geometry, the parallel postulate, also called Euclids fifth postulate since it is the fifth postulate in Euclids Elements, is a distinctive axiom in what is now called Euclidean geometry. It states: If a line segment intersects two straight lines forming two interior angles on the same side... parallel postulate, you get an incomplete system (in the sense that system does not contain all the true statements). An incomplete system can mean simply that you haven't discovered all the necessary axioms.

What Gödel showed is that in most cases, such as in Traditionally, number theory is that branch of pure mathematics concerned with the properties of integers and contains many open problems that are easily understood even by non-mathematicians. More generally, the field has come to be concerned with a wider class of problems that arose naturally from the study of... number theory or Real analysis is that branch of mathematical analysis dealing with the set of real numbers and functions of real numbers. It can be seen as a rigorous version of calculus and studies concepts such as sequences and their limits, continuity, differentiation, integration and sequences of functions. The presentation of real... real analysis, you can never discover the complete list of axioms. Each time you add a statement as an axiom, there will always be another statement out of reach.

You can add an infinite number of axioms; for example, you can add all true statements about the natural numbers to your list of axioms, but such a list will not be a recursive set. Given a random statement, there will be no way to know if it is an axiom of your system. If I give you a proof, in general there will be no way for you to check if that proof is valid.

Gödel's theorem has another interpretation in the language of computer science. In first-order logic, theorems are In computability theory, often less suggestively called recursion theory, a countable set S is called recursively enumerable, computably enumerable, semi-decidable or provable if There is an algorithm that, when given an input — typically an integer or a tuple of integers or a sequence of characters —... recursively enumerable: you can write a computer program that will eventually generate any valid proof. You can ask if they satisfy the stronger property of being In computability theory a countable set is called recursive, computable or decidable if we can construct an algorithm which terminates after a finite amount of time and decides whether a given element belongs to the set or not. A more general class of sets are called recursively enumerable sets. For... recursive: can you write a computer program to definitively determine if a statement is true or false? Gödel's theorem says that in general you cannot.

Many logicians believe that Gödel's incompleteness theorems struck a fatal blow to David Hilbert David Hilbert (January 23, 1862 – February 14, 1943) was a German mathematician born in Wehlau, near Königsberg, Prussia (now Znamensk, near Kaliningrad, Russia) who is recognized as one of the most influential mathematicians of the 19th and early 20th centuries. His own discoveries alone would have... David Hilbert's program towards a universal mathematical formalism. The generally agreed upon stance is that the second theorem is what specifically dealt this blow. However some believe it was the first, and others believe that neither did.

Examples of undecidable statements

The existence of an undecidable statement within a formal system is not in itself a surprising phenomenon.

The subsequent combined work of Gödel and Paul Joseph Cohen (born April 2, 1934) is an American mathematician. He was born in Long Branch, New Jersey and graduated in 1950 from Stuyvesant High School in New York City. He is noted for inventing a technique called forcing which he used to show that neither the continuum hypothesis... Paul Cohen has given concrete examples of undecidable statements (statements which can be neither proven nor disproven): both the In mathematics, the axiom of choice is an axiom of set theory. It was formulated about a century ago by Ernst Zermelo and has remained controversial to this day. It states the following: Let X be a collection of non-empty sets. Then we can choose a member from each... axiom of choice and the In mathematics, the continuum hypothesis is a hypothesis about the possible sizes of infinite sets. Georg Cantor introduced the concept of cardinality to compare the sizes of infinite sets, and he showed that the set of integers is strictly smaller than the set of real numbers. The continuum hypothesis states... continuum hypothesis are undecidable in the standard axiomatization of Set theory is the mathematical theory of sets, which represent collections of abstract objects. It has a central role in modern mathematical theory, providing the basic language in which most of mathematics is expressed. For more information on set theory in Wikipedia, see: Set gives a basic introduction to elementary... set theory. These results do not require the incompleteness theorem.

In 1936 was a leap year starting on Wednesday (link will take you to calendar). Events January-February January 15 -- The first building to be completely covered in glass is completed in Toledo, Ohio, for the Owens-Illinois Glass Company. January 20 - Death of George V of the United Kingdom. His... 1936, Alan Turing, on the steps of the bus, with members of the Walton Athletic Club, 1946. Alan Mathison Turing (June 23, 1912–June 7, 1954) was a British mathematician, logician, cryptographer, and war hero, and is widely considered to be the father of computer science. With the Turing Test... Alan Turing proved that the In computability theory the halting problem is a decision problem which can be informally stated as follows: Given a description of an algorithm and its initial input, determine whether the algorithm, when executed on this input, ever halts (completes). The alternative is that it runs forever without halting. Alan Turing... halting problem—the question of whether or not a The Turing machine is an abstract machine introduced in 1936 by Alan Turing to give a mathematically precise definition of algorithm or mechanical procedure. As such it is still widely used in theoretical computer science, especially in complexity theory and the theory of computation. The thesis that states that Turing... Turing machine halts on a given program—is undecidable. This result was later generalised in the field of In mathematical logic and computer science, the recursive functions are a class of functions from natural numbers to natural numbers which are computable in some intuitive sense. In fact, in computability theory it is shown that the recursive functions are precisely the functions that can be computed by Turing machines... recursive functions to Rice's theorem which shows that all non-trivial decision problems are undecidable in a system that is In computability theory a programming language or any other logical system is called Turing-complete if it has a computational power equivalent to a universal Turing machine. In other words, the system and the universal Turing machine can emulate each other. (Under traditional hyphenation conventions, the adjective Turing-complete should... Turing-complete.

In 1973 was a common year starting on Monday. Events January January 1 - United Kingdom, Ireland, and Denmark enter the European Economic Community, now known as the European Union. January 3 - Columbia Broadcasting System (CBS) sells the New York Yankees for $10 million to a 12-person syndicate led by George... 1973, the In group theory, the Whitehead problem is the following question: Is every abelian group A with Ext1(A, Z) = 0 a free abelian group? The condition Ext1(A, Z) = 0 can be equivalently formulated as follows: whenever B is an abelian group and f : B → A is a... Whitehead problem in Group theory is that branch of mathematics concerned with the study of groups. Please refer to the Glossary of group theory for the definitions of terms used throughout group theory. See also list of group theory topics. History There are three historical roots of group theory: the theory of algebraic... group theory was shown to be undecidable in standard set theory. In For the album by Ash, see 1977 (album). Events January-February January 1 - First woman Episcopal priest ordained. January 6 - EMI sacks the Sex Pistols January 18 - Scientists identify a previously unknown bacterium as the cause of the mysterious legionnaires disease January 18 - Australia experiences its worst railway disaster... 1977, Kirby, Paris and Harrington proved that a statement in Combinatorics is a branch of mathematics that studies finite collections of objects that satisfy specified criteria, and is in particular concerned with counting the objects in those collections (enumerative combinatorics) and with deciding whether certain optimal objects exist (extremal combinatorics). One of the most prominent combinatorialists of recent times was... combinatorics, a version of the This article goes into technical details quite quickly. For a slightly gentler introduction see Ramsey theory. In combinatorics, Ramseys theorem states that in colouring a large complete graph, one will find complete subgraphs all of the same colour. In a precise statement, for any pair of positive integers (r... Ramsey theorem, is undecidable in the axiomatization of arithmetic given by the In mathematics, the Peano axioms (or Peano postulates) are a set of first-order axioms proposed by Giuseppe Peano which determine the theory of Peano arithmetic (also known as first-order arithmetic). This theory constitutes a fundamental formalism for arithmetic, and the Peano axioms form a basis for the formalisation... Peano axioms but can be proven to be true in the larger system of set theory. Kruskal's tree theorem, which has applications in computer science, is also undecidable from the Peano axioms but provable in set theory. Goodstein's theorem is a relatively simple statement about natural numbers that is undecidable in Peano arithmetic.

Gregory J. Chaitin (born 1947) is an American contemporary mathematician and computer scientist. Chaitin, beginning in the late 1960s, made important contributions to algorithmic information theory, in particular a new incompleteness theorem similar in spirit to Gödels incompleteness theorem. In 1995 he was given the degree of doctor... Gregory Chaitin produced undecidable statements in Algorithmic information theory is a field of study which attempts to capture the concept of complexity by using tools from theoretical computer science. The chief idea is to define the complexity (or Kolmogorov complexity) of a string as the length of the shortest program which outputs that string. Strings that... algorithmic information theory and in fact proved his own incompleteness theorem in that setting.

One of the first problems suspected to be undecidable was the In abstract algebra, the word problem for groups is the problem of deciding whether two given words of a presentation of a group represent the same element. There exists no general algorithm for this problem, as was shown by Pyotr Sergeyevich Novikov. The proof was announced in 1952 and published... word problem for groups, first posed by Max Dehn (November 13, 1878 – June 27, 1952) was a German mathematician. He studied the foundations of geometry with Hilbert at Göttingen in 1899, and obtained a proof of the Jordan curve theorem for polygons. In 1900 he wrote his dissertation on the role of the Legendre angle... Max Dehn in 1911 is a common year starting on Sunday (click on link for calendar). Events January-June January 1 - Northern Territory is separated from South Australia January 3 - In London, in what becomes known as the Siege of Sidney Street, the Metropolitan Police and the Scots Guards engage in a shootout... 1911, which states that there is a finitely presented In mathematics, a group is a set, together with a binary operation, such as multiplication or addition, satisfying certain axioms, detailed below. The branch of mathematics which studies groups is called group theory. The historical origin of group theory goes back to the works of Evariste Galois (1830), concerning the... group that has no algorithm to state whether two words are equivalent. It was not proven to be undecidable until Summary of notable events in 1952. Events January events January 8 - West Germany has 8 million refugees inside its borders. January 24 - Sudden heavy snowfall in Algeria. January 24 - Vincent Massey sworn in as first Canada-born Governor-General of Canada. February events February 2 - A Cuba moving northeast. The... 1952.

Misconceptions about Gödel's theorems

Since Gödel's first incompleteness theorem is so famous, it has given rise to many misconceptions. They are refuted here:

1. The theorem does not imply that every interesting axiom system is incomplete. For example, In mathematics, Euclidean geometry is the familiar kind of geometry on the plane or in three dimensions. Mathematicians sometimes use the term to encompass higher dimensional geometries with similar properties. Euclidean geometry sometimes means geometry in the plane which is also called plane geometry. Plane geometry is the topic of... Euclidean geometry can be axiomatized so that it is a complete system. (In fact, Euclid of Alexandria (Greek: Eukleides) (circa 365–275 BC) was a Greek mathematician, now known as the father of geometry. His most famous work is Elements, widely considered to be historys most successful textbook. Within it, the properties of geometrical objects and integers are deduced from a small... Euclid's original axioms are pretty close to being a complete axiomatization. The missing axioms express properties that seem so obvious that it took the emergence of the idea of a formal proof before their absence was noticed.)
2. The theorem only applies to systems that allow you to define the natural numbers as a set. It is not sufficient that the system contain the natural numbers. You must also be able to express the concept "x is a natural number" using your axioms and first-order logic. There are plenty of systems that contain the natural numbers and are complete. For example both the Please refer to Real vs. nominal in economics for the concept of real numbers in economics. In mathematics, the real numbers are intuitively defined as numbers that are in one-to-one correspondence with the points on an infinite line—the number line. The term real number is a... real numbers and The complex numbers are an extension of the real numbers, in which all non-constant polynomials have roots. The complex numbers contain a number , the imaginary unit, with , i.e., is a square root of . Every complex number can be represented in the form , where and are real numbers called... complex numbers have complete axiomatizations.

Discussion and implications

The incompleteness results affect the Philosophy of mathematics is that branch of philosophy which attempts to answer questions such as: why is mathematics useful in describing nature?, in which sense, if any, do mathematical entities such as numbers exist? and why and how are mathematical statements true?. The various approaches to answering these questions will... philosophy of mathematics, particularly viewpoints like Mathematical logic is a discipline within mathematics, studying formal systems in relation to the way they encode intuitive concepts of proof and computation as part of the foundations of mathematics. Although the layperson may think that mathematical logic is the logic of mathematics, the truth is rather that it more... formalism, which uses formal logic to define its principles. One can paraphrase the first theorem as saying that "we can never find an all-encompassing axiomatic system which is able to prove all mathematical truths, but no falsehoods."

On the other hand, from a strict formalist perspective this paraphrase would be considered meaningless because it presupposes that mathematical "truth" and "falsehood" are well-defined in an absolute sense, rather than relative to each formal system.

The following rephrasing of the second theorem is even more unsettling to the The term foundations of mathematics is sometimes used for certain fields of mathematics itself, namely for mathematical logic, axiomatic set theory, proof theory, model theory, and recursion theory. The search for foundations of mathematics is however also the central question of the philosophy of mathematics: on what ultimate basis can... foundations of mathematics:

If an axiomatic system can be proven to be consistent from within itself, then it is inconsistent.

Therefore, in order to establish the consistency of a system S, one needs to utilize some other system T, but a proof in T is not completely convincing unless T's consistency has already been established without using S. The consistency of the In mathematics, the Peano axioms (or Peano postulates) are a set of first-order axioms proposed by Giuseppe Peano which determine the theory of Peano arithmetic (also known as first-order arithmetic). This theory constitutes a fundamental formalism for arithmetic, and the Peano axioms form a basis for the formalisation... Peano axioms for Natural number can mean either a positive integer (1, 2, 3, 4, ...) or a non-negative integer (0, 1, 2, 3, 4, ...). Natural numbers have two main purposes: they can be used for counting (there are 3 apples on the table), or they can be used for ordering (this is... natural numbers for example can be proven in Set theory is the mathematical theory of sets, which represent collections of abstract objects. It has a central role in modern mathematical theory, providing the basic language in which most of mathematics is expressed. For more information on set theory in Wikipedia, see: Set gives a basic introduction to elementary... set theory, but not in the theory of natural numbers alone. This provides a negative answer to problem number 2 on David Hilbert David Hilbert (January 23, 1862 – February 14, 1943) was a German mathematician born in Wehlau, near Königsberg, Prussia (now Znamensk, near Kaliningrad, Russia) who is recognized as one of the most influential mathematicians of the 19th and early 20th centuries. His own discoveries alone would have... David Hilbert's famous list of important open questions in mathematics (called Hilbert's problems).

In principle, Gödel's theorems still leave some hope: it might be possible to produce a general Flowcharts are often used to represent algorithms. An algorithm (the word is derived from the name of the Persian mathematician Al-Khwarizmi), is a finite set of well-defined instructions for accomplishing some task which, given an initial state, will terminate in a corresponding recognizable end-state (contrast with heuristic... algorithm that for a given statement determines whether it is undecidable or not, thus allowing mathematicians to bypass the undecidable statements altogether. However, the negative answer to the The Entscheidungsproblem (German: decision problem) is the challenge in symbolic logic to find a general algorithm which decides for given first-order statements whether they are universally valid or not. In 1936, working independently, Alonzo Church and Alan Turing both showed that this is impossible. As a consequence, it is... Entscheidungsproblem shows that no such algorithm exists.

There are some who hold that a statement that is unprovable within a deductive system may be quite provable in a metalanguage. And what cannot be proven in that metalanguage can likely be proven in a meta-metalanguage, recursively, Ad infinitum is a Latin phrase meaning to infinity. In context, it usually means continue forever, and thus can be used to describe a non_terminating process, a non_terminating repeating process, or a set of instructions to be repeated forever, among other uses. Examples include: The series 2, 4, 6, 8... ad infinitum, in principle. By invoking a sort of super Theory of Types with an axiom of Reducibility -- which by an inductive assumption applies to the entire stack of languages -- one may, for all practical purposes, overcome the obstacle of incompleteness.

Note that Gödel's theorems only apply to sufficiently strong axiomatic systems.

"Sufficiently strong" means that the theory contains enough arithmetic to carry out the coding constructions needed for the proof of the first incompleteness theorem. Essentially, all that is required are some basic facts about addition and multiplication as formalized, e.g., in Robinson arithmetic Q. There are even weaker axiomatic systems that are consistent and complete, for instance Presburger arithmetic is the first-order theory of the natural numbers with addition. It is not as powerful as the Peano axioms because multiplication is omitted. In fact, Mojzesz Presburger proved in 1929 that there is an algorithm which decides for any given statement in Presburger arithmetic whether it is... Presburger arithmetic which proves every true first-order statement involving only addition.

The axiomatic system may consist of infinitely many axioms (as first-order Peano arithmetic does), but for Gödel's theorem to apply, there has to be an effective algorithm which is able to check proofs for correctness. For instance, one might take the set of all first-order sentences which are true in the standard model of the Natural number can mean either a positive integer (1, 2, 3, 4, ...) or a non-negative integer (0, 1, 2, 3, 4, ...). Natural numbers have two main purposes: they can be used for counting (there are 3 apples on the table), or they can be used for ordering (this is... natural numbers. This system is complete; Gödel's theorem does not apply because there is no effective procedure that decides if a given sentence is an axiom. In fact, that this is so is a consequence of Gödel's first incompleteness theorem.

Another example of a specification of a theory to which Gödel's first theorem does not apply can be constructed as follows: order all possible statements about natural numbers first by length and then In mathematics, the lexicographical order, or dictionary order, is a natural order structure of the cartesian product of two ordered sets. Given A and B, two ordered sets, the lexicographical order in the cartesian product A × B is defined as (a,b) ≤ (a′,b′) if and only... lexicographically, start with an axiomatic system initially equal to the Peano axioms, go through your list of statements one by one, and, if the current statement cannot be proven nor disproven from the current axiom system, add it to that system. This creates a system which is complete, consistent, and sufficiently powerful, but not In computability theory, often less suggestively called recursion theory, a countable set S is called recursively enumerable, computably enumerable, semi-decidable or provable if There is an algorithm that, when given an input — typically an integer or a tuple of integers or a sequence of characters —... recursively enumerable.

Gödel himself only proved a technically slightly weaker version of the above theorems; the first proof for the versions stated above was given by John Barkley Rosser Sr. (1907-1989) was an American logician, a student of Alonzo Church, and known for his part in the Church-Rosser theorem, in lambda calculus. He also developed what is now called the Rosser sieve, in number theory. He was later Director of the Army Mathematics Research... J. Barkley Rosser in 1936.

In essence, the proof of the first theorem consists of constructing a statement p within a formal axiomatic system that can be given a meta-mathematical interpretation of:

p = "This statement cannot be proven"

As such, it can be seen as a modern variant of the In philosophy and logic, the liar paradox encompasses paradoxical statements such as: I am lying now. or This statement is false. To avoid having a sentence directly refer to its own truth value, one can also construct the paradox as follows: The following sentence is true. The preceding sentence is... Liar paradox. Unlike the Liar sentence, p does not directly refer to itself; the above interpretation can only be "seen" from outside the formal system.

If the axiomatic system is consistent, Gödel's proof shows that p (and its negation) cannot be proven in the system. Therefore p is "true" (p claims to be not provable, and it is not provable) yet it cannot be formally proved in the system. Note that adding p to the axioms of the system would not solve the problem: there would be another Gödel sentence for the enlarged theory.

An easy solution for provability in and of itself is to insist that in a truly consistent proof-theorem system each true theorem should actually explicitly contain its own proof. It is obvious that this Prior's solution does not injure completeness.

Sir Roger Penrose OM (born August 8, 1931) is an English mathematical physicist. He is highly regarded for his work in mathematical physics, in particular his contributions to cosmology. He is also a recreational mathematician and controversial philosopher. In 1967, Penrose invented twistor theory which maps geometric objects in Minkowski... Roger Penrose claims that this (alleged) difference between "what can be mechanically proven" and "what can be seen to be true by humans" shows that human intelligence is not mechanical in nature. This claim is also addressed by John Randolph Lucas (born 18 June 1929) is a philosopher. He was for 36 years, until his retirement in 1996, a Fellow and Tutor of Merton College, Oxford, and remains an emeritus member of the University Faculty of Philosophy. As an undergraduate, he studied first mathematics, then Greats (Philosophy and... JR Lucas in Minds, Machines and Gödel (http://users.ox.ac.uk/~jrlucas/mmg.html).

This view is not widely accepted, because as stated by Marvin Minsky Marvin Lee Minsky (born August 9, 1927), sometimes affectionately known as Old Man Minsky, is an American scientist in the field of artificial intelligence (AI), co-founder of MITs AI laboratory, and author of several texts on AI and philosophy. He was born in New York, where... Marvin Minsky, human intelligence is capable of error and of understanding statements which are in fact inconsistent or false. However, Marvin Minsky has reported that Kurt Gödel [ kurt gøːdl], ( April 28, 1906 – January 14, 1978) was a logician, mathematician, and philosopher of mathematics. He was born in Brünn in Moravia, Austria-Hungary (now Brno in the Czech Republic), became a Czechoslovak citizen at age 12 when the... Kurt Gödel told him personally that he believed that human beings had an intuitive, not just computational, way of arriving at truth and that therefore his theorem did not limit what can be known to be true by humans.

The position that the theorem shows humans to have an ability that transcends formal logic can also be criticized as follows: We do not know whether the sentence p is true or not, because we do not (and can not) know whether the system is consistent. So in fact we do not know any truth outside of the system. All we know is the following statement:

Either p is unprovable within the system, or the system is inconsistent.

This statement is easily proved within the system. In fact, such a proof will now be given.

Proof sketch for the first theorem

The main problem in fleshing out the above mentioned proof idea is the following: in order to construct a statement p that is equivalent to "p cannot be proved", p would have to somehow contain a reference to p, which could easily give rise to an infinite regress. Gödel's ingenious trick, which was later used by Alan Turing, on the steps of the bus, with members of the Walton Athletic Club, 1946. Alan Mathison Turing (June 23, 1912–June 7, 1954) was a British mathematician, logician, cryptographer, and war hero, and is widely considered to be the father of computer science. With the Turing Test... Alan Turing to solve the The Entscheidungsproblem (German: decision problem) is the challenge in symbolic logic to find a general algorithm which decides for given first-order statements whether they are universally valid or not. In 1936, working independently, Alonzo Church and Alan Turing both showed that this is impossible. As a consequence, it is... Entscheidungsproblem, will be described below.

To begin with, every formula or statement that can be formulated in our system gets a unique number, called its In formal number theory a Gödel numbering is a function which assigns to each symbol and formula of some formal language a unique natural number called a Gödel number (GN). The concept was first used by Kurt Gödel for the proof of his incompleteness theorem. Definition Given... Gödel number. This is done in such a way that it is easy to mechanically convert back and forth between formulas and Gödel numbers. Because our system is strong enough to reason about numbers, it is now also possible to reason about formulas.

A formula F(x) that contains exactly one free variable x is called a statement form. As soon as x is replaced by a specific number, the statement form turns into a In law, good faith (in Latin, bona fides) is the mental and moral state of honest, even if objectively unfounded, conviction as to the truth or falsehood of a proposition or body of opinion, or as to the rectitude or depravity of a line of conduct. One who acts in... bona fide statement, and it is then either provable in the system, or not. Statement forms themselves are not statements and therefore cannot be proved or disproved. But every statement form F(x) has a Gödel number which we will denote by G(F). The choice of the free variable used in the form F(x) is not relevant to the assignment of the Gödel number G(F).

By carefully analyzing the axioms and rules of the system, one can then write down a statement form P(x) which embodies the idea that x is the Gödel number of a statement which can be proved in our system. Formally: P(x) can be proved if x is the Gödel number of a provable statement, and its negation ~P(x) can be proved if it isn't. (While this is good enough for this proof sketch, it is technically not completely accurate. See Gödel's paper for the problem and Rosser's paper for the resolution. The key word is "omega-consistency".)

Now comes the trick: a statement form F(x) is called self-unprovable if the form F, applied to its own Gödel number, is not provable. This concept can be defined formally, and we can construct a statement form SU(z) whose interpretation is that z is the Gödel number of a self-unprovable statement form. Formally, SU(z) is defined as: z = G(F) for some particular form F(x), and y is the Gödel number of the statement F(G(F)), and ~P(y). Now the desired statement p that was mentioned above can be defined as:

p = SU(G(SU)).

Intuitively, when asking whether p is true, we ask: "Is the property of being self-unprovable itself self-unprovable?" This is very reminiscent of the The Barber paradox is a paradox that relates to mathematical logic and set theory. The paradox considers a town with a male barber who shaves daily every man who does not shave himself, and no one else. Such a town cannot exist: If the barber does not shave himself, he... Barber paradox about the barber who shaves precisely those people who don't shave themselves: does he shave himself?

We will now assume that our axiomatic system is consistent.

If p were provable, then SU(G(SU)) would be true, and by definition of SU, z = G(SU) would be the Gödel number of a self-unprovable statement form. Hence SU would be self-unprovable, which by definition of self-unprovable means that SU(G(SU)) is not provable, but this was our p: p is not provable. This contradiction shows that p cannot be provable.

If the negation of p= SU(G(SU)) were provable, then by definition of SU this would mean that z = G(SU) is not the Gödel number of a self-unprovable form, which implies that SU is not self-unprovable. By definition of self-unprovable, we conclude that SU(G(SU)) is provable, hence p is provable. Again a contradiction. This one shows that the negation of p cannot be provable either.

So the statement p can neither be proved nor disproved within our system.

Proof sketch for the second theorem

Let p stand for the undecidable sentence constructed above, and let's assume that the consistency of the system can be proven from within the system itself. We have seen above that if the system is consistent, then p is not provable. The proof of this implication can be formalized in the system itself, and therefore the statement "p is not provable", or "not P(p)" can be proven in the system.

But this last statement is equivalent to p itself (and this equivalence can be proven in the system), so p can be proven in the system. This contradiction shows that the system must be inconsistent.

See also

• Consistency has three technical meanings: In mathematics and logic, as well as in theoretical physics, it refers to the proposition that a formal theory or a physical theory contains no contradictions. See consistency proof. In statistics, consistency (statistics) refers to a property of estimators. In decision theory, a voting system... Consistency
• A self-reference occurs when an object refers to itself. Reference is possible when there are two logical levels, a level and a meta-level. It is most commonly used in mathematics, philosophy, computer programming, and linguistics. Self-referential statements can lead to paradoxes (but see antinomy for limits on... Self-reference
• Logicism is one of the schools of thought in the Philosophy of mathematics. Logicism is the theory that mathematics is an extension of logic and therefore all mathematics is reducible to logic. Modern philosophers believed that proof of this theory was the means of banishing the befuddlement of natural language... Logicism
• Minds, Machines and Gödel
• Löb's Theorem

External links and references

• K. Gödel: Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme, I. (http://home.ddc.net/ygg/etext/godel/) Monatshefte für Mathematik und Physik, 38 (1931), pp. 173-198. Translated in van Heijenoort: From Frege to Gödel. Harvard University Press, 1971.
• B. Rosser: Extensions of some theorems of Gödel and Church. Journal of Symbolic Logic, 1 (1936), N1, pp. 87-91
• Hao Wang: A Logical Journey: From Gödel to Philosophy Bradford Books (January 10, 1997) ISBN 0262231891
• Kārlis Podnieks: Around Goedel's Theorem, http://www.ltn.lv/~podnieks/gt.html
• D. Hofstadter: Gödel, Escher, Bach: An Eternal Golden Braid, 1979, ISBN 0465026850. (1999 reprint: ISBN 0465026567).
• Ernest Nagel, James Roy Newman, Douglas R. Hofstadter: Gödel's Proof, revised edition (2002). ISBN 0814758169.
• Hilbert's second problem (http://aleph0.clarku.edu/~djoyce/hilbert/problems.html#prob2) (English translation)
• Norbert Domeisen, Logik der Antinomien. Bern etc.: Peter Lang. 142 S. 1990. (ISBN 3-261-04214-1), Zentralblatt MATH (http://www.emis.de/cgi-bin/zmen/ZMATH/en/quick.html?first=1&maxdocs=3&type=html&an=0724.03003&format=complete)