Past exam of the mathematics course of the University of Cambridge / 2007 / iii / Paper 26 (Set Theory and Logic)

Here an ultralimit in the model-theoretic sense is a model-theoretic ultralimit: start with a first-order structure, take successive ultrapowers along their diagonal elementary embeddings, and take the directed limit of elementary embeddings of that chain. The elementary chain theorem, proved by induction on formulas after identifying the embeddings with inclusions, makes every stage elementary in the limit. This definition concerns structures, rather than the topological ultrafilter limit.

We first prove the needed Frayne embedding lemma. If $C\equiv D$, every finite subset of the elementary diagram of a structure $D$ can be realized in $C$: existentially quantify its finitely many named elements, and use elementary equivalence. Index by finite diagram fragments, choose such realizations, and extend the filter of cones requiring each diagram formula to an ultrafilter. For each $d\in D$, let $f_d$ give its chosen coordinate realizations, filling unspecified coordinates arbitrarily. The Łoś theorem shows that $d\mapsto [f_d]$ is an elementary embedding of $D$ into an ultrapower of $C$. The formulas $c_d\ne c_e$ ensure injectivity.

There is a relative version: if $C⪯D$, keep all named elements from $C$ constant in every coordinate. Each finite diagram fragment is realizable in $C$ over those parameters by elementarity, so the resulting embedding extends the diagonal embedding of $C$ into its ultrapower.

Now use alternating ultrapowers give isomorphic ultralimits. First embed $B$ into an ultrapower $A_1$ of $A$. Apply the relative lemma to $B⪯A_1$, embedding $A_1$ into an ultrapower $B_1$ of $B$ over its diagonal copy. Next embed $B_1$ into an ultrapower $A_2$ of $A_1$ over $A_1$, and continue. After coherent identifications this givesEach $A_{n+1}$ is an ultrapower of $A_n$ along its diagonal embedding, and each $B_{n+1}$ is an ultrapower of $B_n$ likewise. The two subsequences are cofinal in the same chain of elementary substructures, so their limits are the same union. Hence $\boxed{A\equiv B⟹A_{\infty }\cong B_{\infty }}$. No isomorphism theorem for single ultrapowers has been assumed.

Order the collection $\mathrm{Ch}(P)$ of all chains in a partial order, including the empty chain, by inclusion. Suppose that $f:\mathrm{Ch}(P)\to P$ were an order-preserving injection. The chain-poset nonembedding lemma follows by a transfinite recursion of length the Hartogs ordinal $h(P)$:Inductively, the previously constructed points form a strictly increasing chain. If $\beta <\alpha$, then $C_{\beta }⊊C_{\alpha }$, since $p_{\beta }$ belongs to the latter but not the former. Monotonicity gives $p_{\beta }\le p_{\alpha }$, and injectivity makes this inequality strict. Thus the recursion continues at every $\alpha <h(P)$ and gives an injection $h(P)\to P$, contradicting the defining property of the Hartogs ordinal. Therefore $\boxed{\mathrm{Ch}(P)\text{ has no order-preserving embedding into }P.}$ The empty chain is part of the convention: excluding it would make a one-point poset a counterexample.

Suppose a nonempty set $S$ had no minimal member for the intersection-power-set predecessor relation. Put $b=\bigcap S$, which is a set by separation. For every $y\in S$ there is an $x\in S$ with $\mathcal{P}(x\cap y)\subseteq y$. Since $b\subseteq x\cap y$, this gives $\mathcal{P}(b)\subseteq y$. Intersecting over every $y\in S$ yields $\mathcal{P}(b)\subseteq b$.

Now form the diagonal subset $d=\{u\in b:u\notin u\}$. It belongs to $\mathcal{P}(b)$, hence to $b$, so its defining condition implies $d\in d⟺d\notin d$, a contradiction. Thus $\boxed{R\text{ is well-founded}.}$ This is a Cantor diagonal argument; it uses neither the Axiom of foundation nor the axiom of choice. In particular, no selection of an infinite descending sequence is needed.

Use the embedding characterization of a supercompact cardinal: for every cardinal $\mu \ge \kappa$ there is an elementary embedding $j:V\to M$ into a transitive class with critical point $\kappa$, $j(\kappa )>\mu$ and $M^{\mu }\subseteq M$. In the Lévy hierarchy, a ${\Sigma }_2$ sentence can be put into the form $\exists x\forall y\theta (x,y)$ with bounded matrix $\theta$. The same argument allows parameters $p\in V_{\kappa }$, which the embedding fixes.

