Who has actually read Godel's theorems?

[gravenewworld]

I constantly see threads that deal with Godel's theorems on the math boards. Right now I am taking math logic and will be plowing through the actual proof of what Godel showed. I was wondering if anyone else has actually read and understood Godel's theorem's, not just books about them. My professors constantly says that people try to make all sorts of nonsense arguments with godel's theorems when they have never actually read and fully understood them.

 

[Chronos]

Goedel asserts that no logical model can validate its assumptions. I consider that circular logic. Under Goedel's rules, he refutes his own argument.

 

[matt grime]

And that'd be one of the answers that your professor would find disturbing.

There are two incompleteness theorems, or so I've been informed. So evidently I'm not one who can say "yes I've read them". But I can back up your professor. The most common misstatement is that there are true statements that can't be proven in an axiomatic system.

Firstly, it must be finitely axiomatized, and strong enough to define (a model of) the natural numbers (ie something we can induct on). Secondly it doesn't state there are true statements that can't be proven. It states there is a statement S, such that taking S to b an axiom yields no contradiction, and taking not(S) to be an axiom leads to no contradiction. I'm deliberately being very careful not to use the word "consistent" which is the topic of the other theorem and the one that Chronos just wilfully abused. I think "independent" is the more useful term.

If we take the axioms of geometry, the parallel postulate is independent of the other axioms. That is if we took just the other axioms we can produce a model in which the P.P. is taken as an axiom, and one in which its negation is taken as an axiom. (Euclidean and spherical, or hyperbolic) Please note that geometry is not in the scope of Goedel since it doesn't define the natural numbers, this was an illustration of the "independence" the only other ones I know are the continuum hypothesis and the axiom of choice being independent of ZF

 

[Hurkyl]

The way the result is usually presented is somewhat misleading... Matt Grime's statement is somewhat more careful.

IIRC, Gödel proves that for any model of the theory in question, there exists a proposition in the theory that is true for the model, but cannot be proven or disproven from the axioms of the theory.

When stated this way, it sounds awfully like it's saying there are true statements of the theory that cannot be proven.


I don't recall the exact statement of the second incompleteness theorem.


People also seem to forget Gödel proved a completeness theorem. Given a statement of a theory using first order logic, it's provable from the axioms iff it's true in every model.



Here's another example of an independant proposition: in the theory of fields, the proposition 1+1=0 is independent of the axioms.

 

[matt grime]

Damn model v axioms thing...

 

[gazzo]

He introduces a bunch of specific symbols which confuses everything!

They have it at borders in town but its like $50 for a tiny book so only read it there.

Good luck.

 

[learningphysics]

The way the result is usually presented is somewhat misleading... Matt Grime's statement is somewhat more careful.

IIRC, Gödel proves that for any model of the theory in question, there exists a proposition in the theory that is true for the model, but cannot be proven or disproven from the axioms of the theory.

When stated this way, it sounds awfully like it's saying there are true statements of the theory that cannot be proven.

Yes it does. Can you explain the difference? What is the "model" of the theory? Thanks.

 

[master_coda]

I don't recall the exact statement of the second incompleteness theorem.

Basically, any theory powerful enough to model the natural numbers can prove its own consistency if and only if it is inconsistent.

 

[matt grime]

Axioms are a set of rules. A model is mathematical gadget in which the objects satisfy those rules.

I gave you an example of geometry.

Examples: Vector space axioms, group axioms and so on. A model of the axioms is then a vector space, or a group resp. And just as in these cases there may be strictly different models of the same axioms. And in some models some results will be true, and others won't. I don't know which bits of maths you know about, but if you do know about groups or vector spaces I could couch things in those familiar terms.

 

[learningphysics]

Axioms are a set of rules. A model is mathematical gadget in which the objects satisfy those rules.

I gave you an example of geometry.

Examples: Vector space axioms, group axioms and so on. A model of the axioms is then a vector space, or a group resp. And just as in these cases there may be strictly different models of the same axioms. And in some models some results will be true, and others won't. I don't know which bits of maths you know about, but if you do know about groups or vector spaces I could couch things in those familiar terms.

I'm familar with linear algebra and vector spaces.

