Errata to "An Introduction to Ramsey Theory"

If you think you found an error that is not listed below, please contact me (jan.reimann@psu.edu).

  • page 54, proof of Theorem 2.12:
    The proof as written does not work, as it is not guaranteed that the \(n_i\) will go to infinity. Thanks to Shamil Asgarli for pointing this out, and for suggesting the following proof.

    We simultaneously define, inductively, an infinite path \(\vec{t} \in [T]\) and a subsequence \( (\vec{s}_{n_k}) \) such that \(\vec{s}_{n_k} \to \vec{t}\) for \(k \to \infty\).

    We put \(t^0 = r\) and \(\vec{s}_{n_0} = \vec{s}_0\). Note that the set \[ S_0 = \{ m \colon s_m^0 = t^0 \} \] is infinite (every sequence passes through the root node).

    Now assume we have defined \(t^0 < \ldots < t^k \), where each \(t^i\) is in \(T\) and an immediate predecessor of \(t^{i+1}\), and \(\vec{s}_{n_0}, \ldots, \vec{s}_{n_k} \) such that the set \[ S_k = \{ m \colon s_m^0 = t^0, \ldots, s_m^k = t^k \} \] is infinite. Note that all sequences in \(S_k\) have distance at most \(2^{-k}\) from each other in the path metric, since they all have the same first \(k\) elements. \(S_k\) is infinite and \(T\) is finitely branching, hence by the pigeonhole principle we can find an immediate successor \(t^{k+1} \in T\) of \(t^k\) such that \[ S_{k+1} = \{ m \colon s_m^0 = t^0, \ldots, s_m^k = t^k, s_m^{k+1} = t^{k+1} \} \] is infinite. Let \(n_{k+1}\) be the smallest number \(m \in S_{k+1}\) that is greater than \(n_k\).

    Since all \(t^k\) are on \(T\), they define an infinite path \[ \vec{t} = t^0 \, t^1\, t^2 \, \ldots \in [T]. \] By definition of \(t^k\), \(d(\vec{t}, \vec{s}_{n_k}) \leq 2^{-k}\), and thus \((\vec{s}_{n_k})\) converges to \(\vec{t}\) in the path metric.

  • page 75, line 20:
    The sentence starting with “Pick the \(\prec\)-least element \(\ldots\)” should read: “Pick the \(\prec\)-least element \(x_{\alpha_1}\) of \(Z_1\) (which must exist since \(\prec\) is a well-ordering) and observe that \(\{y \in Z_1: c(x_{\alpha_1},y) = \text{red} \} \) is again uncountable.”
    [Thanks to Shamil Asgarli for catching this.]

  • page 158, big formula (formal statement of Ramsey’s theorem):
    The last line of the formula is incorrect – we need to check each entry in the argument of the function whether it is an element of the set coded by \(z\). The line should read as follows: \[ \forall m \leq l \: ( \, \forall s \leq p \exists i \leq k (\operatorname{decode}(\operatorname{arg}(f,m),s)=\operatorname{decode}(z,i)) \; \Rightarrow \; \operatorname{val}(f,m)=j \,) \] [Thanks to Vineet Gupta and Adnan Aziz for pointing this out.]

  • page 180, proof of Proposition 4.46:
    The transition from the formula \(\mathcal{N} \models \exists x_1 \forall x_2 \ldots \exists x_n \: \psi(a, \vec{c}, \vec{x})\) to the \(\Delta_0\) formula using “meta”-quantifiers needs further justification. In particular, it does not follow inductively by simply applying logical equivalences. Instead, the property of indiscernibles has to be invoked at this step already.

    Click here for an improved writeup of the argument (covering the remainder of the proof of Proposition 4.46)

    Thanks to Michael Weiss for bringing up this important issue. Michael has a blog diagonalargument.com I recommend. Among other entries, there is a series of “conversations” with John Baez about non-standard models of PA. Here is the first entry. Check it out!

    Finally, for the connoisseurs, Michael has provided a proof of the above transition that does not use indiscernibility: PDF file

  • page 182, Definition 4.48:
    The definition should read:
    Let \(X \subseteq \mathbb{N}\), \(n \geq 1\), and suppose \(f: [X]^n \to \mathbb{N}\). A set \(M \subseteq X\) with \(|M| > n\) is min-homogeneous if for every \(s, t \in [M]^n\), \[ \min s = \min t \; \Rightarrow \; f(s) = f(t). \] [Thanks to Vineet Gupta and Adnan Aziz]

  • page 186/187, proof of Lemma 4.52:
    At several places \([W]^{n+1}\) should be \([Y]^{n+1}\) instead: page 186, lines 3, 6, last line of the second last paragraph, and page 187, line 2.

    [Thanks to Vineet Gupta and Adnan Aziz]