Suppose $V\models \exists x\forall y\theta (x,y,p)$ and choose a witness $a$. Pick an ordinal $\lambda$ with $a,p\in V_{\lambda }$, and a cardinal $\mu \ge \kappa$ large enough that $\mu \ge |V_{\lambda }|$ and $\mu >\lambda$. Take the corresponding supercompact embedding. Its closure implies $V_{\lambda }\subseteq M$: induct on rank, enumerate each set in this rank segment by at most $\mu$ elements already in $M$, and use $M^{\mu }\subseteq M$ followed by taking the range. Thus $a\in M$ and $\mathrm{rank}(a)<j(\kappa )$.

Bounded formulas are absolute between transitive classes. Since $\forall y\theta (a,y,p)$ holds in $V$, it holds in $M$ and then in the transitive rank segment $V_{j(\kappa )}^M$. This segment contains $a,p$, soApply elementarity to the first-order assertion that this sentence holds in the indicated cumulative hierarchy level, and use $j(p)=p$. We obtain the supercompact Sigma-two downward reflection conclusionThe closure requirement is used to put the original witness into the target; elementarity alone would not do that.

In an infinite game of perfect information, the players alternately choose elements of a nonempty set $A$, producing $x\in A^{\omega }$. Player I wins when $x$ belongs to the payoff set $B$. A strategy in an infinite game chooses a move at each position where its player moves, and a winning strategy in an infinite game wins against every possible opposing play. The Gale-Stewart theorem states that such a game is determined when $B$ is open in the product topology of discrete $A$. The same holds for closed payoff sets and, more strongly, for every $G_{\delta }$ payoff set.

For open determinacy, let $P=A^{<\omega }$ be the positions and $D=\{s:[s]\subseteq B\}$ the prefixes certifying a win for I, where $[s]$ is the extension cylinder set. Form the winning-position attractor in an infinite game by transfinite recursion: start at $W_0=D$, at a successor stage add I-positions with some successor already in $W_{\alpha }$ and II-positions with all successors in $W_{\alpha }$, and take unions at limits. This increasing sequence stabilizes, since its positions form a set. Call the stable set $W$.

Each position in $W\setminus D$ has a least entry ordinal, necessarily a successor. I chooses a successor with smaller entry ordinal; every II successor has smaller entry ordinal. An infinite strictly decreasing sequence of ordinals is impossible, so play reaches $D$ in finitely many moves. This gives I a winning strategy in an infinite game from every position in $W$. Outside $W$, all I moves stay outside, while II can choose a move outside. The axiom of choice selects those moves simultaneously. Such a play never reaches $D$, so it is outside the open payoff set. Thus II wins from the complement of $W$, proving determinacy. Interchanging the players and complementing the payoff gives closed determinacy.

We prove the $G_{\delta }$ strengthening via Buchi games, including their determinacy argument. On a set of positions $S$ with nonempty successor sets, putFor a specified set $F$ of marked positions, I's objective is to visit $F$ infinitely often. For each $X\subseteq S$, let $H(X)$ be the least fixed point obtained by starting $Y_0=\varnothing$ and iteratingwith unions at limits. Its inner entry ranks let I force a visit to $F\cap \mathrm{Pre}(X)$. The operation $H$ is monotone. Starting at $X_0=S$, iterate $X_{\alpha +1}=H(X_{\alpha })$ with intersections at limits. This descending sequence stabilizes at $W=H(W)$.

From $W$, the inner ranks force a marked position with a next move still in $W$. I chooses such a move, and the construction repeats. At II-positions all necessary moves stay in the indicated inner attractor, or in $W$ at a marked position. Every round takes finitely many moves by decreasing inner ranks. I therefore forces infinitely many marked visits.

For $s\notin W$, let $\alpha$ be its removal rank: $s\in X_{\alpha }\setminus X_{\alpha +1}$. Since $s\notin H(X_{\alpha })$, at I's turn all successors lie outside $H(X_{\alpha })$, and at II's turn there is a successor outside it. II chooses such successors. If also $s\in F$, then $s\notin \mathrm{Pre}(X_{\alpha })$; II can choose outside $X_{\alpha }$, or every I move lies outside $X_{\alpha }$. Along this strategy removal ranks never increase and strictly decrease after each marked visit. Infinitely many visits would give an infinite ordinal descent, so II wins. This proves Buchi game determinacy on a set-sized arena without any countability restriction.

