Errata to "The Mathematics of Logic"

# Errata to "The Mathematics of Logic"

• Page 1, line 3 from bottom: remove the word means. (The fact that edges go downwards does not rule out loops or cycles, at least for some idea of graph but a tree is not allowed to have loops. Note that my definition of tree is not the same as some others you will find, for example in graph theory. In particular my trees are rooted trees, meaning they have a special designated node as root.)
• Page 5, definition 1.5: A tree is a non-empty set $T$ of sequences of finite length such that... (Add the words non-empty and of finite length.)
• Page 8, line 5: does not appear should be appears. (This was an unintentional double negative: a sequence is $x n$-free if it has no subsequence of form $x n$.)
• Page 14, line 6: should read $c ∈ X$. (Upper-case X.)
• Page 15, last line: should read $a n + 1 = x m ∈ X$. (Upper-case X.)
• Page 17, line 8 (first line of proof): ... let $A = ⋃ Y = x ∈ B : B ∈ Y$. Then $A ⊇ C$ for ... (Correcting an obvious typo.)
• Page 20, Exercise 2.34. The ring $R$ should be taken to have an element $1$.
• Page 21, proof of Zorn's lemma: in the proof, the function $u ( C )$ needs to return a strict bound of the chain $C$, and the proof originally given that any two chains in $D$ one is an initial segment of the other can be clarified. Replace the second paragraph of this proof with: We first apply the Axiom of Choice. Considering $X$ as a non-empty set, and $P 0$ the set of all non-empty subsets of $X$, by the Axiom of Choice there is a function $f : P 0 → X$ such that $f ( A ) ∈ A$ for all $A ∈ P 0$. Now let $C ⊆ X$ be a chain. By the Zorn property there is some upper bound, $y ∈ X$, for $C$. Since $X$ has no maximum element there is $y ' ∈ X$ with $y < y '$. In other words, the set $U C = y ∈ X : ∀ x ∈ C x < y$ is non-empty and hence in $P 0$. Thus $f ( U C )$ is a strict upper bound for $C$. Composing functions $C ↦ U C ↦ f ( U C )$ we obtain a function $u$ such that $u ( C )$ is a strict upper bound of $C$ whenever $C ⊆ X$ is a chain.
• Page 22, replace the first complete paragraph on page 22 with: Suppose to start with that there is $x ∈ C 1$ which is not in $C 2$. Then there is a least such $x 1 ∈ C 1 ∖ C 2$, and $C 2 ⊇ y ∈ C 1 : y < x 1$. If $C 2 = y ∈ C 1 : y < x 1$ then $C 2$ is an initial segment of $C 1$ as required, so suppose not. Let $y 1 ∈ C 2$ be least in $C 2 ∖ y ∈ C 1 : y < x 1$. Observe that if $y ∈ C 1$ with $y < x 1$ then $y ∈ C 2$, and as $C 2$ is a chain we must have $y < y 1$ since $x 1 > y ≥ y 1$ is impossible. Thus $y ∈ C 1 : y < x 1 = z ∈ C 2 : z < y 1$ and it follows that $x 1 = u ( y ∈ C 1 : y < x 1 ) = u ( z ∈ C 2 : z < y 1 ) = y 1$ contradicting our assumption that $x 1$ is not in $C 2$. So $C 2$ is an initial segment of $C 1$. If there is $x ∈ C 2$ which is not in $C 1$ then a similar argument shows $C 1$ is an initial segment of $C 2$, and if neither of these applies then $C 1 = C 2$.
• Page 59, line 2 of the proof of Proposition 5.17: least such should read greatest such.
• Page 70, line 4 from bottom: add the word prove just before $⊥$.

This web page is copyright. It is one of Richard Kaye's Logic Web Pages, designed to supplement the book The Mathematics of Logic: a guide to completeness theorems and their applications (CUP, 2007).