Further corrections to IGT, noted after the fourth printing went to press. Where there are two page numbers, the first refers to earlier printings, the second to the fourth and later printings. I use e.g. ‘§13.0’ to refer to the un-numbered preamble to Ch. 13. All the corrections (except where otherwise noted) are due to Orlando May, to whom enormous thanks are due.
- §3.3 (only in later editions, fn. 11 on p. 23) put “understanding” for “understand”.
- §5.2 (p. 39, line 17/18) put “as soon as it does” for “as soon as does”
- §5.3 (p. 40, first line of section) put “it immediately follows” for “it immediate follows”.
- §13.0 (p. 106, line 8) put “captures the same function f as a function” for “captures the same function f”.
- §13.2 (p. 108, top). The definition of the predicate H(x,y,z) doesn’t entirely tally with the description of h(x, y) a few lines earlier. In particular, the statements that “h(x,y) is the least z<= y” isn’t implemented by the wff H. Appropriate conjuncts need to be added.
- §13.2 (p. 109, line 6) delete first occurrence of “wffs” [Thanks to ‘Joe’].
- §13.4 (p. 112, last line of footnote) put “is not greater than” for “is less than”.
- §15.7 (p. 132, line 4 of para starting ‘Look at the pattern’) put “raising the first j primes to powers” for “raising the first j to powers”.
- §15.7 (next para) put “Section 11.7(c)” for “Section 8.5(b)”.
- §15.9 (p. 134, line 17 up, in (iii)) put “‘Sτj’ where τj occurs earlier” for “‘Sτj’ where τi occurs earlier”.
- §16.6 (p. 142, line 9 up) put “Section 8.4” for “Section 8.3”.
- §18.2 (p. 157. line 15 of section) put “restrict T’s quantifiers” for “restrict the T’s quantifiers”.
- §19.1 (only in later editions, p. 164 fn. 2) put “so that it has” for “so that has”.
- §20.4 (only in later editions, second line of section) put “PA ¦- G <-> Ey(y = …” for “PA ¦- G <-> Ey(u = …” [i.e. swap y for u inside bracket].
- §21.3 (p. 177 fn. 4) put “see Section 12.2(b)” for “see the end of Section 12.2” [fussy, the point is nearer the beginning than the end!].
- §21.7 (p. 185/186 four lines up) put “So by Result O4 from Ssection 9.4” for “So by Result 5 from Section 9.9”.
- §22.5 (p. 193/194, seven lines up in main text) put “see Section 2.1” for “see Section 2.3”
- §24.7 (p. 220/221, beginning last para.) put “Of course, it is” for “Of course, is”.
- §25.6 (p. 229/230, lines 4-5) put “the requirement of ω-consistency” for “the requirement of ω-inconsistency”.
- §26.3 (p. 234/235, first line after Theorem 26.4) move subscript T from the phi to the box!
- §26.3 (p. 234/235 fn. 1) put “Boolos (1993, p. 44)” for “Boolos (1993, p. 54)”.
- §26.3 (p. 235/236, first line) put “Section 9.8” for “Section 9.7”.
- §26.4 (p. 236/237) Theorem 26.5 is mis-stated. T still needs to be p.r. (or at least recursively) axiomatized, or we won’t be form the predicate Prf needed to define the Box. [Task for the second edition, tidy up hereabouts.]
- §27.2 (p. 242/243), indented definition labelled “ii”. The variables in CPrfT(x, y), should be ordinary italic type, not sans serif upright. (And the next two definitions are misnumbered before the fourth printing.) [Thanks to Mehmet Budak]
- §28.6 (p. 262/263 fn. 11) put “Godel (1995, p. 157)” for “Godel (1951, p.157)”.
- §28.7 (p. 263/264, line 11 of section) put “We haven’t needed to deploy” for “We haven’t need to deploy”.
- §29.1 (p. 267/268 line 7) put “Section 11.7” for “Section 11.8”.
- §29.3 (p. 269/270 line 6 up in main text) put “a variant on Ackermann’s” for “a variant on the Ackermann’s”.
- §29.4 (only in later editions, p. 274 line 2) put “defined from h” for “defined from g”.
- §30.2 (p. 278/279 line 6 up) put “Theorem 3.1” for “Theorem 3.5”.
- §30.3 (p. 280/281 line 5) put “Section 3.4 (iii)” for “Section 3.4 (ii)”.
- §30.7 (p. 284/285), definition of thm(m) three-quarters of the way down the page. This is illegitimate as it stands — “the least j” operator is being applied to a non-regular condition, for just suppose m doesn’t number a sentence. I forgot to put in the requirement — even though it is in effect mentioned in the previous paragraph — that m numbers a sentence. However, since we are dealing with a properly axiomatized theory T there will be a recursive function sent(m) that gives the characteristic function of that requirement. So what we want in the square bracketed condition is e.g. [{sent(m) = 0 & (enum(j) = m v enum(j) = neg(m)) v {sent(m) = 1 & j = 0}]. Then whatever value m takes, this is a regular condition. If sent(m) = 0, there will be a j such that enum(j) = m v enum(j) = neg(m). Otherwise sent(m) = 1, and j = 0 satisfies the second disjunct. [Thanks to Tony Roy for initially spotting the problem. If anyone would like to offer a neater way of dealing with the problem than the one I suggest here, I’d like to hear about it!]
- §31.1 (p. 289/290 line 3 from section break) put “the basic conception, however, is always” for “the basic conception, however, always”.
- §31.3 (p. 295/296 last para, line 2) delete redundant parenthesis after “the end of the second block”.
- §32.3 (p. 303/304 line 2 before section break) put “Section 29.4” for “Section 29.3”.
- §33.6 (p. 312 last para of fn.5/4) put “see Section 11.7(c) Fact D” for “Section see 11.8, Fact 4”; put “Section 29.5” for “Section 29.3”.
Dear Professor Smith,
Thomas Sullivan I have a question about p. 277 in the fourth printing of your beautifully written and very helpful book on Goedel. Our question may well be based upon our misunderstanding the phrase “what is or isn’t,” but we would like to make sure. We sent a version of this question last January, but think that we must have misaddressed the email.
On p. 277 you observe that Church’s Thesis can be formulated as a conjunction of two conditionals. On the one hand, there is the “Unexciting” conditional: If a function is mu-recursive, then it is effectively computable in the intuitive sense. On the other hand, there is the “Interesting” conditional: If a function is effectively computable in the intuitive sense, then it is mu-recursive.
Of course, each of these conditionals can be equivalently formulated in a contrapositive form. Thus, the “Unexciting” conditional can be equivalently formulated as, “If a function is not effectively computable in the intuitive sense, then it is not mu-recursive.” Similarly, the “Interesting” conditional can be equivalently formulated as, “If a function is not mu-recursive, then it is not effectively computable in the intuitive sense.” {Indeed, this is the formulation of the “Interesting” conditional given in the first paragraph of Section 29.7.}
You go on to distinguish two “uses” of Church’s Thesis. On the one hand, there are “Interpretive” uses and, on the other, there are “Labour-saving” uses. It seems that upon a first quick reading of page 277, one might assume that the “Interpretive” uses of the Thesis rely exclusively upon the “Unexciting” conditional, while the “Labour-saving” uses rely exclusively upon the “Interesting” conditional.
However, upon rereading p. 277, one might notice three occurrences of the phrase “what is or isn’t” in the following sentences: (1) “The interpretive use relies on the Thesis to pass from technical claims about what is or isn’t mu-recursive to claims about what is or isn’t effectively computable.” (2) “The labour-saving use relies on the Thesis to pass in the opposite direction, from informal claims about what is or isn’t computable in the intuitive sense to formal claims about mu-recursiveness.” These occurrences of the phrase “what is or isn’t” might be read as suggesting that there are two ways in which each half of Church’s Thesis can be invoked – what might be called “is” invocations, on the one hand, and “is not” invocations, on the other.
Consider sentence (1) in the immediately preceding paragraph {the “Interpretive” use sentence} and first take the “is” invocation alternative. Under this alternative it seems that readers are invited to imagine conditionals of the form, “If function F is mu-recursive, then F is effectively computable in the intuitive sense.” Such conditionals obviously invoke the “Unexciting” half of Church’s Thesis, a result that conforms to the expectation that all “Interpretive” uses of the Thesis rely exclusively upon the “Unexciting” half of the Thesis.
However, on the other hand, consider the “is not” invocation alternative. Under this alternative it seems that readers are invited to imagine conditionals of the form, “If function F is not mu-recursive, then it is not effectively computable in the intuitive sense.” Contrary to the “is” invocation alternative, it seems that conditionals of this second form rely upon the contrapositive version of the “Interesting” half of the Thesis.
Thus, it seems that the “is” invocation cases of the “Interpretive” uses of the Thesis invoke the “Unexciting” half of the Thesis, but that the “is not” invocation cases of the “Interpretive” uses of the Thesis invoke the contrapositive form of the “Interesting” half of the Thesis.
In addition, it seems that a similar analysis can be made of the “is” invocation and the “is not” invocation alternatives for the “Labour-saving” uses of Church’s Thesis. Thus, it might seem that the “is” invocation cases of the “Labour-saving” uses of Church’s Thesis invoke the “Interesting” half of the Thesis, but that the “is not” invocation cases of the “Labour-saving” uses invoke the contrapositive form of the “Unexciting” half of the Thesis.
So, our questions are these. Do all “Interpretive” uses of the Thesis rely exclusively upon the “Unexciting” half of the Thesis? Or, is it only the “is” invocation cases of “Interpretive” uses that rely upon the “Unexciting” half of the Thesis, while the “is not” invocation cases rely upon the contrapositive form of the “Interesting” half of the Thesis? And, as mentioned, there are analogous questions about the “Labour-saving” uses of the Thesis.
Thanks very much for your help.
– Russell Pannier and Thomas Sullivan
Thanks for this — and my apologies if I missed/accidentally trashed an e-mail!
You write ‘It seems that upon a first quick reading of page 277, one might assume that the “Interpretive” uses of the Thesis rely exclusively upon the “Unexciting” conditional’. I’m not really sure why one might assume that.
Certainly it would be wrong to do so. One techie result is, e.g., that there is no recursive way of deciding theorem hood for first-order logic. We interpret that as implying that there is no effective way at all of deciding theorem hood for first-order logic. In so doing, we rely on the exciting contrapositive “If function F is not mu-recursive, then it is not effectively computable in the intuitive sense”. Interpretation can be exciting (but needn’t be).
On the other hand, the labour saving invocation of CT always (or almost always?) goes from the availability of an informal argument for effective computability to the recursiveness of some function, i.e. always rely on the exciting direction of CT.
So the situation isn’t quite symmetric and perhaps the way I’ve written that section could mislead. I might tinker with it!
Not sure if this is where I should post this, but…
IGT 4th printing, section 13.2, page 109, 1st paragraph, “captured as functions by the corresponding wffs delta-0 wffs G-tilde and H-tilde.” I believe the first “wffs” should be removed.
Thanks — now incorporated in the list above!