Now write the original payoff as $B={\bigcap }_{n<\omega }{U}_n$, with each $U_n$ open. Add a deterministic monitor to the finite position, initially $n=0$. At each new prefix, if its cylinder is contained in $U_n$, increment the monitor and mark that step. For a play $x$, the monitor increments infinitely often exactly when $x\in B$. In one direction every increment certifies the next required open set. In the other, after the monitor reaches $n$, openness of $U_n$ supplies a later certifying prefix, so it eventually reaches $n+1$. The expanded game is a Buchi game; its monitor is determined by the observed finite play, so its winning strategy transfers directly to the original game. ConsequentlyComplementing and interchanging players also gives determinacy for $F_{\sigma }$ payoff sets. These arguments work on pruned game subtrees as well, and assigned terminal winners can be incorporated by replacing each terminal position by an absorbing position with the corresponding outcome.

Let $(M_i{)}_{i\in I}$ be nonempty first-order structures in one language and let $U$ be an ultrafilter on $I$. In the ultraproduct $M={\prod }_i{M}_i/U$, identify functions when $\{i:f(i)=g(i)\}\in U$, interpret functions coordinatewise and relations by their coordinate truth sets. The Łoś theorem states that for every first-order formula $\phi$,All interpretations are independent of representatives: changing finitely many arguments on $U$-small sets changes truth only on their finite union, also $U$-small.

Prove the theorem by structural induction on formulas. Terms evaluate coordinatewise by induction on terms. This proves the atomic cases of logical equality and relation symbols. For conjunction, intersect the two truth sets and use the filter laws. For negation, the truth set is complemented, and an ultrafilter contains exactly one of a set and its complement. These cases supply the other Boolean connectives too.

For the existential step, a witness $[g]$ in the ultraproduct makes the coordinate truth set for $\psi (g(i),\bar{f}(i))$ belong to $U$ by the induction hypothesis. That set is contained in the coordinate truth set of $\exists x\psi (x,\bar{f}(i))$, so the latter is in $U$. Conversely, if that existential truth set $J$ belongs to $U$, choose a witness $g(i)$ in $M_i$ for each $i\in J$, and any element of $M_i$ elsewhere. The axiom of choice supplies this function. The induction hypothesis makes $[g]$ a witness in the ultraproduct. Universal quantification follows by negation. This completes the proof.

For the compactness theorem, take $I$ to be the set of finite subsets of the given theory $T$. For each $s\in I$, choose $M_s\models s$. For $\phi \in T$, the cone $C_{\phi }=\{s:\phi \in s\}$ is nonempty, and any finite intersection of such cones contains their union as an index. Extend the filter they generate to an ultrafilter $U$. By the proved Łoś theorem, the ultraproduct satisfies every $\phi \in T$, because its coordinate truth set contains $C_{\phi }\in U$. Thus $\boxed{\prod _{s\in I}{M}_s/U\models T}$. This proves compactness without assuming it in the ultraproduct construction.

The Ehrenfeucht-Mostowski theorem asserts that an infinite first-order structure has, for any prescribed total order $I$, an elementary extension containing distinct order-indiscernibles $(c_i{)}_{i\in I}$. After a Skolem expansion, the Skolem hull of those generators is a model of the original complete theory. Every order automorphism of $I$ extends to a unique automorphism of this specified Skolem hull in the expanded language.

Choose a Skolem expansion $M^{\ast }$ of the original infinite structure: for each existential formula, select a witness function, including nullary functions when needed. Add constants $c_i$ for $i\in I$ and the elementary diagram of a structure of $M^{\ast }$, using separate names for its elements. Require $c_i\ne c_j$ for distinct indices, and for each formula $\phi$ in the Skolem language requirewhenever both index tuples are strictly increasing. These are the order-indiscernible sequence requirements.

Every finite fragment is satisfiable in $M^{\ast }$. Choose a countably infinite sequence of distinct elements of $M^{\ast }$. The fragment mentions only finitely many formulas and arities. Color increasing $k$-tuples of that sequence by the finite vector of truth values of its relevant $k$-ary formulas. The Ramsey theorem supplies an infinite homogeneous subsequence; repeat for the finitely many arities. Assign the finitely many named $c_i$ to distinct elements of the final homogeneous subsequence in increasing index order. The fixed finite part of the elementary diagram of a structure already holds in $M^{\ast }$. By the compactness theorem proved in Question 5, the full set of requirements has a model $N^{\ast }$, giving the required elementary extension and order-indiscernible sequence.

Let $H$ comprise all values of Skolem-language terms in finitely many $c_i$. It is closed under the witness functions. If $N^{\ast }\models \exists x\psi (x,\bar{h})$ for parameters in $H$, the specified witness function supplies a witness in $H$. Induction on formulas therefore gives $H⪯N^{\ast }$; its reduct is a model of $\mathrm{Th}(M)$. For infinite $I$, its cardinality is at most $\max (|I|,|L^{\ast }|,{\aleph }_0)$ and at least $|I|$.

