Errata for "Elements of Finite Model Theory"
1. Page 21, bibliographic notes. Credits to Chandra/Harel 1980 for
identifying queries as the main object of study in finite model
theory is missing.
2. Page 16, line -16: "In general, Theorem 2.1..." should be
"In general, Theorem 2.6..."
3. Page 39, last paragraph. There is an informal argument that
for more complicated properties combinatorial game proofs are more
involved. While certainly true, the example of an n-ary tree is
not a good one, as a very easy modification of the preceeding proof
(simply by adding extra n-1 edges to each node) shows that being an
n-ary tree is not FO-expressible. (thanks to David Richerby).
5. Page 58, In the definition of \frak{A} \simeq_0^{bij} \frak{B} in
line -1, condition |A|=|B| is missing.
6. Page 64, Exercise 4.14: a basic r-local formula should be
defined as \alpha(\vec x) which is r-local around one of the
variables x_i (in the definition given, \alpha only depends
on x_i).
7. Page 77, line 11: \equiv_k should be \equiv_{k+2}.
8. Page 79, line -7: "q_i <_a p_j" should be "q_i <_a q_j".
9. Page 81, condition (5.8): \equiv_i should be \equiv_{k-i}.
10. Page 106, equation (6.11), \nu_i=t should be \nu_i \subseteq t.
(thanks to Pablo Barcelo for catching the #7-#10).
11. p. 116, line 9: V should be \vec{V}; line 10: \vec{U} should be
\vec{V}.
12. p. 178, definition 10.1, second sentence. "A set X \subseteq A"
should be changed to "A set X \subseteq U"
13. p 178, paragraph 4, fifth sentence: "If X^i \subseteq X^{+1}"
should be changed to "If X^i \subseteq X^{i+1}"
(#10-12, thanks to Anthony Widjaja To)
14. Page 204 (section 10.7). It should be noted that an earlier version
of Gurevich's conjecture asking whether the set of Ptime queries is
r.e. was formulated by Chandra and Harel in 1982. (Thanks to David
Harel for pointing this out).
15. Page 236, line -6, the last expression: 2^{kn+k^2} should be
2^{kn-k^2}. The remaining calculations do not apply, but it is
still very easy to see that the sequence converges to 0.
16. Page 237, line 3: the expression should be divided by
2^{\binom{n}{2}}.
(thanks to Luc Segoufin for catching #14 and #15).
17. Page 256, line 6 should read "\pi(Q(A))=Q(\pi(A))" (thanks to
Steven Lindell).
18. Page 273, exercise 13.17. FO^{gen}_{act}(M,\sigma) should be
FO^{gen}(M,\sigma) (thanks to Anthony Widjaja To)
19. Page 277, the complexity of containment of unions of conjunctive
queries is NP-complete, not \Pi^p_2-complete as stated.
\Pi^p_2-completeness applies if queries are give by relational algebra
expressions, as described in Chapter 6 (thanks to Frantisek Simancik).