Typographical and other errors

Stephen G. Simpson

July 11, 2024

1 Typographical errors in the first edition

Here is a list of typographical errors in Subsystems of Second Order Arithmetic, Stephen G. Simpson, Springer-Verlag, 1999, XIV + 445 pages. It contains all errors which were discovered through 2006. All of these errors were corrected in the second edition which was published in 2009.

• Proof of Theorem I.9.1, displayed formula, replace |c − c_{k}| < 2^{n} by |c − c_{k}| < 2^{−n}.

• Theorem I.10.3, in item 8, replace “set of sentences” by “consistent set of sentences”.

• Proof of Lemma III.2.5, the subscripts need to be repaired. The proof should be as follows:

We first consider the case of a finite product Â = ∏_{i=1}^{m} Â_{k}. In this case, for each j ∈ ℕ, let l_{j} = the smallest l such that m·2^{−l} ≤ 2^{−j}. Put n_{j} = ∏_{k=1}^{m}(n_{l_{j}k} +1)−1 and let ⟨x_{ij} : i ≤ n_{j}⟩ be an enumeration of ∏_{k=1}^{m}{x_{il_{j}k} : i ≤ n_{l_{j}k}}. Then ⟨⟨x_{ij} : i ≤ n_{j}⟩ : j ∈ ℕ⟩ attests to the compactness of Â. In the case of a countably infinite product Â = ∏_{k∈ℕ} Â_{k}, for each j ∈ ℕ let l_{j} = smallest l such that (j+2)·2^{−l} ≤ 2^{−j−1}. Put n_{j} = ∏_{k=0}^{j+1}(n_{l_{j}k} +1)−1 and let ⟨x_{ij} : i ≤ n_{j}⟩ be an enumeration of ∏_{k=0}^{j+1}{x_{il_{j}k} : i ≤ n_{l_{j}k}}. Again ⟨⟨x_{ij} : i ≤ n_{j}⟩ : j ∈ ℕ⟩ attests to the compactness of Â. This completes the proof of the lemma.

• Proof of Theorem III.3.2, main paragraph, replace h : K → ℚ by g : K → \overline{ℚ}, and replace h(a) = b by g(a) = b. Also, replace all three occurrences of K_{1} by M.

• Proof of Theorem III.4.3, last line of third paragraph, replace

∀n (q_{2n} ≠ 0 → f(q_{2n+1}/q_{2n}) = n)

by

∀n (q_{2n} ≠ 0 → f(q_{2n+1}/q_{2n}) = n) and ∀n (q_{2n} = 0 → q_{2n+1} = 0).

• Proof of Theorem III.6.5, middle of page 120, replace y_{ij} = p_{f(i)}z_{i,j+1} by y_{ij} = p_{f(i)}y_{i,j+1}.

• Proof of Theorem III.6.5, first line of last paragraph on page 120, replace h_{i} : A → D, i = 1, 2 by h_{1}, h_{2} : A → D.

• Proof of Lemma IV.1.4, end of proof, replace f∗(∑_{i=0}^{j−1} f(i) + k) = 1 by f∗(∑_{i=0}^{j−1} g(i) + k) = 1.

• Exercise IV.2.10, replace “closed set” by “closed set C”.

• Definition V.4.5, replace A by A.

• Remark V.10.1, replace Σ_{1}^{0}-AC_{0} by Σ_{1}^{1}-AC_{0}.

• Theorem VI.2.6, replace “Over” by “over”.

• Proof of Sublemma VI.3.3, in the definition of C_{0}, replace X_{1} ⊕ X_{1} by X_{0} ⊕ X_{1}.

• Definition VII.3.2.4, replace u − (v − u) by u − (u − v).

• Proof of Theorem VII.3.31, first line, replace T by T.

• Proof of Theorem VII.6.9, first paragraph, second last sentence, replace “The” by “Then”.

