Godel Incompleteness Theorum

[Pigeon]

The Godel Incompleteness Theorem

In 1931 and while still in Vienna, Gödel published his incompleteness theorems in "Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme" (called in English "On Formally Undecidable Propositions of Principia Mathematica and Related Systems"). In that article, he proved for any computable axiomatic system that is powerful enough to describe the arithmetic of the natural numbers (e.g. the Peano axioms or Zermelo–Fraenkel set theory with the axiom of choice), that:

1. If the system is consistent, it cannot be complete.
2. The consistency of the axioms cannot be proven within the system.

These theorems ended a half-century of attempts, beginning with the work of Frege and culminating in Principia Mathematica and Hilbert's formalism, to find a set of axioms sufficient for all mathematics. The incompleteness theorems also imply that not all mathematical questions are computable.
In hindsight, the basic idea at the heart of the incompleteness theorem is rather simple. Gödel essentially constructed a formula that claims that it is unprovable in a given formal system. If it were provable, it would be false, which contradicts the idea that in a consistent system, provable statements are always true. Thus there will always be at least one true but unprovable statement. That is, for any computably enumerable set of axioms for arithmetic (that is, a set that can in principle be printed out by an idealized computer with unlimited resources), there is a formula that obtains in arithmetic, but which is not provable in that system. To make this precise, however, Gödel needed to solve several technical issues, such as encoding statements, proofs, and the very concept of provability into the natural numbers. He did this using a process known as Gödel numbering.
...
In 1951, Gödel demonstrated the existence of paradoxical solutions to Albert Einstein's field equations in general relativity. He gave this elaboration to Einstein as a present for his 70th birthday.[13] These "rotating universes" would allow time travel and caused Einstein to have doubts about his own theory. His solutions are known as the Gödel metric.

[Pigeon]

World's shortest explanation of Gödel's theorem

We have some sort of machine that prints out statements in some sort of language. It needn't be a statement-printing machine exactly; it could be some sort of technique for taking statements and deciding if they are true. But let's think of it as a machine that prints out statements.

In particular, some of the statements that the machine might (or might not) print look like these:

Code:

P*x (which means that the machine will print x)
NP*x (which means that the machine will never print x)
PR*x (which means that the machine will print xx)
NPR*x (which means that the machine will never print xx)

For example, NPR*FOO means that the machine will never print FOOFOO. NP*FOOFOO means the same thing. So far, so good.

Now, let's consider the statement NPR*NPR*. This statement asserts that the machine will never print NPR*NPR*.

Either the machine prints NPR*NPR*, or it never prints NPR*NPR*.

If the machine prints NPR*NPR*, it has printed a false statement. But if the machine never prints NPR*NPR*, then NPR*NPR* is a true statement that the machine never prints.

So either the machine sometimes prints false statements, or there are true statements that it never prints.

So any machine that prints only true statements must fail to print some true statements.

Or conversely, any machine that prints every possible true statement must print some false statements too.

The conclusion then translates directly: any machine or method that produces statements about arithmetic either sometimes produces false statements, or else there are true statements about arithmetic that it never produces. Because if it produces something like NPR*NPR* then it is wrong, but if it fails to produce NPR*NPR*, then that is a true statement that it has failed to produce.

So any machine or other method that produces only true statements about arithmetic must fail to produce some true statements.

http://blog.plover.com/math/Gdl-Smullyan.html

[Dr Exile]

So does that mean that National Public Radio is a false statement?

[SweetGrass]

Because if it produces something like NPR*NPR* then it is wrong, but if it fails to produce NPR*NPR*, then that is a true statement that it has failed to produce.

Is that like lying by omission?

BTW, I had always thought you had liked National Public Radio too.

[Egg]

Godel - some things are not provable.

[Pigeon]

Because if it produces something like NPR*NPR* then it is wrong, but if it fails to produce NPR*NPR*, then that is a true statement that it has failed to produce.

Is that like lying by omission?

It proves:

any machine or method that produces statements about arithmetic either sometimes produces false statements, or else there are true statements about arithmetic that it never produces.

"true statements about arithmetic that it never produces" meaning it is incomplete.

[Kat]

[Kat]

and

[Pam]

and

Hahahahaha that person should have got marks for coming up with the elephant in the way idea

[Kat]