Problem 1035

Prove that if $\leqslant$ is a well-quasi-ordering on a set $X$, but not on $[X]^{<\omega}$, we can construct a bad sequence $\left(A_{n}\right)_{n \in \mathbb{N}}$ in $[X]^{<\omega}$ as follows: Given $n \in \mathbb{N}$, assume inductively that for each $i < n$, $A_{i}$ has already been defined, and there exists a bad sequence in $[X]^{<\omega}$ starting with $A_{0}, \ldots, A_{n-1}$. (This is clearly true for $n=0$: by assumption, $[X]^{<\omega}$ contains a bad sequence, which starts with the empty sequence.) Choose $A_{n} \in [X]^{<\omega}$ such that there is a bad sequence in $[X]^{<\omega}$ starting with $A_{0}, A_{1}, \ldots, A_{n}$, and $|A_{n}|$ is as small as possible.

Clearly, $\left(A_{n}\right)_{n \in \mathbb{N}}$ is a bad sequence in $[X]^{<\omega}$; in particular, for all $n$, $A_{n} \neq \emptyset$. For each $n$, choose an element $a_{n} \in A_{n}$, and let $B_{n} := A_{n} \setminus \{a_{n}\}$.

By Corollary 12.1.2, the sequence $\left(a_{n}\right)_{n \in \mathbb{N}}$ contains an infinite increasing subsequence $\left(a_{n_{i}}\right)_{i \in \mathbb{N}}$. By the minimality of the choice of $A_{n_{0}}$, the sequence
$$A_{0}, \ldots, A_{n_{0}-1}, B_{n_{0}}, B_{n_{1}}, B_{n_{2}}, \ldots$$
is good. Consider a good pair; since $\left(A_{n}\right)_{n \in \mathbb{N}}$ is bad, this pair cannot have the form $\left(A_{i}, A_{j}\right)$ or $\left(A_{i}, B_{j}\right)$ (note that $B_{j} \leqslant A_{j}$). Therefore, it must have the form $\left(B_{i}, B_{j}\right)$. By extending the injection $B_{i} \rightarrow B_{j}$ with $a_{i} \rightarrow a_{j}$, we conclude that $\left(A_{i}, A_{j}\right)$ is good, which is a contradiction.