# Who has actually read Godel's theorems?

1. Feb 17, 2005

### 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.

2. Feb 17, 2005

### 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.

Last edited: Feb 17, 2005
3. Feb 17, 2005

### 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

4. Feb 17, 2005

### Hurkyl

Staff Emeritus
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.

Last edited: Feb 17, 2005
5. Feb 17, 2005

### matt grime

Damn model v axioms thing....

6. Feb 17, 2005

### 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.

7. Feb 17, 2005

### learningphysics

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

8. Feb 18, 2005

### master_coda

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

9. Feb 18, 2005

### 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.

10. Feb 19, 2005

### learningphysics

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:
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.

11. Feb 19, 2005

### 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 infinte 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"

12. Feb 19, 2005

### Hurkyl

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

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.

13. Feb 19, 2005

### 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.

Last edited: Feb 19, 2005
14. Feb 19, 2005

### 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 ).

15. Feb 19, 2005

### gravenewworld

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

16. Feb 19, 2005

### 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.

Last edited: Feb 19, 2005
17. Feb 19, 2005

### Hurkyl

Staff Emeritus
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)

18. Feb 19, 2005

### 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.

19. Feb 19, 2005

### 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?

20. Feb 19, 2005

### learningphysics

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.

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.