Tuesday, April 07, 2009

How not to present Gödel's Theorems

I was wondering whether to spruce up my very rapidly written hand-outs on Gödel's Theorems which I produced for the Cameleon weekend and publish them here. I was beginning to think I wouldn't bother, as there are other things I want to be getting on with. But I just now read the chapter on incompleteness in Shawn Hedman's A First Course in Logic, and that reminded me how crummy some textbook treatments can be, and hence of the need for crisp and clear presentations. Not that Hedman is technically wrong, of course (well, I haven't read him that carefully, but the details look ok). But I defy any beginning student to take away from his chapter a really clear sense of what the key big ideas are, or of how to distinguish the general results from the hack-work needed to show that they apply to this or that particular theory. So back to those hand-outs!


a.c. said...

So back to those hand-outs!

Yay! I am keen to read them.

Can you recall any books that have good explanations?

Karim Zahidi said...

That would actually be much appreciated.

While I'm commenting. I read in Franzen's book the remark that although PA doesn't prove its own consistency, it does prove the consistency of any finite subset of its axioms. Do you know of any reference of this result, our is it folklore?



Peter Smith said...

To a.c.: Well one book with good explanations is mine (I hope!). Indeed, I wrote it with an eye to giving clear motivations and clear road-maps through the territory. My favourite book is perhaps Smullyan's Gödel's Incompleteness Theorems, but in some ways it is very terse. Christopher Leary's A Friendly Introduction to Mathematical Logic tries to be just that.

To Karim: Good question. Well, any finitely axiomatized subtheory will have to have a finite limit on the complexity of the induction axioms. And we can prove in PA that the subsystem you get by restricting the induction axioms to "Sigma_n" instances is consistent. (That means the wff we do induction over is no more complex than ExAyEzAw ....F,with n alternations of quantifiers.) That's proved -- indeed in a slightly stronger version -- on p.108 of Hájek and Pudlák's bible Metamathematics of First-Order Arithmetic. I'm being forgetful, though, about whether there is a more accessible proof.

Karim Zahidi said...

Thanks for the reference.


a.c. said...

What do you think of Fitting's Incompleteness in the Land of Sets?

BTW, I looked up the Friendly Introduction to Mathematical Logic on Amazon and found:

UK: 5 used & new from £84.06 (!)

The new one is going for £160.64 (!!!)

US: 10 used & new from $45.96

That's better, though still expensive, but after two at 40-something, prices climb to 60-something, $77, and then are over $100. The new one is $167.29!

Now that print-on-demand is fairly common, I am puzzled as to why good books go out of print and cost so much anyway.

Re "anyway", Smullyan's book is still in print, yet at US Amazon, it is "in stock" at $189.00. (!!!)

That is despite it being a print-on-demand book, available at UK Amazon for a "mere" £37.04

Aatu Koskensilta said...

Regarding the provability of consistency of ISigma-n in PA, _Metamathematics of First-Order Arithmetic_ is probably not the best source. They prove a stronger result -- about provability of reflection for ISigma-n in ISigma-n+1 -- using a variant of the arithmetical completenes theorem obtained as a corollary of the low-basis theorem. (Or something like that; it's been a while since I worked through _MoFA_) For the weaker result this is a huge over-kill, and the standard way is to invoke the cut-elimination theorem for first-order logic in combination with the existence of a truth definition for formulas of restricted quantifier complexity. As I noted in sci.logic, essentially this proof is presented at least in Girard's _Proof Theory and Logical Complexity_, p. 218.

PS. Of course, if all we want to know is that PA proves for any of its finite subtheory that the theory is consistent there's really no need to introduce ISigma-n at all. The Haupsatz and the existence of restricted truth predicates is all we need.

Aatu Koskensilta said...

On the subject of good books on incompleteness and related stuff, we should not forget Smorynski's Logical Number Theory...

a.c. said...

Smorynski's Logical Number Theory...

Naturally, it is out of print, and Amazons UK and US don't even have used copies.

Cna anything be done to encourage publishers to keep good maths / logic books in print at reasonable prices?

Peter Smith said...

The reason I tried (successfully) to get CUP to publish my Gödel book is that they are good at publishing books at relatively decent prices, and keeping them in print (you can still buy the full Principia Mathematica if you really want!)

I agree that other publishers have some very odd policies and unsatisfactory policies with classics in their back list. Dover pick up some titles. But my attempts to get into correspondence with them about some possibilities never led to anything (not even friendly responses -- odd as Dover could have got a lot of well-informed advice for free).

Rowsety Moid said...

Dover's done well lately. For example:

Levy, Basic Set Theory
Hodges, Building Models by Games
Bell and Slomson, Models and Ultraproducts
Goldblatt, Topoi: The Categorial Analysis of Logic
Bell, Toposes and Local Set Theories
Jech, The Axiom of Choice
Pillay, Intro to Stability Theory
Cohen, Set Theory and the Continuum Hypothesis

I don't know if there's any system to it, though. It's too bad they didn't reply when you contacted them.

Still, they show it can be done: reasonably well-made books at a very good price.

Peter Smith said...

Oh I agree that Dover's list is terrific -- all credit to them! And the prices are amazing.

Karim Zahidi said...

@ Aatu Koskensilta

Thansk for the references.


Rowsety Moid said...

I agree that Cambridge UP is pretty good, though even the paperback version of Hodges (long) Model Theory is £70.00.

Seems OUP is worse, for some reason. Wouldn't Smullyan and Fitting's Set Theory and the Continuum Problem have done better as a reasonably priced text? Instead, it was absurdly expensive and is now out of print and unavailable.

Another scandal, IMO, is Judith Roitman's Introduction to Modern Set Theory which always seemed insanely expensive. Wiley's to blame in that case.

BTW, another source of reasonably priced, books is the Springer "Lecture Notes" series.

They have some interesting early versions of some significant books:

Shelah, Proper Forcing. (£22.99 at Amazon)

Shelah, Around Classification Theory of Models (Recently available for something like £37, but now out of print.)

Devlin, Aspects of Constructibility (£27)

Devlin, The Axiom of Constructibility (£15)

The same series also has:

Horst Herrlich, The Axiom of Choice (£37)

Elisabeth Bouscaren (ed), Model Theory and Algebraic Geometry: An Introduction to E. Hrushovski's Proof of the Geometric Mordell-Lang Conjecture (£30.39).