[Prev][Next][Index][Thread]
Errata to "What's so special about Kruskal's theorem ..."
Gopalan Nadathur has kindly pointed out that there is a gap in the proof of
theorem 4.5, page 207-208, of my paper
"What's so special about Kruskal's theorem and the ordinal \Gamma_0"
published in the Annals of Pure and Applied Logic, 53 (1991), 199-260.
Specifically, there is a gap in the proof of the
claim that \preceq is a wqo on {\cal D}, (line 11 of page 208).
The problem is that even though t_k \preceq t_h, the proof does not
ensure that k < h (line 16 of page 208).
However, the proof of the claim can be repaired quite
easily using the following observation.
Any bad sequence r = <r_{1},r_{2},\ldots,r_{j},\ldots >
in {\cal D} must contain a bad subsequence
r' = <r_{1}',r_{2}',\ldots,r_{j}',\ldots >
with the following property:
if i < j, then r_{i}' is a subtree of a tree t_{p} and
r_{j}' is a subtree of a tree t_{q} such that p < q.
Indeed, every t_i only has finitely many subtrees, and
r being bad must contain an infinite number of distinct trees.
Thus, we consider a bad sequence r with the additional
property that if i < j, then r_{i} is a subtree of a tree t_{p} and
r_{j} is a subtree of a tree t_{q} such that p < q.
Then, the rest of the proof goes through, since k < h
is now enforced.
If you want an errata page, please send me mail.
-- Jean Gallier