• Remark VIII.1.16, replace “as do ACA_{0} and Σ_{1}^{1}-AC_{0}” by “while ACA_{0} and Σ_{1}^{1}-AC_{0} prove the same Π_{2}^{1} sentences.”

• Proof of Lemma VIII.2.16, first line of page 323, replace Y by Z.

• Proof of Lemma IX.2.4, second line, replace |M| ∪ S_{M′} by |M| ∪ S_{M}.

• Theorem X.2.9, items 5, 6, and 7, replace X by X∗.

• Section X.3, just before Definition X.3.1, replace “Ramsey’s theorem” by “Ramsey’s theorem for exponent 3”.

• Definition X.4.1, replace “atomic formula” by “numerical term”.

• Bibliography, item 268, replace “borel” by “Borel”.

• Index, atomic formula, replace “2, 410” by “2”.

• Index, formula, atomic, replace “2, 410” by “2”.

• Index, GKT basis theorem, replace “325–326” by “325–326, 354–356”.

• Index, numerical term, replace “23” by “2, 23, 410”.

• Index, term, numerical, replace “2, 23” by “2, 23, 410”.

• Index, add index entry, weak Σ_{1}^{1}-AC_{0}, 342–347.

• Index, universal Σ_{1}^{1}, replace “333, 356” by “252, 333, 356”.

2 Errors in the second edition

Here is a list of errors in Subsystems of Second Order Arithmetic, Second Edition, Stephen G. Simpson, Association for Symbolic Logic, Cambridge University Press, 2009, XVI + 444 pages. This list is current as of today, July 11, 2024.

• The proof of Theorem IV.8.2 contains two typographical errors. In displayed equation (15), < 2^{−3(n+2)} should be < −2^{−3(n+2)}. In line 7 from the bottom of the page, > −2^{−3(n+2)} should be > 2^{−3(n+2)}.

• Nik Weaver has pointed out a typographical error in the proof of Theorem V.6.8. Namely, the displayed formula

∀X ∀n (LO(X) ∧ ¬ WO(X)) → |X ∗ Y_{n}| < |U|)

should be

∀X ∀n (LO(X) ∧ ¬ WO(X_{n})) → |X ∗ Y_{n}| < |U|) .

• David Madore has pointed out that part 18 of Lemma VII.3.7 is incorrect. The error is not typographical but mathematical. Namely, B_{0}^{set} does not include the Axiom of Regularity, so for instance it is consistent with B_{0}^{set} that there are proper-class-many sets x such that x = {x}, and of course all such sets are hereditarily finite. There are two ways to repair this.

1. Preferred way: Move the Axiom of Regularity from Definition VII.3.8 (the axioms of ATR_{0}^{set}) to Definition VII.3.3 (the axioms of B_{0}^{set}).

2. Another way: Change part 6 of Definition VII.3.6 to read as follows: Trans(u) ↔ u is transitive, i.e., ∀x ∀y ((x ∈ y ∧ y ∈ u) → x ∈ u) ∧ ∀v ((v ⊆ u ∧ v ≠ ∅) → ∃x (x ∈ v ∧ ∀y (y ∈ v → y ∉ x))). Thus regularity is incorporated into the definitions of transitivity and hereditary finiteness.

Under either 1 or 2, part 7 of Definition VII.3.6 can be simplified by omitting the clause which begins with ∀v.

• In line 2 of the proof of Theorem VII.3.9, “Then” should be “The”.

• David Madore has pointed out another mathematical error. Namely, in the Notes for §VII.5 on page 293, the stated characterization of α_{k+2}^{Δ} is correct for k ≥ 1 but incorrect for k = 0. A correct characterization of α_{2}^{Δ} reads as follows. α_{2}^{Δ} = the least admissible ordinal which is the limit of smaller admissible ordinals.

• Andre Kornell has pointed out a typo in Definition VII.4.22. In the displayed formula, u ⊆ rng(f) should be u ∈ rng(f).

• Definition X.4.1, replace RCA_{0} by RCA_{0}^{∗}.