Perhaps I'm just misunderstanding what you and Hurkyl were saying.

If we have a particular model... would the natural numbers work?

And we have a particular theory of the model, that consists of a set of axioms...

There exists a true statement about the model that cannot be proven or disproven using the theory in question? Is this correct?

I was confused by what Hurkyl said:

When stated this way, it sounds awfully like it's saying there are true statements of the theory that cannot be proven.

Does a statement of a theory without any corresponding model, actually have truth value?

What I'm getting at is... isn't it presumed that someone is talking about statements... that there is some model involved, and doesn't the statement have to be about the model in question?

I don't know anything about model theory.

 

[matt grime]

You appear to have it precisely backwards.

The axioms come first. The model comes second.

The natural numbers are not a model of set theory, what do you think they are a "particular model" of?

Consider the following:

Let A be the list of axioms of a vector space. Let V be a model of the axioms, that is V is a vector space, and let us suppose that V is over the reals and is two dimensional. Then the Statement V contains an infinite number of elements is true. Now take W a 2-d vector space over a finite field (ie another model), then that statement is false in this model. Thus the statement "a (non-zero) vector space contains an infinite number of elements" is independent of the axioms of vector spaces.

(I am indebted to Hurkyl for showing me this way of thinking).

We aren't doing model theory, really. If you prefer replace the word "model" with "a realization of something satisfying the rules"

 

[Hurkyl]

Models are one of those fundamentals that you use all the time, but don't really need to know you are.

Does a statement of a theory without any corresponding model, actually have truth value?

Yes. All the statements of a theory "are" true.

I think you meant the statements in a particular language -- the language is the one that contains all possible propositions.


The concept of "truth" isn't really an inherent property of logical statements. It's acquired through the specification of a truth assignment: a function from the statements of a language to the truth values.

If a truth assignment says the axioms of a theory are true, then it will also say that every statement of the theory is true.


So, we haven't really talked about models at all. It turns out that each model of a theory gives rise to a truth assignment that maps the axioms of the theory to "true". I think the converse is true -- each truth assignment gives rise to a set-theoretic model.

 

[mathwonk]

Paul Cohen gave a course on logic at Harvard in about 1965, and the notes were published as a paperback Benjamin book:

Set Theory and the Continuum Hypothesis
by Paul J. Cohen


I recommend this as a source, but it is hard to find outside libraries.


Here is a typical review from the Amazon site:

five stars: All-time classic -- a "desert island book", July 5, 2003
Reviewer: Joseph L. Shipman (Rocky Hill, NJ USA) - See all my reviews
(REAL NAME)
Paul Cohen's "Set Theory and the Continuum Hypothesis" is not only the best technical treatment of his solution to the most notorious unsolved problem in mathematics, it is the best introduction to mathematical logic (though Manin's "A Course in Mathematical Logic" is also remarkably excellent and is the first book to read after this one).

Although it is only 154 pages, it is remarkably wide-ranging, and has held up very well in the 37 years since it was first published. Cohen is a very good mathematical writer and his arrangement of the material is irreproachable. All the arguments are well-motivated, the number of details left to the reader is not too large, and everything is set in a clear philosophical context. The book is completely self-contained and is rich with hints and ideas that will lead the reader to further work in mathematical logic.