For an order automorphism $\alpha :I\to I$, defineRewrite any finite list of indices in increasing order, allowing a term to repeat or omit variables. The order-indiscernible sequence property transfers every equality between terms and every relation among their values, making this definition well defined and elementary. Applying ${\alpha }^{-1}$ gives its inverse. All of $H$ is generated by the $c_i$ and the named Skolem functions, so an automorphism extending $\alpha$ must have precisely this action. Thus $\boxed{\mathrm{Aut}(I)\hookrightarrow \mathrm{Aut}(H^{\ast })}$, with uniqueness in the Skolem expansion. This uniqueness need not hold in the unexpanded reduct.

A measurable cardinal is an uncountable cardinal $\kappa$ carrying a nonprincipal ultrafilter $U$ on $\kappa$ that is $\kappa$-complete: intersections of fewer than $\kappa$ members of $U$ remain in $U$. An elementary embedding $j:M\to N$ preserves truth of every first-order formula, with its parameters carried along by $j$.

The identity is always an elementary embedding of the universe into itself. The substantive question concerns a nonidentity embedding. In ZFC, the Kunen inconsistency theorem givesHere, as usual for class embeddings, restrictions to sets and the recursively defined critical sequence are available. We give the stationary-set proof, including its partition ingredient.

Suppose such a $j$ existed. It has a least moved ordinal $\kappa$, its critical point of an elementary embedding. To see why some ordinal must move, if all ordinals were fixed, induction on rank would fix every set: membership of $z$ in $j(x)$ is equivalent to membership of $z$ in $x$ once every lower-rank $z$ is fixed. A rank segment containing a moved set would then be fixed pointwise, a contradiction. The critical point is an uncountable cardinal. All finite ordinals and $\omega$ are definable and fixed. If $\kappa$ had cardinality $\mu <\kappa$, a bijection $f:\mu \to \kappa$ would be carried to a surjection $j(f):\mu \to j(\kappa )$ whose range still consists exactly of the fixed ordinals below $\kappa$, impossible since $j(\kappa )>\kappa$.

Put ${\kappa }_0=\kappa$, ${\kappa }_{n+1}=j({\kappa }_n)$ and $\lambda ={\sup }_{n<\omega }{\kappa }_n$. Applying $j$ to this Kunen critical sequence shifts it by one, so $j(\lambda )=\lambda$. Elementarity also gives $j({\lambda }^{+})={\lambda }^{+}$; write $\theta ={\lambda }^{+}$.

We need a stationary partition at a successor cardinal. If $S\subseteq {\lambda }^{+}$ is stationary, choose bijections $e_{\beta }:\lambda \to \beta$ for $\lambda \le \beta <{\lambda }^{+}$. For each $\xi <{\lambda }^{+}$, on the stationary tail $\{\beta \in S:\beta >\max (\lambda ,\xi )\}$ the function $\beta \mapsto e_{\beta }^{-1}(\xi )$ is regressive. The Fodor lemma supplies a stationary fiber $E_{\xi }$ with constant value $i_{\xi }<\lambda$. Some value $i$ occurs for ${\lambda }^{+}$ many $\xi$, since a union of $\lambda$ sets each of size at most $\lambda$ cannot have size ${\lambda }^{+}$. For distinct such $\xi$, their fibers are disjoint: $e_{\beta }(i)$ cannot equal two different ordinals. These fibers yield ${\lambda }^{+}$ disjoint stationary subsets; include any leftover points in one cell. Grouping cells also gives a partition into any nonzero number at most ${\lambda }^{+}$.

For completeness, the Fodor lemma used here follows from diagonal intersections of clubs. If a regressive function $f:S\to \theta$ had no stationary fiber, choose a club set $C_{\xi }$ disjoint from each fiber. The diagonal intersection $\{\beta <\theta :\forall \xi <\beta (\beta \in C_{\xi })\}$ is club by regularity and closure. A point $\beta$ in its intersection with $S$ would belong to $C_{f(\beta )}$, contradicting the choice of that club.

The set $S=\{\beta <\theta :\mathrm{cf}(\beta )=\omega \}$ is stationary: inside any club choose a strictly increasing countable sequence, whose supremum still lies below the regular uncountable $\theta$ and belongs to the club. Partition it as $⟨S_{\alpha }:\alpha <\kappa ⟩$. Its image $⟨T_{\alpha }:\alpha <j(\kappa )⟩$ is another stationary partition of the same $S$.

