Godel's Theorem, What's it really saying?

[IndianDruid]

Hi,
So I was just going through my copy of The Emperor's New Mind, and I'm having a little difficulty accepting Godel's theorem , at least the way Penrose has presented it.

If I'm not wrong, the theorem asserts that there exist certain mathematical statements within a formal axiomatic system that are true, but cannot be proven through the axioms and rules of procedure laid down in the formal system. This is, as I understand it, a blow to formalism because it implies that insight or intelligence is needed to demonstrate truth for non-computable ( or non-recursive ?? I'm really confused as to where the difference lies ) mathematical statements.

Two problems here, first, why is it unreasonable to adopt the position that those statements are neither true nor false. The argument Penrose presents is reductio ad absurdum. He shows that it cannot be false because that would be absurd, hence it has to be true. But doesn't a true statement which is not provable also ring absurdity ? If I remember correctly, there was an active philosophical stance at the time which asserted that we cannot speak of truth or falsity unless it has been established to be so one way or another. So is it wholly unreasonable to say that those statements are neither true nor false ?
Further, doesn't Godel's theorem also establish something about the undecidability of some problem( that the problem cannot be proven nor disproven, ) ? Is this really different from ' neither true nor false'? I also don't really understand how the two 'parts' of Godel's theorem are related, if they are at all.

P.S I hope this isn't in the wrong place, but I couldn't find a mathematical philosophy thread in PhysicsForums.

 

[disregardthat]

In mathematical logic you have to distinguish between your formal syntax, that is your theory (such as the axioms of peano arithmetic, ZFC, or any other kind of axiomatic system), and your model. Your theory will contain propositions, which we do not call true or false, but we call them derivable (or provable) if they follow formally from your set of axioms using first order logic.

Your model on the other hand is a set satisfying the axioms of your theory. It comes equipped with an interpretation function, which to every proposition assigns either 1 or 0 (true or false). For example, the natural numbers $\mathbb{N}$ is a model of the peano axioms. Every possible proposition in peano arithmetic will either be true or false in this model. However...

Godels incompleteness theorem shows (more or less) that any consistent theory capable of expressing peano arithmetic will have true propositions which are not derivable. This means that in any model of peano arithmetic (or a stronger theory) there will be a true proposition which is not derivable in the theory. So truth refers to a model, and derivability refers to the theory.

 

[HallsofIvy]

I prefer not to use the words "true" and "false" in relation to mathematics. What Gödel's theorem says that in any consistent axiomatic system, large enough to encompass the natural numbers, there exist a statement that can be stated in terms of the system, but can be neither proven nor disproven.

 

[disregardthat]

I prefer not to use the words "true" and "false" in relation to mathematics. What Gödel's theorem says that in any consistent axiomatic system, large enough to encompass the natural numbers, there exist a statement that can be stated in terms of the system, but can be neither proven nor disproven.

Correct me if I'm wrong, but Godels theorem is significantly stronger than this. Godels theorem shows that there are propositions which are true in any model, despite being unprovable. Independence proofs came much earlier. Despite being impossible to prove or disprove, there may be models in which they are true, and models in which they are false. Examples are the Axiom of choice and the Continuum hypothesis.

 

[micromass]

Correct me if I'm wrong, but Godels theorem is significantly stronger than this. Godels theorem shows that there are propositions which are true in any model, despite being unprovable.

That is incorrect. Godels completeness theorem states that if something is true in any model, then it is provable.
http://en.wikipedia.org/wiki/Gödel's_completeness_theorem

 

[disregardthat]

That is incorrect. Godels completeness theorem states that if something is true in any model, then it is provable.
http://en.wikipedia.org/wiki/Gödel's_completeness_theorem

Ah, right.

 

[HallsofIvy]

Actually, I would like for both of you to state exactly what you mean by "true" here. How would you tell if a statement is true, other than by proving it?

 

[micromass]

Actually, I would like for both of you to state exactly what you mean by "true" here. How would you tell if a statement is true, other than by proving it?

I mean the theory of semantic consequences. A formula is a semantic consequence of a theory if it is true in all models of the theory. What "true" means in this context can be made rigorous. http://euclid.trentu.ca/math/sb/pcml/pcml-16.pdf Chapter 6

 

[disregardthat]

I personally have always found it kind of fishy speaking of models of ZFC. Models are defined as sets satisfying certain conditions, like an interpretation satisfying the axiom schema of ZFC. But even speaking of, for example, the first countable ordinal $\omega$ as a model for ZFC without axiom of infinity suddenly becomes kind of circular. Not exactly, it's hard to point at. But what is this $\omega$? Suddenly you find yourself entrenched within ZFC (or weaker) to even speak of models for ZFC. So what can this model really tell you about ZFC w/o infinity? Or oppositely, what can ZFC w/o infinity tell you about $\omega$? To interpret a statement from ZFC w/o infinity in $\omega$ requires the theory of ZFC in the first place.

 