It is one of my two favorite math books (the other being Conway's "On Numbers and Games"). My copy is falling apart from extreme overuse.

 

[Clausius2]

To say the truth, I have read all the posts and I keep on not understanding what is the true meaning of Godel's theorems.

Maybe, Hurkyl and Mattgrimme, could you give us an example of the real consequence of Godel's theorems on, for example, the formulation of some field of the Physics?

Or am I definitely lost and it has no consequence over physics formulation? I mean, it is one of those useless theorems that mathematicians usually invent? (kidding ).

 

[gravenewworld]

My logic prof. said godel's theorems mostly have applications to mathematics, philosophy, and computer science.

 

[mathwonk]

of course you were jesting, but to me goedel is a logician, not a mathematician.

nonetheless, mathematicians are concerned with proving theorems, and they generally believe in the power of the axiomatic method, that one can write down all the relevant assumptions on a given topic, and then deduce all desired results, by using purely logical reasoning.

goedel undertook to examine the validity of this belief. he apparently showed that it is not so easy to write down enough assumptions to allow one to then deduce all results which are nonetheless "true" in ones context, with some reasonable definition of "true".

a novice myself, from what i read here and elsewhere, i gather that after encountering a true statement which one does not have enough assumptions to prove, that one could then augment the collection of assumptions so as to be able to prove it. (perhaps tautologically by including the statement itself.)

But the true facts seems always to keep ahead of the statements which are "provable with current tools".

i believe this is the case at least in any fairly large logical system, but not in small ones.

this could have implications for mechanizing certain logical processes, maybe for applications of artificial intelligence.

As a working geometer however, after an initial period of interest and fascination, I have literally never given goedels results a second thought.

in my experience, they fascinate amateurs more than professionals, for the most part, although professional logicians no doubt do think about them.

but virtually no mathematician ever stops to worry whether the problem he is working on might actually be undecidable.

I have taught some courses on elementary logic in geometry, and it gave me great comfort to learn the principle of "models". I.e. a system of axioms is "consistent". or without internal contradiction, if there exists a model in which all the axioms are true.


Since Euclid's axuioms are all true, including the fifth postulate, for the geometry of R^2, that put to rest at last my hazy feelings about high school geometry.

The simple fact that the hyperbolic geometry of the upper half plane violates that suspicious parallel postulate, then settles the question as to whether the fifth postulate depends on the others.

what puzzles me is why this was not clear hundreds of years before, since the more intuitive model, of "table top" geometry seems to offer an even simpler model for non euclidean geometry.

i.e. a finite model of the plane, like the one we actually draw on the board, also has many parallel lines to a given one.

and why was none of this made clear in my high school geometry course?

my favorite geometry text for a deeper look, merely for beginning students however, at the underpinnings of high school geometry, is that of millman and parker

they introduce a few axioms at a time, and as they go forward, they maintain as many models as possible which embody all the axioms. Then when they have all euclid's axioms except the parallel postulate, they are down to only two models.

it turned out to be unfeasible to teach from this book in unversity since the students in the course actually did not know high school geometry, and the course thus had to become a review of basic material from secondary school.

thus courses in university today on teaching geometry, are often actually watered down versions of the high school course the candidate will teach. the old assumption that the students knew high school math and should be taught a deeper understanding of the topic in college have had to be abandoned.

 

[Hurkyl]

It's nice to know someone's looking at foundational issues, even if you're not interested.

I have used Gödel's first incompleteness theorem for practical purposes. It, with Tarski's theorem, was how I first proved to myself that the natural numbers are not a semi-algebraic set of any real closed field. (Though, at the time, I only understood it in logical terms, not geometric)

 

[mathwonk]

by the way, i have enjoyed some of Tarski's writings on logic, and recommend them.

i should also hasten to add that my comfort in the consistency of euclid's geometry, based on the model for it provided by R^2, should be tempered by an admission that the consistency of R^2, i.e. of the existence of the real numnbers, is also presumably philosophically an open matter.

 

[mathwonk]

ignorant question: my impression is that goedels proof that undecidable statements exists, is by producing decidedly uninteresting ones, that basically amount to getting round the prohibition on meaningless statements of the kind in russells paradox.

i.e. to my knowledge no one has ever found a genuine problem that anyone cared about, like fermat's last problem, or goldbach's conjecture, to be true but undecidable.

help on this from the cognoscenti?

 

[learningphysics]

You appear to have it precisely backwards.

The axioms come first. The model comes second.

The natural numbers are not a model of set theory, what do you think they are a "particular model" of?

Peano's axioms?

What I had meant was that we have a set of objects of some kind... a vector space (set of vectors). (This is what I meant by beginning with a model... I apologize for the confusion, as model presumes the existence of something that models it - what I really meant was a set of objects).

Now, we want some theory, or a set of axioms to give all the true statements about this vector space. Something that models the vector space.

Consider the following:

Let A be the list of axioms of a vector space. Let V be a model of the axioms, that is V is a vector space, and let us suppose that V is over the reals and is two dimensional. Then the Statement V contains an infinite number of elements is true. Now take W a 2-d vector space over a finite field (ie another model), then that statement is false in this model. Thus the statement "a (non-zero) vector space contains an infinite number of elements" is independent of the axioms of vector spaces.

(I am indebted to Hurkyl for showing me this way of thinking).

We aren't doing model theory, really. If you prefer replace the word "model" with "a realization of something satisfying the rules"

Ok. I think I understand. Let A be a finite list of axioms. Let V be a model of the axioms. Now what does Godel's incompleteness theorem say: There is some statement S that can be made about V, such that S does not contradict with A, and neither does not(S). I think this is how you said it in a previous post. But S is actually true or false, right?

Is this correct: There is a true statement about V that cannot be proven using A.

 

[chronon]

ignorant question: my impression is that goedels proof that undecidable statements exists, is by producing decidedly uninteresting ones, that basically amount to getting round the prohibition on meaningless statements of the kind in russells paradox.

i.e. to my knowledge no one has ever found a genuine problem that anyone cared about, like fermat's last problem, or goldbach's conjecture, to be true but undecidable.

help on this from the cognoscenti?

Goodstein's theorem has been shown to be undecidable in 1st order Peano arithmetic.

http://curvebank.calstatela.edu/goodstein/goodstein.htm

 

[matt grime]

I think that your interpretation is good enough, learingphysics - it's about the same as mine, but I'm not a logician, so please be wary and wait until your professor does it properly. The abstract proof, roughly, from the little I know shows you can take the axioms A, and embed them in some larger system, in which it is possible to make a statement such as "this is not provable in A" that is true in the larger system. That is a VERY loose interpretation. As mathwonk and others indicate the kinds of thing that turn out to be independent of any reasonable set of axioms such as ZF are quite odd things. However, in mathematical physics there are people coming up against Russell's/Cantor's Paradox of the "set of all sets" kind. The rough problem seeemed to be that they wanted to integrate (path sum) over the set of all 'simplices' and to do that the set of simplices has to be a simplex. So there are some problems that may start to need more philosophical input in physics.

 

[learningphysics]

I think that your interpretation is good enough, learingphysics - it's about the same as mine, but I'm not a logician, so please be wary and wait until your professor does it properly. The abstract proof, roughly, from the little I know shows you can take the axioms A, and embed them in some larger system, in which it is possible to make a statement such as "this is not provable in A" that is true in the larger system. That is a VERY loose interpretation. As mathwonk and others indicate the kinds of thing that turn out to be independent of any reasonable set of axioms such as ZF are quite odd things. However, in mathematical physics there are people coming up against Russell's/Cantor's Paradox of the "set of all sets" kind. The rough problem seeemed to be that they wanted to integrate (path sum) over the set of all 'simplices' and to do that the set of simplices has to be a simplex. So there are some problems that may start to need more philosophical input in physics.

Thanks. I appreciate all your help.

 

[mathwonk]

thanks chronon. for some reason i am still not impressed. i guess I am looking for an example where the interesting theorem is not provable using anything normally available, not a case where you artificially restrict what is available.

they did prove goodstein's thm using ordinary set theory. or maybe i just do not care about this sort of thing.

so there is nothing in any of this to convince me that usual approaches to proving theorems are ever going to fail. but maybe there never was.

the more clear you experts make these results, the less consequential they seem to be. this is usual in science. i.e. that popular accounts of some theorems threaten more potential consequences than are justified by the actual statements.

 

[chronon]

thanks chronon. for some reason i am still not impressed. i guess I am looking for an example where the interesting theorem is not provable using anything normally available, not a case where you artificially restrict what is available.

they did prove goodstein's thm using ordinary set theory. or maybe i just do not care about this sort of thing.

so there is nothing in any of this to convince me that usual approaches to proving theorems are ever going to fail. but maybe there never was.

the more clear you experts make these results, the less consequential they seem to be. this is usual in science. i.e. that popular accounts of some theorems threaten more potential consequences than are justified by the actual statements.

The important point is that this is the limit of what Gödel's incompleteness theorem actually says, that given a set of axioms for the integers there will be statements unprovable from those axioms. If we are allowed to use our intuitive knowledge of the integers, then Gödel's theorem places no limits on what can be proved.

The situation in set theory is somewhat different, in that we don't have direct access to infinite sets, so we can't say 'obviously the continuum hypothesis is true'.

I've written more about this subject at http://www.chronon.org/Articles/fermat_undecidable.html

 

[CrankFan]

The important point is that this is the limit of what Gödel's incompleteness theorem actually says, that given a set of axioms for the integers there will be statements unprovable from those axioms.

That's not what it says.

 

[mathwonk]

chronon, aren't you confusing "undecidable true statements" in a system with statements which are "independent of that system"?

i.e. my impression is the continuum hypothesis is "undecidable" only in the sense it could be either true or false, i.e. it is independent of the rest of the theory of real numbers, like euclid's parallel postulate is of the rest of euclidean geometry geometry.

 

[mathwonk]

here is an extract from a set of notes apparently handed out at Stanford for a course on logic, by Rob van Glabbeek:

"Goedel's incompleteness theorem: If a proof system for arithmetic is sound (meaning that only true formulas are provable) then there must be a true formula that is not provable.

Proof: The set of provable formulas is enumerable, and the set of true formulas isn't. Therefore there must be a difference. QED

Remark: The proof of Goedel's incompleteness theorem given here rests heavily on Church's thesis, which is not a mathematical theorem. Goedel's own proof bypasses Church's thesis (in fact it predates it by several years) and therefore is much more complicated. The undecidability proof of truth goes through also in the absence of Church's thesis: truth is then not recursive. However, showing that provability is recursive enumerable is a lot of work, and requires slightly stronger assumptions regarding the notion of a reasonable method of provability. It is possible to bypass the use of decidability and recursive enumerability by showing that provability is arithmetical (see below), whereas truth is not. Alternatively it is possible to construct an actual formula that is true but not provable; this is what Goedel did."

 

[mathwonk]

the author of the following webpage seems to make the same mistake, confusing "true but unprovable" statements, with "independent statements"...i.e. he confuses statements which if added as postulates, must be taken as true, with statements whose truth or falsity could either be added as a consistent statement.

"Godel's Incompleteness Theorem
Zillion's Philosophy Pages

First let me try to state in clear terms exactly what he proved, since some of us may have sort of a fuzzy idea of his proof, or have heard it from someone with a fuzzy idea of the proof..

The proof begins with Godel defining a simple symbolic system. He has the concept of a variables, the concept of a statement, and the format of a proof as a series of statements, reducing the formula that is being proven back to a postulate by legal manipulations. Godel only need define a system complex enough to do arithmetic for his proof to hold.

Godel then points out that the following statement is a part of the system: a statement P which states "there is no proof of P". If P is true, there is no proof of it. If P is false, there is a proof that P is true, which is a contradiction. Therefore it cannot be determined within the system whether P is true.

As I see it, this is essentially the "Liar's Paradox" generalized for all symbolic systems. For those of you unfamiliar with that phrase, I mean the standard "riddle" of a man walking up to you and saying "I am lying". The same paradox emerges. This is exactly what we should expect, since language itself is a symbolic system.

Godel's proof is designed to emphasize that the statement P is *necessarily* a part of the system, not something arbitrary that someone dreamed up. Godel actually numbers all possible proofs and statements in the system by listing them lexigraphically. After showing the existence of that first "Godel" statement, Godel goes on to prove that there are an infinite number of Godel statements in the system, and that even if these were enumerated very carefully and added to the postulates of the system, more Godel statements would arise. This goes on infinitely, showing that there is no way to get around Godel-format statements: all symbolic systems will contain them.

Your typical frustrated mathematician will now try to say something about Godel statements being irrelevant and not really a part of mathematics, since they don't directly have to do with numbers... justification that might as well turn the mathematician into an engineer. If we are pushing for some kind of "purity of knowledge", Godel's proof is absolutely pertinent.

In addition, some known mathematical phenoma already exhibit the Godel incompleteness property. For instance, in set theory mathematicians define different degrees of infinity based on the number of members of the set of all integers, rational numbers or reals. The first degree of infinity, called (aleph-nought), is the number of integers or the number of rational numbers (these numbers are the same "degree of infinity"). The second degree of infinity is aleph-nought raised to the power aleph-nought. For a long time people were trying to decide whether 'C', the number of real numbers, was the same as the second degree of infinity. Finally it was proven that whether C and 2nd infinity were equivalent came down to the truth or falsehood of a statement that could not be proven from the existing axioms of mathmatics. This statement was absorbed as a new axiom, just as Godel statements would have to be. So there is the first of many Godel-style statements that we'll probably see popping up in mathematics.

Of course, a more familiar example is the parallel-postulate axiom, since it cannot be proven from any other axioms of Euclidean geometry, and in this case the way you define it leads to at least three different self-consistent systems. "


As usual it seems many people discuss these matters publicly and more or less knowledgably, who yet do not quite understand fully what they are talking about.

I offer my own post as another example.

 

[chronon]

chronon, aren't you confusing "undecidable true statements" in a system with statements which are "independent of that system"?

i.e. my impression is the continuum hypothesis is "undecidable" only in the sense it could be either true or false, i.e. it is independent of the rest of the theory of real numbers, like euclid's parallel postulate is of the rest of euclidean geometry geometry.

Well I always try to distinguish between Gödel's form of undecidability and say the axiom of choice, which I think is the distinction you are making.

However, when you say 'system', I think you are confusing two different things, a set of axioms and a model of those axioms. The integers we all know and love are a model of the axioms for the integers. Gödel's statement is true in this model, but not provable from the axioms. It is important to note that when you have a model, there is no such thing as an undecidable statement, all meaningful statements are either true or false.

Alternatively, if you take Gödel's statement then you can add it's negation to the axioms without inconsistency. From this you can get a non-standard model of the axioms (which is also a model of your original axioms). In this model Gödel's statement is false.

 

[mathwonk]

in my admittedly untutored opinion, you still seem to be missing the point that there are statements which cannot be added as false to some systems of axioms, preserving consistency, and these are the interesting ones for incompleteness.

i.e. the negation of a true but unprovable statement cannot be added preserving conssitency. a statement is independent iff either it or its negation can be added both preserving consistency.

for example according to your reference, goodstein's theorem is true but undecidable in 1st order Peano arithmetic, i.e. the negation of goodsteins theorem cannot be added without sacrificing consistency.

there is no comparison between this situation and that of euclids parallel postulate, since either it or its negation can be added to the other postulates without sacrificing consistency.

there is nothing surprizing about a statement being independent of another collection of statements, except for the historical accident that it took people hundreds of years to notice the obvious, i.e. that "table top geometry" is a model for the rest of euclids system of axioms in which the 5th postulate is false.

the whole point of incompleteness is the existence of an unprovable statement whose negation cannot be added with sacrificng consistency.

of course i know, as with the parallel postulate, there are models of set theory in which either the continuum hypothesis or its negation are true. this is an example of independence, not incompleteness.

what am i missing?

 

[chronon]

for example according to your reference, goodstein's theorem is true but undecidable in 1st order Peano arithmetic, i.e. the negation of goodsteins theorem cannot be added without sacrificing consistency.

No, the negation of Goodstein's theorem can be added to 1st order Peano arithmetic without sacrificing consistency. In fact this is how undecidability is proved, a model of the axioms is constructed in which the theorem is false. (We already have a model in which it is true, the normal integers).

 

[HallsofIvy]

What exactly do you take as the meaning of "true but unprovable"? In other words, exactly what do you mean by "true" in an abstract axiom system?

 

[master_coda]

in my admittedly untutored opinion, you still seem to be missing the point that there are statements which cannot be added as false to some systems of axioms, preserving consistency, and these are the interesting ones for incompleteness.

This is not true if you are working with first-order logic. If you're working with first-order Peano arithmetic, a statement can be undecidable if and only if there exists models in which the statement is false and models in which the statement is true.

the whole point of incompleteness is the existence of an unprovable statement whose negation cannot be added with sacrificng consistency.

It is a consequence of incompleteness that higher-order logics have statements of this form. However the theorem itself is concerned with first order logic, so this is certainly not the "whole point" of incompleteness.

 

[jennycraig10]

I'm a high school student and am doing a report on Kurt Godel... Can anyone help me out by telling me what career there is out there that uses Godel's theory? I would really appreciate it.