The set $C=\{\beta <\theta :j‘‘\beta \subseteq \beta \}$ is club. Closure is immediate. To get a member above any given ordinal, repeatedly bound the images of all earlier ordinals and take a countable supremum; regularity of $\theta$ keeps each bound below $\theta$. Choose $\beta \in C\cap T_{\kappa }$. Since $\mathrm{cf}(\beta )=\omega$, a countable cofinal sequence in $\beta$ and $j(\omega )=\omega$ give $j(\beta )=\beta$: the image sequence remains below $\beta$ by closure under $j$, and $j(\beta )\ge \beta$.

But $\beta \in S_{\alpha }$ for some $\alpha <\kappa$. Applying $j$ and using $j(\alpha )=\alpha$ gives $\beta =j(\beta )\in T_{\alpha }$, contradicting its membership in the disjoint cell $T_{\kappa }$. This proves the assertion. The use of axiom of choice in the cardinal and stationary-partition arguments matters; the conclusion here is explicitly in ZFC.

Write ${\mathsf{ZF}}^{-}$ for ZF with the Axiom of foundation omitted. Independence is a relative-consistency assertion: from a model of ZFC we construct models of ${\mathsf{ZF}}^{-}+\neg \mathsf{Foundation}$, both with and without axiom of choice. A model of ZFC itself supplies the positive cases.

First use a Rieger-Bernays permutation model. Inside the starting model choose a definable class bijection $\pi$ and put $xEy$ exactly when $x\in \pi (y)$. The new extension of $y$ is the old set $\pi (y)$, so any prescribed set of new members $b$ has representative ${\pi }^{-1}(b)$. We verify the axioms rather than treating the change of membership as automatically harmless.

The axiom of extensionality follows from injectivity of $\pi$. The new empty set is ${\pi }^{-1}(\varnothing )$ and a pair with members $a,b$ is ${\pi }^{-1}(\{a,b\})$. The union of a new set $x$ is represented byA new subset $z$ of $x$ means $\pi (z)\subseteq \pi (x)$. Hence the new power set of $x$ is represented byThese are sets by the original power-set and replacement axioms. Translate each formula by replacing membership with $E$. The original separation axiom extracts the required subset of $\pi (x)$, and replacement collects the range of a definable functional relation on $\pi (x)$; applying ${\pi }^{-1}$ gives their new representatives. Thus the full Axiom schema of replacement and separation schemes survive.

For axiom of infinity, start at $e={\pi }^{-1}(\varnothing )$, iterate the new successor $s_E(x)={\pi }^{-1}(\pi (x)\cup \{x\})$ along the old $\omega$, and take a new set representing this range. It contains the new empty set and is closed under the new successor. Finally, the old axiom of choice well-orders each old extension $\pi (x)$. Encode that relation using new ordered pairs and its new set representative. All subsets of the extension are represented in the new model, so this is genuinely a new well-order. Thus choice survives the full membership permutation.

Now transpose the old $\varnothing$ and $\{\varnothing \}$ and fix every other object. The old empty set $q=\varnothing$ satisfies $\pi (q)=\{q\}$, so its sole new member is itself: it is a Quine atom. The nonempty new set $q$ has no member disjoint from it, violating foundation. This gives $\boxed{\mathrm{Con}(\mathsf{ZFC})⟹\mathrm{Con}({\mathsf{ZF}}^{-}+\mathsf{AC}+\neg \mathsf{Foundation})}$. Together with the starting model, this proves independence of foundation.

For failure of choice, a membership permutation alone is insufficient, as the verification above shows. Add a symmetry restriction. Choose distinct old objects $a_n=\{\omega ,n\}$ for $n<\omega$ and let $\pi$ simultaneously swap $a_n$ with $\{a_n\}$, fixing all other objects. The two families are disjoint, so this is a class bijection. Each $a_n$ is now a Quine atom. Write $A$ for the new set having precisely these atoms as members.

Every permutation of the atoms extends to an automorphism of the new universe, fixing its pure well-founded part. To construct it, send the atoms according to the prescribed permutation and, for any other object $x$, take the unique object whose new members are the images of its new members. This recursion is well founded away from the atomic self-loops: every other membership step decreases old rank, including the steps from the transposed singletons to their old extensions. Thus all the required automorphisms exist.

An object is supported by a finite set $F\subseteq A$ if every atom permutation fixing $F$ pointwise fixes it. Let $H$ consist of objects that have finite support in a permutation action and all of whose new membership descendants also have finite support in a permutation action. This is the hereditarily finite-supported Quine-atom model. The atoms belong to $H$, as does $A$ itself. We check that restricting $E$ to $H$ preserves ${\mathsf{ZF}}^{-}$.

