Monday, October 26, 2009

Gödel Without Tears -- 3

Here's the third episode (slightly updated to take account of some initial comments). Not anywhere near so exciting as the first two -- but after all that arm-waving generality, we do need to get our hands dirty looking at some actual formal theories of arithmetic, mildly tedious though that is! And you really ought to know, e.g., what Robinson Arithmetic is.

7 comments:

a.c. said...

First proof in section 9.3, line 6 says "0 /= SS" which is not well-formed. "SS" should be "SS0".

A question re section 10: If we fix the domain of the quantifiers to be the natural numbers, why do we have to rule out "pseudo-zeros"?

Perhaps I'm missing something obvious, but I could understand it if the aim was to ensure the axioms didn't have models that contained pseudo-zeros; but if we fix the domain to be the natural numbers, ...?

a.c. said...

At first, you use "schemata" (lower case), but once you've introduced some schemata, you always(?) use "Schemata" (capital "S").

Perhaps it's capital "S" because "Schema 1", "Scheme 2", etc, would be "S", with "Schemata" as a way to refer to the particular ones collectively; but you don't do the same with "theorems". That is, you use "Theorem 1", "Theorem 2", etc, but not "Theorems".

a.c. said...

Proof of Theorem 12: "We've just shown that Q |- phi": "|-" should be crossed. That is, whats just been shown is that Q can't prove phi.

I can't follow the "in headline terms" part of the proof of Theorem 11. For instance, it says "Adding* S∗n to a yields a", but earlier were were told that x +* a = b. So shouldn't adding* S*n to a yield b?

"And adding* S∗a to any x is the same as adding* a (since S∗a = a) i.e. is b" -- but a +* n = a.

a.c. said...

Third line of the second paragraph of 10.6: "Q is can capture" should be "Q can capture".

Pedantic detail: The first sentence of the 3rd paragraph of 10.6 should say "(and it was isolated by Robinson for that reason)" -- "it" added -- because otherwise it looks like it's saying Q is about the weakest arithmetic that is both sufficiently strong and isolated by Robinson for that reason.

Ed said...

To a.c.:

In regards to your query about Section 10, the quantifiers of the language are merely *intended* to range over the natural numbers. You are right that we should not assert from the outset that all L_A-structures have the naturals as their universes, though the text would suggest that reading. In fact, the theory Q itself (like PA) has nonstandard models where the universe is *not* just the natural numbers, but adding in the axiom in question does indeed ensure that Q at least doesn't have models that contain such pseudo-zeroes.

a.c. said...

Ed, what's leading me into confusion is that section 10.1 says "We fix the domain of the quantifiers to be the natural numbers. The result is the language LA."

(Not only is the domain fixed, that seems to be part of the definition of the language.)

I'm aware that (normally?) there can be nonstandard / unintended models (indeed, one is used in section 10.3); and I can see why an axiom would be needed to rule out models that contain "pseudo-zeros".

What's not clear to me is how all that fits with fixing the domain, and moreover to one that doesn't contain pseudo-zeros.

Peter Smith said...

Thanks for the comments -- I hope the various issues, smaller and larger, and now sorted.