[lavinia]

I am starting to read about Godel's proof with a friend. We are using "Godel's Incompleteness Theorem's" by Smullyan.

In the first section of the book (pgs. 1- 13) the author proves what he calls the Abstract Form of Godel's Proof.

In abstract, the first incompleteness theorem shows that there are sentences that are true but not provable in certain formal languages.

These languages must satisfy a list of properties, all of which are intuitive such as the language has only countably many expressions; the language is correct i.e. a sentence that is provable is true, and a sentence that is refutable is false.

In this Abstract Form of the Proof, the author assumes that predicates are functions of the natural numbers so that for every predicate,F, and natural number,n, the expression F(n) is a sentence in the language. He calls a set of natural numbers "nameable" if there is a predicate, F, such that the sentence ,F(n), is true if and only if n is in the set.

Choose a bijection between the set of all expressions and the positive integers. This is called a Godel numbering.
If F_n is the expression whose Godel number is n, define the function Diagonal(n) to be the Godel number of the expression F_n(n). (If F_n is a predicate, then F_n(n) is a sentence.)

Finally, define for any set of positive integers,S, the set S* of all numbers such that Diagonal(n) is in S.

Now let P be the set of Godel numbers of provable sentences, and ~P its complement.( ~P is just the Godel numbers of all expressions that are not provable sentences.)

Assume that (~P)* is nameable.

With this last assumption, that (~P)* is nameable, the proof is quick.

Proof: If F is the predicate that names (~P)* then F(n) is true if and only if n is in (~P)* That is if and only of Diagonal(n) is in ~P.
So if n is the Godel number of F then F(n) is true only if Diagonal(n) is in ~P i.e. only if F(n) is an unproveable sentence. So F(n) is either true and unproveable or false and provable. But since the system is correct, no false statement can be proved. F(n) must be true but not provable.

The application of this general set up to a specific language requires showing that (~P)* is nameable and this is done by separately showing that the Godel numbers of its proveable sentences are nameable and that for any nameable set its complement and * are nameable. According to the author, these verifications are where all of the work is. Examples of specific languages are "Peano Arithmetic" , "Peano Arithmetic with Exponentiation", and " Peano Arithmetic with ω-consistency"

- The author also gives a simple example that illustrates the argument and does not use Godel numbers.
One has a language made up of all finite strings of the symbols P N ( ) ~ and a machine that prints a string if it is "printable".

The sentences in the language are the expressions P(X) PN(X) ~P(X) and ~PN(X) for any string,X.
P(X) is true if X is printable PN(X) is true if X(X) is printable and their negations are true if they are not printable.

The predicate ~PN names the expressions,X, so that X(X) is not printable. This corresponds to the set (~P)* above.
The abstract Form of Godel's proof then says that ~PN(~PN) is true if and only if it is not printable.

 

[cosmik debris]

Some people are talking about the incompleteness theorem and some the completeness theorem, which is it?

 

[micromass]

Godel has a completeness theorem and incompleteness theorems.

 

[Svein]

An amusing and quite readable explanation is contained in "Gödel, Escher, Bach" by Douglas Hofstadter.

 

[logico]

Aargh. 50 years ago I had to study this stuff. It is certainly important to resolve it. Godel's incompleteness theorem is one of a class of arguments depending on diagonalisation - preceded by Cantor and followed by Church-Turing. First of all, assume that you have a strategy for listing all the elements of a set systematically. Each is encoded as a string of symbols, in such a way that any such string can be decoded. The first string on the list is, let's say: a, b, c, d, e, -, -, -... where the dashes signify an infinite repetition of some null symbol (if the set was decimal fractions, that would allow us to have strings "of the same length" for a half and for the reciprocal of root two: 0.5000... and 0.7071... for example). Clearly we can construct a string which is different from the first at its first symbol, from the second at its second symbol, from the nth at the nth symbol... We have a string which was not on the list, and when we decode it we have an element which was not in the set. We have cleverly proved that an infinite set can never be complete...

Far be it from me to dismiss the importance of this result for mathematicians, but the infinite and the infinitesimal are problematic in the philosophy of science - in physics or cosmology. My personal view is that we live in a digital (or computational) universe properly described by discrete mathematics.

 

[logico]

Feynman toyed with the idea of a checkerboard universe - discrete space and time - all his working life. Why? Because he didn't like the need for renormalisation as practised.