Extensionality is inherited because every member of an object of $H$ is again in $H$. Empty sets, pairs and unions have supports obtained by taking finite unions of the supports of their parameters, and their descendants are already supported. The pure natural numbers and their set are fixed by every atom permutation, giving infinity. For separation, permutations fixing the domain and formula parameters preserve the defined subset, which therefore has their common finite support in a permutation action. For replacement, translate the relativized formula into the original universe and use original replacement to collect its unique values. Every value lies in $H$, and the range is invariant under the same finite support in a permutation action. Finally, the collection of all $H$-subsets of an object $x\in H$ is a subcollection of its full new power set, hence is a set in the original universe. Every permutation fixing a support of $x$ permutes these supported subsets, so this collection is supported; its members and their descendants lie in $H$. This verifies the internal power-set axiom. These arguments handle the full schemes with arbitrary finite tuples of parameters.

There is no choice function on the two-element subsets of $A$ in $H$. Suppose $f$ were one and had finite support in a permutation action $F$. Choose distinct atoms $a,b\notin F$. The transposition exchanging them fixes $f$ and the unordered pair $\{a,b\}$, but exchanges its two possible selected values. Thusis impossible. The family of all such pairs belongs to $H$: it is invariant under every atom permutation and each pair has finite support in a permutation action. Therefore $H\models \neg \mathsf{AC}$; it still contains the self-membered atoms, so it also fails foundation. We have provedThe positive-choice permutation model and this negative-choice symmetry model establish independence of choice from ${\mathsf{ZF}}^{-}$. These constructions can be carried out internally in any starting model; no assumption of a transitive set model is needed.

Use rooted-tree homeomorphic embedding: an injective map of vertices preserves ancestor order and lowest common ancestors, so edges may be stretched into paths and distinct branches remain distinct. The source root may map below the target root. Kruskal's tree theorem asserts that finite rooted trees are well-quasi-ordered by this embedding: every infinite sequence $T_0,T_1,\dots$ has $i<j$ with $T_i⪯T_j$. More generally, labels from any well-quasi-ordering may be required to increase under the embedding. This labelled result implies the unlabelled one by using a one-point label set, and also implies the version for unrooted trees by choosing roots arbitrarily.

We first prove the word lemma needed for the tree argument. In a well-quasi-ordering $Q$, every infinite sequence has an infinite nondecreasing subsequence. Indeed, some term must be below infinitely many later terms: if no term were, recursively avoiding the finitely many successors dominated by each previously chosen term would produce a bad sequence. Repeat this observation inside the infinite set of later terms dominating the chosen one.

The Higman lemma says that finite words over $Q$ are well-quasi-ordered by subsequence embedding with letterwise comparison. Suppose otherwise, and choose a minimal bad sequence of words, minimizing length at each position among words admitting a bad continuation of the chosen prefix. No word is empty. Write $w_i=v_i{a}_i$, separating its last letter. Choose indices $i_0<i_1<\cdots$ on which $a_{i_j}$ is nondecreasing. Thenis bad. A comparison from a prefix word into some $v_{i_j}$ would give a comparison into $w_{i_j}$ in the old bad sequence. A comparison $v_{i_j}⪯v_{i_k}$, $j<k$, together with $a_{i_j}\le a_{i_k}$ would give $w_{i_j}⪯w_{i_k}$. Both are impossible. But the new continuation uses a shorter word at position $i_0$, contradicting minimality. This proves the Higman lemma.

Now suppose there were a bad sequence of labelled finite rooted trees. Choose it minimally by number of vertices at each position. Let $\mathcal{P}$ be the collection of all proper rooted subtrees occurring at vertices other than the roots in these trees. We claim that $\mathcal{P}$ is well-quasi-ordered. Otherwise take a bad sequence of such subtrees $S_j$, with $S_j$ a proper subtree of $T_{i_j}$. The indices cannot remain bounded, because finitely many finite trees have only finitely many rooted subtrees, and repetition is a comparison. Pass to a subsequence with strictly increasing $i_j$. The sequenceis bad: a comparison from an earlier $T_h$ into $S_j$ would compose with the subtree embedding $S_j⪯T_{i_j}$ to contradict the original badness. Its other comparisons were excluded already. Since $S_0$ has fewer vertices than $T_{i_0}$, this contradicts minimality, proving the claim.

List each tree's immediate root subtrees in any chosen order. These are finite words over $\mathcal{P}$, hence form a well-quasi-ordering by the word lemma. Combine the lists with the root labels. A product of two well-quasi-orders is well-quasi-ordered: pass to an infinite nondecreasing subsequence in the first coordinate and find a comparable pair in the second. Thus two trees have comparable root labels and a subsequence matching of their child lists. Map the first root to the second root and use the matched subtree embeddings in distinct child branches. The resulting injective map preserves labels and lowest common ancestors, giving $T_i⪯T_j$, the desired contradiction. This proves the full labelled form of Kruskal's tree theorem.

