How does Kurt Godel`s Theorem work?

Answer 1

Gödel's incompleteness theorems are two celebrated theorems about the limits of formal systems, proved by Kurt Gödel in 1931.


Gödel's first incompleteness theorem is perhaps the most celebrated result in mathematical logic. It states that

For any consistent formal theory that proves basic arithmetical truths, it is possible to construct an arithmetical statement that is true 1 but not provable in the theory. That is, any consistent theory of a certain expressive strength is incomplete.
Here, "theory" refers to a set of statements. (A theory is in general an infinitely large set.) A theory is "consistent" if it does not prove any contradictions. The meaning of "it is possible to construct" is that there is some mechanical procedure which, when given the axioms of the theory, produces another statement. That this statement is not provable in the theory means that it cannot be derived from statements of the theory using the standard rules of first-order logic. The statement produced by the procedure is often referred to as "the Gödel sentence" for that theory, though there are actually infinitely many statements that have the same property (of being true but not provable from the theory).

(Some technical hypotheses have been omitted here; the most important one is the stipulation that the theory be computably enumerable. That is, for Gödel's theorem to be applicable, it must be possible in principle to write a computer program that, if allowed to run forever, would print out all theorems of the theory, and nothing else.)

Second incompleteness theorem
Gödel's second incompleteness theorem can be stated as follows:

For any formal theory T including basic arithmetical truths and also certain truths about formal provability, T includes a statement of its own consistency if and only if T is inconsistent.
(Proof of the "if" part:) If T is inconsistent then anything can be proved, including that T is consistent. (Proof of the "only if" part:) If T is consistent then T does not include the statement of its own consistency. This follows from the first theorem.

There is a technical subtlety involved in the second incompleteness theorem, namely how exactly are we to express the consistency of T in the language of T. There are many ways to do this, and not all of them lead to the same result. In particular, different formalizations of the claim that T is consistent may be inequivalent in T, and some may even be provable. For example, first order arithmetic (Peano arithmetic or PA for short) can prove that the largest consistent subset of PA is consistent. But since PA is consistent, the largest consistent subset of PA is just PA, so in this sense PA "proves that it's consistent". What PA does not prove is that the largest consistent subset of PA is, in fact, the whole of PA. (The term "largest consistent subset of PA" is rather vague, but what is meant here is the largest consistent initial segment of the axioms of PA ordered according to some criteria, e.g. by "Gödel numbers", the numbers encoding the axioms as per the scheme used by Gödel mentioned above).

In case of Peano arithmetic or any familiar explicitly axiomatized theory T, it is possible to define the consistency "Con(T)" of T in terms of the non-existence of a number with a certain property, as follows: "there does not exist an integer coding a sequence of sentences, such that each sentence is either one of the (canonical) axioms of T, a logical axiom, or an immediate consequence of preceding sentences according to the rules of inference of first order logic, and such that the last sentence is a contradiction". However, for arbitrary T there is no canonical choice for Con(T).

Answer 2

There is an entire book on the subject (and probably several books); there is not enough space here to explain the whole thing. But generally, what it is about, is that there exist true theorems in any logic system that cannot be proven to be true. The subject is of more theoretical than practical interest, since most of the logical decisions that we make are really rather simple, and if needed, could be proven using nothing more exotic than a Venn diagram.

Answer 3

In 1931, the Czech-born mathematician Kurt Gödel demonstrated that within any given branch of mathematics, there would always be some propositions that couldn't be proven either true or false using the rules and axioms ... of that mathematical branch itself. You might be able to prove every conceivable statement about numbers within a system by going outside the system in order to come up with new rules and axioms, but by doing so you'll only create a larger system with its own unprovable statements. The implication is that all logical system of any complexity are, by definition, incomplete; each of them contains, at any given time, more true statements than it can possibly prove according to its own defining set of rules.

Gödel's Theorem has been used to argue that a computer can never be as smart as a human being because the extent of its knowledge is limited by a fixed set of axioms, whereas people can discover unexpected truths ... It plays a part in modern linguistic theories, which emphasize the power of language to come up with new ways to express ideas. And it has been taken to imply that you'll never entirely understand yourself, since your mind, like any other closed system, can only be sure of what it knows about itself by relying on what it knows about itself.

Answer 4

only suggested it means that there'll continuously be genuine statements which won't manage to be shown to be genuine, interior an axiomatic equipment. Godel's theory for the life of something godlike is likewise nicely worth analyzing. in spite of the actual undeniable fact that refuted by using Hume on the definition of words, it is an rather interesting logical hypothesis.

Answer 5

Read "Godel, Escher, Bach" by Douglas Hofstadter

Answer 6

since it has already been explained with jargon, i thought, i'd explain it in plain language-- Goedel's Theorum takes a paradox and assigns unique finite numbers to it in order to show in number theory that the theory itself is incomplete. It is incomplete because the paradox is that the statement is obviously true, but only when not true. A simple version of the paradox he used is: "This sentence is false."