Friedman's finite form of Kruskal's theorem is a uniform finite consequence. For every fixed natural $k$, there is $N$ such that any sequence of $N$ finite rooted trees satisfying $|T_i|\le k+i$ has a comparable pair $i<j$. It also holds with labels in any fixed finite label set. To prove it, assume no such $N$ exists. Form the finite bad-sequence tree whose nodes are bad finite tree sequences satisfying those size bounds, using one representative of each isomorphism type. Each position has finitely many extensions, since there are finitely many labelled tree types of each bounded size. By assumption this finitely branching tree has nodes at every finite height. The König infinity lemma supplies an infinite branch, which is an infinite bad sequence of trees, contradicting the theorem just proved. HenceLikewise, using $k$ fixed labels with the bound $|T_i|\le i$ for $i=1,2,\dots$ gives the customary finite labelled tree form. Only existence of its finite bound is claimed here, not a small numerical estimate.

We prove the Borel determinacy theorem by reducing each Borel game to a clopen game while preserving winning strategies. The construction permits arbitrary set-sized alphabets; no enumeration of the move set is used. Assume $A\ne \varnothing$. For an empty alphabet the game ends at its initial position, with its assigned terminal outcome, and is trivially determined.

Allow intermediate game trees $T$ to have terminal positions with assigned winners. Write $[T]$ for the space of infinite branches, with its prefix-cylinder topology; the payoff $B\subseteq [T]$ governs infinite plays, while the assigned winners govern finite plays. Question 4's attractor proof still gives open and clopen determinacy: include I-winning terminals among the initial targets and make the opposing terminals absorbing losses.

A covering of an infinite game consists of a new tree $\tilde{T}$, a prefix-preserving map $\pi :\tilde{T}\to T$ preserving lengths, and a strategy map $\Phi$ for each player. Old terminal outcomes must be inherited. The strategy map is local in depth: choices before depth $n$ depend only on the given strategy before depth $n$. Its essential lifting requirement is that each original play $x$ following $\Phi (\sigma )$ has a lift $\tilde{x}$ following $\sigma$ whose projection is $x$, or whose projection is an initial segment of $x$ and which ends with a loss for the player using $\sigma$. Infinite projections are taken by union of prefixes. A $k$-covering is identical to the original tree, terminal assignments and strategy choices through depth $k$.

These conditions transfer winning strategies for every payoff. Indeed, if $\sigma$ wins the covered game with payoff ${\pi }^{-1}(B)$, a lift of a play following $\Phi (\sigma )$ cannot be an early loss for its player. The lift therefore projects to the whole original play. Infinite membership in $B$ agrees under projection, and an original terminal loss would also be a loss in the game covering. Hence the original play is won. Call a game covering an unravelling of a game payoff when ${\pi }^{-1}(B)$ is clopen in $[\tilde{T}]$.

We first construct a $k$-covering unravelling any closed $C\subseteq [T]$. Choose an even $m\ge k$ and leave the first $m$ levels unchanged. At a nonterminal position $p$ of length $m$, I's next move will carry auxiliary information. For each legal ordinary move $a$, let $Z$ be the set of first nonterminal positions strictly beyond $pa$ whose infinite continuations miss $C$: $q\in Z$ means $q$ extends $pa$, $[T_q]\cap C=\varnothing$, and no intervening strict extension of $pa$ has this property. These positions are pairwise incomparable. I plays $(a,X)$, where $X\subseteq Z$.

If $pa$ was already terminal, inherit its outcome. Otherwise II has two types of response. On accepting, II plays $(\mathrm{accept},b)$ with $b$ an ordinary legal move, and subsequent moves are ordinary. When a position $q\in Z$ is reached, end the covered game with a win for I if $q\in X$ and for II if $q\notin X$. Other old terminals retain their winners. On challenging, II plays $(\mathrm{challenge},q,b)$ with $q\in X$ and $pab$ an initial segment of $q$; subsequent play is forced along $q$ until reaching it and then proceeds ordinarily in $T_q$. Original terminal outcomes remain in force. Forget the auxiliary data to define $\pi$.

For an infinite accepted play, no exit in $Z$ was reached. Its projection belongs to $C$: if it did not, closedness would give a prefix cylinder disjoint from $C$, and the first such nonterminal extension strictly beyond $pa$ would have ended the play. An infinite challenged play projects through an exit $q$ and therefore misses $C$. Thus, among infinite plays, the inverse image of $C$ is exactly the acceptance branch of this finite protocol. It is clopen, decided at depth $m+2$.

Here are both strategy-transfer maps; these are necessary because continuous projection by itself does not preserve determinacy. Given a strategy $\sigma$ for I in the covered tree, follow its ordinary moves while simulating acceptance of its announcement $X$. If an exit $q\notin X$ is reached, continue arbitrarily: that play has an early covered loss for I as a lift. If $q\in X$ is reached, switch to the continuation prescribed by $\sigma$ under the challenge of $q$. This is consistent with the already observed prefix, since the challenged game forced every intermediate move along $q$. If no exit is reached, acceptance itself supplies the full lift. Old terminal plays lift in the same way. This defines $\Phi (\sigma )$ and verifies the lifting requirement for I.

For a covered strategy $\tau$ for II, at the projected position $pa$ defineAgainst announcement $Y$, the strategy must accept: a challenge would have to name an element of $Y$, contradicting its definition. Simulate this acceptance, including its ordinary response $b$. If an exit $q\in Y$ is reached, it is an early covered loss for II, so continue arbitrarily. If an exit $q\notin Y$ is reached, choose an announcement $X_q$ for which $\tau$ challenges $q$, and switch to that simulation. The challenged game's forced prefix agrees with the observed prefix, including the earlier ordinary response $b$, so it supplies a full lift following $\tau$. If no exit is reached, the original acceptance simulation gives the full lift. This defines $\Phi (\tau )$ and verifies lifting for II. Choices of $X_q$ use the axiom of choice on a set of possibilities.

Both maps are local in depth. The sets $Y$ and the chosen $X_q$ use only II's response function at depth $m+1$; later choices use only strategy values at the already reached depth. The switches do not query choices at later levels. On irrelevant histories assign fixed legal moves. Thus this is a genuine $k$-covering. Complementing $C$ changes neither the game covering nor its lifting property, and complements of clopen sets are clopen. This proves the base construction for both closed and open payoff sets.

We next give the limiting construction needed for the induction. Coverings compose by composing their position and strategy maps; lifting successively verifies the same lifting condition. Supposeis a sequence of game coverings whose $i$th map leaves depth $k+i$ unchanged. For each finite depth $d$, the trees and terminal assignments through that depth eventually stop changing. Define $T_{\infty }$ using these stabilized levels. Its map to $T_i$ on a position of length $d$ is the composite from any sufficiently late stage; stabilization makes the value independent of the stage. Define strategy maps in the same way, using their locality in depth. These maps respect the tree, terminal outcomes and composition, and leave depth $k$ unchanged.

To check lifting, start with a play of $T_i$ consistent with the projected strategy. Lift the entire play successively through the later game coverings, using the corresponding projected strategy at each stage. If all these lifts are infinite, each projects to the preceding one and each finite prefix eventually stabilizes, giving the desired infinite lift in $T_{\infty }$. If a premature own-player loss occurs, later lifts have nonincreasing finite lengths, and those lengths and their prefixes eventually stabilize. This gives a terminal own-player loss in $T_{\infty }$, which is exactly the allowed exceptional lift. The same reasoning handles original finite terminal plays. Thus $T_{\infty }$ covers every $T_i$. This argument uses level stabilization, not compactness of an infinitely branching tree.

Now induct on the countable Borel hierarchy rank, with the strengthened assertion: for every game tree on any set alphabet and every $k$, a payoff of that rank has a $k$-covering unravelling it. The base case of open or closed sets was proved above. Complements preserve the assertion using the same game covering. For the union step, write $B={\bigcup }_{n<\omega }{B}_n$ with constituent sets of smaller rank. Starting at $T_0=T$, successively choose a $(k+n)$-covering $T_{n+1}\to T_n$ that unravels the inverse image of $B_n$ under the composite map to $T$. This is legitimate because continuous inverse images preserve Borel hierarchy rank, and the induction assertion ranges over all trees and alphabets, including the enlarged ones produced by earlier game coverings.

In the stabilized inverse limit, each pulled-back $B_n$ is clopen, because the later projection to the stage where it was unravelled is continuous. Their union is therefore open. Apply the already proved open-set unravelling construction once more, with preservation depth $k$, and compose with the limit game covering. The result unravels $B$ itself. This proves the strengthened assertion at every successor or limit countable Borel hierarchy rank. Every Borel set arises at some such rank: countable unions take the supremum of countably many countable ranks and then one further stage, and complements do not leave the generated hierarchy.

Apply the assertion to $T=A^{<\omega }$ and $k=0$. The covered payoff is clopen and hence determined by Question 4, including its assigned finite terminal outcomes. Transfer its winning strategy through the game covering. We obtainEvery auxiliary alphabet and strategy collection used above is a set. The argument uses power sets and replacement to build those collections and their iterated game coverings, and the axiom of choice for strategy selections; it does not require $A$ to be countable.