Past exam of the mathematics course of the University of Cambridge / 2004 / iii / Paper 24 (Set Theory)

Independence here is a relative consistency assertion: from a ground first-order model satisfying ZFC, construct a first-order model of each remaining theory in which the omitted axiom fails. The ground axiom of choice is a tool for constructing these countermodels, not an extra axiom imposed on the theories being tested. The constructible universe supplies the usual relative-consistency implication from ZF to ZFC, so this ground choice assumption requires no additional consistency strength. These constructions can be formalized inside an arbitrary ground model; they do not require the stronger assumption that a transitive model exists.

Union. Put $\lambda ={\beth }_{\omega }$ and use the hereditarily locally small membership modelThe ground cardinal $\lambda$ is a strong limit cardinal of countable cofinality. This transitive class contains the empty set and $\omega$. Pairing preserves the bound, as does taking a subset, so separation holds for every formula relativized to this class. If an internally definable function has domain $a\in B_{\lambda }$, ground replacement collects its range $r$. Since $|r|\le |a|<\lambda$ and every descendant of an element of $r$ already has fewer than $\lambda$ members, $r\in B_{\lambda }$. Thus the full functional Axiom schema of replacement holds. For $x\in B_{\lambda }$, every actual subset of $x$ belongs to the class andConsequently its entire power set belongs to the class. Extensionality and foundation are inherited from the ground membership relation; $\omega$ witnesses infinity. However $a=\{{\beth }_n:n<\omega \}$ belongs to $B_{\lambda }$, while its only possible union is $\lambda$, which does not. All the other ZF axioms hold, and union fails. Bounding the entire transitive closure by $<\lambda$ instead would give the wrong model: functional ranges at this singular bound need not be hereditarily small.

Power set. Use the transitive class $H_{{\omega }_1}$ of hereditarily countable sets. Pairing, union and separation preserve hereditary countability. A functional image of a countable domain is countable, and its members have countable transitive closures; their countable union is countable in the ground ZFC model. This proves replacement. The remaining structural axioms and infinity are inherited. Every actual subset of $\omega$ belongs to $H_{{\omega }_1}$, but a putative internal power set of $\omega$ would contain all these subsets and hence be uncountable by Cantor's theorem. Power set fails in $H_{{\omega }_1}$, with every other ZF axiom intact.

Replacement. Use $V_{\omega +\omega }$ in the cumulative hierarchy. At a limit ordinal cutoff, pairing, union, power set and every instance of separation remain below the cutoff; foundation, extensionality and infinity hold as well. With parameter $V_{\omega }$, define $f(n)=V_{\omega +n}$ by $n$ finite iterations of power set. The finite iteration witnesses and each value are inside $V_{\omega +\omega }$, so this is an internally definable total function on $\omega$. Its range has rank of a set $\omega +\omega$ and is absent from the model. This instance of replacement fails.

Extensionality. Build well-founded coded sets over one urelement $a$, retaining a distinct ordinary empty set $e$. Membership of an atom is always false, and membership of a set code is its coded extension. Thus $a\ne e$ but they have identical empty extensions. Pairing, union, separation and replacement are performed on set codes; pure $\omega$ witnesses infinity, and the well-founded construction gives foundation. There is a small point concerning the unmodified, untyped Axiom of power set: the atom is vacuously a subset of every object. Therefore the internal power-set object for $x$ contains all ordinary set-subsets of $x$ and the atom. It has exactly the required extension. All remaining ZF axioms hold, but extensionality fails. In the usual typed atom theory, the power-set axiom instead quantifies only over set-subsets.

Foundation. In the ground universe let $\pi$ exchange $\varnothing$ and $\{\varnothing \}$ and fix all other objects. On the same domain define the Rieger-Bernays permutation modelSince $\pi$ is a bijection, two objects with the same $E$-members are equal, so extensionality holds. Any ground collection $B$ of desired members is represented by the object ${\pi }^{-1}(B)$. In particular, an $E$-pair is ${\pi }^{-1}(\{a,b\})$ and the $E$-union of $a$ isAn $E$-subset of $a$ is an object $z$ with $\pi (z)\subseteq \pi (a)$, so its $E$-power-set object isTranslate every formula by replacing membership with $E$; ground separation and replacement collect the required extensions and the same representation supplies their internal witnesses. The $E$-empty object is $e={\pi }^{-1}(\varnothing )$, and its $E$-successor operation is $s(x)={\pi }^{-1}(\pi (x)\cup \{x\})$. Ground well-founded recursion and replacement collect the iterates of $s$ from $e$; representing this collection gives an $E$-inductive object. Thus infinity holds. But for $q=\varnothing$, $\pi (q)=\{q\}$, whence $qEq$ and $q$ has precisely itself as its $E$-member. Foundation fails.

Infinity. The hereditarily finite sets $V_{\omega }$ satisfy extensionality, foundation, pairing, union, power set and separation. Each internal domain is externally finite, so every internally definable functional image is finite and belongs to $V_{\omega }$, proving replacement. No finite object can contain the empty set and all its successive Finite von Neumann ordinals. Infinity fails, and all other ZF axioms hold.

Choice with atoms. For the negative model use the Basic Fraenkel permutation model. Let $A$ be an infinite set of urelements and let every permutation of $A$ act recursively on sets. Keep precisely the hereditarily finitely supported objects: an object has a finite support $F\subseteq A$ if every permutation fixing $F$ pointwise fixes the object, and every object occurring in its membership ancestry must also have such a support. The class of these objects contains the pure universe and $A$ itself.

Supports for a pair are united; union preserves a support; a formula defining a subset uses the finite union of the supports of its domain and parameters. An internally definable functional range has the same support, since its values are uniquely specified, and its elements are already hereditarily supported. This proves the full separation and replacement schemas. All hereditarily supported set-subsets of a fixed set form its symmetric internal power set; this collection is invariant under the pointwise stabilizer of a support of the original set. For the untyped version add all the atoms, as above. Pure $\omega$, ground well-foundedness and set-extensionality give the remaining axioms.

The family $[A{]}^2$ of unordered pairs of atoms is hereditarily supported. If it had a choice function $f$, let $F$ be a finite support of $f$. Choose distinct $a,b\in A\setminus F$. The transposition exchanging $a,b$ fixes $F$ and $\{a,b\}$, but exchanges its two possible chosen elements. Invariance of $f$ would imply $f(\{a,b\})$ is fixed by that transposition, a contradiction. Conversely, the full well-founded universe over the atoms, before restricting to finite supports, satisfies choice when the ground universe does. Both choice and its negation are relatively consistent with the stated weakening of extensionality.

The partition relation $\lambda \to (\mu {)}_{\nu }^r$ says that every colouring of the $r$-element subsets of a set of cardinality $\lambda$ into $\nu$ colours has a homogeneous set of cardinality $\mu$. Define the beth numbers over an infinite cardinal $\kappa$ by ${\beth }_0(\kappa )=\kappa$ and ${\beth }_{n+1}(\kappa )=2^{{\beth }_n(\kappa )}$. The Erdős-Rado theorem for finite arities gives the precise boundThus any fixed finite arity and any fixed infinite number of colours admit arbitrarily large infinite monochromatic sets once the starting cardinal is sufficiently large. For pairs, the especially useful case is $(2^{\kappa }{)}^{+}\to ({\kappa }^{+}{)}_{\kappa }^2$. The successor in this bound matters: a binary first-difference colouring on a suitably ordered set of binary sequences supplies the familiar obstruction at $2^{\kappa }$. Also, a theorem for every fixed finite arity is not a theorem homogenizing all arities simultaneously.

The mechanism is to build an end-homogeneous routing tree: each new vertex is routed according to its colours to earlier vertices on its branch. A long branch is end-homogeneous, meaning the colour from a fixed earlier vertex is independent of the later vertex. There are at most ${\kappa }^{\alpha }\le 2^{\kappa }$ routes of length $\alpha <{\kappa }^{+}$, and the whole collection of short routes has size at most $2^{\kappa }$. Inserting $(2^{\kappa }{)}^{+}$ vertices therefore forces a branch of length ${\kappa }^{+}$. One colour occurs at ${\kappa }^{+}$ earlier vertices on that branch, giving the pair theorem. Iterating the higher-arity version of this routing construction explains the successive powers in the Erdős-Rado theorem for finite arities.

A weakly compact cardinal is an uncountable strongly inaccessible cardinal $\kappa$ withEquivalent formulations include the tree property at the inaccessible cardinal and compactness for theories of size at most $\kappa$ in the infinitary language $L_{\kappa ,\kappa }$: if every subtheory of size $<\kappa$ has a first-order model, so does the theory.

A measurable cardinal is an uncountable $\kappa$ carrying a nonprincipal ultrafilter closed under intersections of fewer than $\kappa$ members. Such an ultrafilter contains no set of size $<\kappa$, since all singletons have complements in it and it is kappa-complete. Consequently a cofinal sequence of length $<\kappa$ would partition $\kappa$ into too few small pieces, so $\kappa$ is regular cardinal. If $\lambda <\kappa$ and $\kappa$ distinct subsets of $\lambda$ existed, choose, for each coordinate of $\lambda$, the bit selected by the ultrafilter. Kappa-completeness would make all those bits simultaneously constant on a large set of indices; only one distinct subset could have that bit pattern, a contradiction. Hence $2^{\lambda }<\kappa$: $\kappa$ is also a strong limit cardinal.

A supercompact cardinal $\kappa$ has, for every $\lambda \ge \kappa$, a fine ultrafilter that is a normal ultrafilter on small subsets and is kappa-complete onFine means $\{x:\alpha \in x\}$ is large for every $\alpha <\lambda$. Normal means that a function $f$ with $f(x)\in x$ on a large set is constant on some large set. Equivalently, for every such $\lambda$ there is an elementary embedding $j:V\to M$ with critical point $\kappa$, $j(\kappa )>\lambda$, and $M$ closed under $\lambda$-sequences from the universe.

These notions form the implication chain supercompact $\Rightarrow$ measurable $\Rightarrow$ weakly compact. For the first implication, an embedding as above gives the measure $U=\{X\subseteq \kappa :\kappa \in j(X)\}$. For the second, use a normal ultrafilter on a cardinal obtained by normalizing its measure. Indeed the ultrapower embedding gives the measure $U=\{X\subseteq \kappa :\kappa \in j(X)\}$; for a regressive $f$, $j(f)(\kappa )<\kappa$ is a fixed ordinal, yielding the required constant large fibre. Given a pair-colouring, select for each $\alpha$ the measure-one colour on the tail above $\alpha$. One selected colour occurs on a measure-one set of $\alpha$'s. Normality makes the diagonal intersection of their selected tails measure one; any two members of that intersection have the selected colour. This gives the required partition relation, and the preceding regularity and strong-limit argument gives inaccessibility.

Forcing constructs new first-order models while controlling which ground-model properties survive. Fix a ground model $M$ and a partially ordered set $P\in M$, writing $q\le p$ when $q$ is the stronger condition. A generic filter is upward closed, directed towards stronger conditions, and meets every ground-model dense subset of a forcing order. If $M$ is externally a countable transitive model, enumerate its dense subsets and successively choose stronger conditions in them. The resulting filter is $M$-generic. External countability is crucial: this is not a claim that the ground model regards its own universe as countable.

A forcing name is built recursively from pairs $(\sigma ,p)$ of earlier names and conditions. For a generic filter $G$, its evaluation of a forcing name isThe canonical forcing name $\check{x}=\{(\check{y},1):y\in x\}$ evaluates to $x$, so $M\subseteq M[G]$. Recursive evaluation also proves transitivity. Name ranks bound the ranks of their evaluations, so an ordinal in the extension is below some ground ordinal and is already a ground ordinal. Thus forcing preserves ordinals.

The central link between syntax and generic interpretation is the forcing theorem. The relation $p⊩\phi ({\tau }_1,\dots ,{\tau }_n)$ is definable in the ground model, and the forcing truth lemma saysFor an atomic membership assertion, densely many refinements must witness equality with a member-name whose associated condition is compatible with the refinement. Equality is obtained by recursive mutual inclusion of names. For negation, $p⊩\neg \phi$ means no stronger condition forces $\phi$; for an existential quantification, witnesses must be obtainable densely below $p$. Induction on name rank establishes the atomic clauses, and induction on formulas establishes definability and the truth lemma. The generic filter meets the relevant dense sets at the existential step. An arbitrary semantic assertion about one chosen generic filter is insufficient: the definable relation must work uniformly for all generic interpretations.

This explains preservation of ZFC. Extensionality and foundation follow from transitivity; canonical names supply infinity. Pair and union names give pairing and union. For separation, restrict a name's members to conditions forcing the defining formula. For replacement, the definable forcing relation lets ground axiom schema of collection bound a set of names for all possible witnesses to the unique outputs; evaluating their collected name gives the range. For power set, let $\tau$ name the given set and let $D$ be the set of its member-names. Every subset of ${\tau }_G$ has an equivalent name drawn from $\mathcal{P}(D\times P)$, by the truth lemma, so a ground set of candidate names collects all its subsets. Finally choose a ground well-order of the relevant names; its evaluated image surjects onto the desired set, and choosing the first name for each value well-orders that set. This is why ordinary forcing over a choice model preserves choice.

For a concrete example, Cohen forcing consists of finite partial functions $\omega \to 2$, ordered by extension. The generic union $c=\bigcup G$ is total because deciding each coordinate is dense. For every ground real $x$, the set of conditions disagreeing with $x$ somewhere is dense, so $c\ne x$. This construction changes the universe by adding a genuinely new real without changing its ordinals.

The size and compatibility of conditions determine what else changes. With the countable chain condition for forcing, an ordinal-valued name has only countably many possible values at each coordinate: take a maximal antichain deciding that value. Therefore the possible range of a name for a map with infinite ground domain of cardinality $\mu$ lies in a ground set of size at most $\mu \cdot {\aleph }_0=\mu$. This prevents cardinal collapse and changes of uncountable regular cofinalities. Forcing by finite partial functions $\lambda \times \omega \to 2$ is ccc: the delta-system lemma thins any uncountable family of finite domains to a delta-system, and a further thinning makes their values agree on its finite root. Two remaining conditions are compatible. Distinct coordinates add distinct reals.

For example, start with GCH and take $\lambda ={\aleph }_2$. This forcing has size $\lambda$ and adds $\lambda$ distinct reals. A nice name for a real uses countably many antichains, and each antichain is countable. The ground arithmetic ${\lambda }^{{\aleph }_0}=\lambda$ bounds the number of such names by $\lambda$. Hencegiving a relative-consistency example of the failure of CH. The ground choice of GCH is available through the constructible universe; no claim that every starting model has this arithmetic is needed.

By contrast, countably closed forcing adds no new countable sequences of ground ordinals. Given a name, recursively strengthen a condition to decide each coordinate, then take a lower bound of the descending sequence. That condition decides the entire sequence. Closure and chain conditions thus control different features; neither should be silently substituted for the other.

Further applications include changing cofinalities, adding branches through trees, and constructing prescribed continuum patterns. If the aim is to violate choice, an ordinary generic extension of a choice model will not do: one restricts to a suitable symmetric collection of names, checking the axioms again. These examples also mark a limitation: forcing proves relative consistency, not absolute consistency of the background theory. The countable-transitive-model picture gives a concrete semantic construction; the definable forcing relation and Boolean-valued formulation supply the corresponding formal consistency arguments without asserting that a transitive ground model can be proved to exist.

Use the rooted-tree homeomorphic embedding relation: an injective map of vertices preserves lowest common ancestors, so edges may become paths and the source root may map below the target root. We prove the stronger labelled statement for labels in any well-quasi-ordering $Q$, with labels increasing under the embedding. Forgetting labels gives Kruskal's tree theorem.

First every infinite sequence in a well-quasi-ordering has an infinite nondecreasing subsequence. Colour its index pairs according as the earlier term is or is not below the later term. Ramsey's theorem gives an infinite constant-colour subsequence; the bad colour would contradict well-quasi-ordering. Applying this successively in each coordinate proves finite product closure of well-quasi-orderings.

We need Higman lemma with its proof. Order finite words over $Q$ by subsequence embedding with increased letters. If there were a bad sequence, choose one $w_0,w_1,\dots$ minimally: at each position choose a shortest word admitting a bad continuation of the fixed prefix. No word is empty. Write $w_n=u_n{a}_n$, separating the last letter, and choose $n_0<n_1<\cdots$ with $a_{n_0}\le a_{n_1}\le \cdots$. ConsiderAn earlier prefix word cannot embed in a later $u_{n_j}$, since it would then embed in $w_{n_j}$. Nor can $u_{n_i}$ embed in $u_{n_j}$: adding the comparable last letters would embed $w_{n_i}$ in $w_{n_j}$. Thus the displayed sequence is bad, contradicting minimality at $n_0$, since $u_{n_0}$ is shorter. Finite words over a well-quasi-order are well-quasi-ordered.

Now suppose labelled rooted trees admit a bad sequence $T_0,T_1,\dots$, chosen minimally in vertex count at each position. Let $\mathcal{A}$ consist of all proper rooted subtrees of these trees, rooted at a descendant and containing all its descendants. We claim $\mathcal{A}$ is well-quasi-ordered. Otherwise take a bad sequence $S_0,S_1,\dots$ from $\mathcal{A}$. Only finitely many subtrees come from any fixed finite prefix of the $T_n$'s, and a bad sequence cannot repeat an object. Thin it so that $S_i$ comes from $T_{m_i}$ with $m_0<m_1<\cdots$. The sequenceis bad: $T_j⪯S_i$ would imply $T_j⪯T_{m_i}$, since a rooted subtree embeds in its host; comparisons within the $S_i$'s are excluded by their choice. But $S_0$ is strictly smaller than $T_{m_0}$, contradicting minimality. This proves the claim.

Choose an arbitrary ordering of the children of each $T_n$. Record its root label and the finite word of rooted child-subtrees:By Higman lemma and finite product closure, two records, with indices $i<j$, are comparable. Map the root of $T_i$ to the root of $T_j$, and map its selected child-subtrees into the distinct selected branches of $T_j$. Within a branch the embeddings preserve lowest common ancestors; between different branches both lowest common ancestors are the roots. Labels increase everywhere. This gives $T_i{⪯}_Q{T}_j$, contradicting badness. Finite labelled rooted trees are well-quasi-ordered by label-monotone homeomorphic embedding. In particular, this proves the unlabelled theorem. A root-preserving variant follows by giving the root a special incomparable label unavailable at nonroot vertices; the general labelled theorem then forces root to root. Adjacency-preserving embeddings are a different, more restrictive relation and do not satisfy the same assertion.

For Friedman's finite form of Kruskal's theorem, fix $k\in \mathbb{N}$ and consider finite bad sequences satisfying $|T_i|\le k+i$, with indices starting at $1$. Their prefixes form a finite bad-sequence tree. At each depth there are only finitely many possible unlabelled tree isomorphism types below the size bound, so this tree is finitely branching. If bad sequences existed at every finite length, König infinity lemma would yield an infinite branch, hence an infinite bad sequence of rooted trees, contrary to what was just proved. ThereforeThe same proof works with any fixed finite label set. The finite size bounds are what make the bad-prefix tree finitely branching; the proof does not claim a small effective numerical bound.

Work in ZFC. The move alphabet need not be countable; choice permits the selections of moves, strategies and witnesses used below. Assume $A\ne \varnothing$; with the usual convention that a player unable to move loses, the empty alphabet is a trivial terminal game. We prove Borel determinacy theorem by strengthening the assertion to the existence of game coverings that unravel payoffs. Simply asserting that determined payoffs are closed under countable unions would not be a proof.

It is useful to allow a tree of legal finite plays with terminal nodes explicitly labelled as losses for either player. For an infinite branch, I wins exactly when it belongs to the payoff $C$. Projection of a game tree is length-preserving and respects prefixes. At a projected original terminal node the outcome is inherited, but the new tree may also have artificial terminal losses.

A covering of an infinite game has such a projection $\pi :S\to T$ and maps $\Phi$ taking a strategy on $S$ to a strategy of the same player on $T$. Its crucial lifting condition is this: each maximal play $x$ on $T$ following $\Phi (\sigma )$ has a $\sigma$-compatible lift $y$ on $S$, either projecting exactly to $x$ with its inherited terminal outcome, or projecting to a prefix of $x$ and ending in a loss for the player using $\sigma$. Its strategy maps must be local in depth: choices up to a given depth use only the upstairs strategy up to that depth. A $k$-covering preserves the initial $k$ levels and choices. If ${\pi }^{-1}(C)$ is clopen, call it an unravelling of a game payoff. A winning upstairs strategy cannot have a compatible premature losing lift; hence any such covering transfers winning strategies downstairs, for the payoff pulled back by $\pi$.

First, clopen determinacy with terminal losses holds on any set-sized tree. At a node where all infinite extensions have one fixed winner, the other player can win only by forcing a terminal loss for that winner. Decide that reachability game by the winning-position attractor in an infinite game: begin with the desired losing terminals, add the attacking player's positions with a successor already in the attractor and the defending player's positions with every successor in it, and take unions at limit stages. Entry ranks give a strategy reaching the target; outside the attractor the defender avoids it. If there are no infinite extensions the same reachability analysis still applies. At every remaining position there are infinite extensions in both $C$ and its complement. This remaining tree is well-founded, since an infinite branch through it would contradict clopenness at that branch. Well-founded recursion now assigns a winner upwards from the already decided nodes, choosing a winning successor when the player to move has one. These choices give an actual winning strategy.

Next we construct an announcement-and-challenge covering of a closed payoff. Let $C\subseteq [T]$ be closed, and choose an even depth $l>k$. Play initially follows $T$ unchanged. At a nonterminal position $p$ of length $l$, replace I's next move $a$ by $(a,X)$, where $X$ is any subset of the following set $Z_{p,a}$ of exit positions: $r$ strictly extends $pa$, is nonterminal, and is a shortest such extension along its branch satisfying $[T_r]\cap C=\varnothing$. If $[T_{pa}]\cap C=\varnothing$ already, the first nonterminal extension beyond $pa$ counts as an exit. Distinct exits form a prefix antichain. An original terminal move always keeps its original outcome.

Player II now either accepts and makes an ordinary next move $b$, or challenges an $r\in X$ and makes the move $b$ prescribed by that $r$. On acceptance, continue the original play until the first exit $r$: it is an artificial win for I if $r\in X$, and an artificial loss for I otherwise. On a challenge, both players are forced to follow $r$ until it is reached, after which the original game resumes without the acceptance stopping rule. The projection forgets the announcements and challenge flags.

An infinite accepted play avoids all exits. Every sufficiently long prefix of its projection therefore has a continuation in $C$, so closedness implies that the projection is in $C$. Every infinite challenged play passes through an exit cylinder disjoint from $C$. Thus among infinite plays the pulled-back payoff is decided by II's acceptance or challenge: it is clopen. This remains true when a particular branch reaches an inherited terminal position before either case produces an infinite play.

Here is the strategy-transfer proof, which also fixes the artificial terminal labels. Given an I-strategy $\sigma$ upstairs, use its announced ordinary move $a$ downstairs and initially simulate an accepting response. If the projected play never exits, this is an exact lift. If its first exit $r$ is not in the announced $X$, the accepting lift ends in a loss for I, as allowed. If $r\in X$, switch to the simulation in which II challenged this particular $r$. The earlier ordinary prefix is unchanged: all moves through $r$ in the challenged simulation are forced and agree with the observed prefix. Beyond $r$ follow $\sigma$ in that simulation. This gives an exact compatible lift. Original terminal outcomes are inherited throughout.

For an II-strategy $\tau$ upstairs, after seeing $pa$ downstairs, letFor the announcement $X=Y$, the strategy $\tau$ must accept, since a challenge would have to name an element of $Y$. Use its accepting ordinary response downstairs and simulate that acceptance until an exit. If the exit $r$ belongs to $Y$, the accepting lift is an artificial loss for II, as required. If $r\notin Y$, choose an announcement $X_r$ for which $\tau$ challenges $r$, and switch to that simulation. Its first ordinary response and all the intervening forced moves agree with the actual prefix $r$; after $r$ use $\tau$ there. This gives an exact lift. Choices of $X_r$ use choice. No switch uses unseen future moves, and the definition of $Y$ uses only the strategy's responses at the fixed announcement level. Thus the maps are local in depth. The unchanged initial segment makes this a $k$-covering.

We now establish the stronger assertion: every Borel payoff on every such game tree admits a $k$-unravelling for every finite $k$. Closed payoffs were just handled. Complements need no new construction, since the complement of a clopen pulled-back payoff is clopen.

For countable unions, suppose $C={\bigcup }_{n<\omega }{C}_n$ and the stronger assertion is known for each constituent and for its continuous pullbacks. Starting with $T_0=T$, choose a covering $T_{n+1}\to T_n$ that unravels the current pullback of $C_n$ and preserves at least the first $k+n$ levels and choices. Previously unravelled payoffs remain clopen under further continuous projections. There is a depth-stabilizing inverse limit of game coverings: each finite level eventually ceases to change, and these stable levels form a tree $T_{\infty }$.

For completeness, the limit retains the covering property, not just the topology. Compose the projections and the depth-local strategy maps; their finite restrictions stabilize. To lift a play following the limit-projected strategy, lift it successively, coherently, from $T_n$ to $T_{n+1}$. If all lifts are exact, the stabilized finite prefixes give a compatible play on $T_{\infty }$. If a premature losing terminal lift occurs, every further lift is either exact or another losing terminal prefix, so its length cannot increase; lengths and then its finite position stabilize. This produces the permitted losing terminal lift in the limit. The choices needed to select successive lifts are available in ZFC. Projections, inherited terminal outcomes and depth-local strategy maps consequently make $T_{\infty }\to T$ a genuine $k$-covering.

On $T_{\infty }$, the pullbacks of all the $C_n$ are clopen, so their union is open. Its complement is closed. Apply the closed-payoff construction once more to unravel this complement; it unravels the union too. Composition gives the desired covering of $T$. This proves the induction step. Induction on a well-founded construction of a Borel set, whose operations are complementation and countable union starting from open sets, proves the assertion for every Borel payoff. Continuous preimages of a constituent have the same type of construction, so the induction hypothesis used at successive covers is justified. No countability of the move alphabet was used; all enlarged alphabets and trees remain sets.

Finally apply this result to $T=A^{<\omega }$. The unravelled clopen game has a winning strategy by the first argument. The covering lifting condition transfers it to the original game. ThereforeThis is a theorem in the usual background set theory with choice; it does not assert unrestricted determinacy for arbitrary, non-Borel payoffs.

Identify the space of infinite subsets of the natural numbers with their increasing enumerations, with the ordinary topology on infinite subsets inherited from the discrete product ${\omega }^{\omega }$. This is the sequence convention in the Open Ramsey theorem. For a general infinite ground set, first choose a countably infinite subset and use its enumeration. The theorem cannot mean unrestricted sequences with repetitions: the clopen partition according as the first two entries agree or differ has both colours over every infinite ground set.

For a finite finite stem $s$ and an infinite tail $B$ above $\max s$, writewhere the enumeration of $s$ precedes the tail. Let $O$ be open. The tail $B$ accepts $s$ if $[s,B]\subseteq O$; it rejects $s$ if no infinite subtail accepts it. Both properties persist on infinite subtails, and any stem can be decided by thinning: choose an accepting subtail if one exists; otherwise the current tail already rejects it.

Use deciding all finite stems by fusion. At stage $n$, choose a new element $b_n$ from the current tail, then thin the remaining tail to decide each of the finitely many subsets of $\{b_0,\dots ,b_n\}$. First decide the empty stem as well. The final selected set $B$ decides every finite stem from $B$, because all subsequent selections lie in the tail that decided that stem. If $B$ accepts the empty stem, $[B{]}^{\omega }\subseteq O$ and we are done.

Otherwise the empty stem is rejected. If a stem $s\subset B$ is rejected, only finitely many $a\in B$ above $\max s$ can have the tail $B/a$ accepting $s\cup \{a\}$. Indeed, if infinitely many such $a$ formed $D$, then every $X\in [D{]}^{\omega }$ starts with one of them and has its remaining tail in $B/a$. It follows that $[s,D]\subseteq O$, contradicting rejection of $s$. All other one-point extensions are rejected, since the first fusion has already decided them.

Build an infinite $C\subseteq B$ recursively. Maintain that every subset of the finite selected prefix is rejected. To select its next element, avoid the finite union of the finitely many accepting-extension obstructions for these rejected stems. Such an element exists, and all the new stems remain rejected. Hence every finite stem from $C$ is rejected. If some $X\in [C{]}^{\omega }$ were in $O$, openness would supply a finite initial segment $s$ of $X$ whose entire ordinary cylinder is contained in $O$. The tail $C/\max s$ would accept $s$, a contradiction. ThusIn particular every open payoff has an infinite homogeneous set. A finite partition into open colour classes can be handled by successive application of this two-colour assertion.

For an arbitrary partition use finite-symmetric-difference parity colouring. On the infinite subsets of the ground set, declare $X\sim Y$ when $X△Y$ is finite, and choose a representative $R$ from each equivalence class. Colour $X$ byFor any infinite $H$, removing one member gives an infinite $H^{\prime }$ in the same class and reverses the parity. Thus $H$ and $H^{\prime }$ have opposite colours, so neither colour contains all infinite subsets of any infinite ground set. This two-colouring has no infinite homogeneous set. Representative selection uses choice; the construction is deliberately unrestricted by topological regularity.

An ultraproduct converts coordinatewise finite information into a single first-order structure. Let $(M_i{)}_{i\in I}$ be nonempty structures in a common first-order language, and let $U$ be an ultrafilter on $I$. In ${\prod }_i{M}_i$, setThe ultraproduct ${\prod }_i{M}_i/U$ has these equivalence classes as its elements. Functions are interpreted coordinatewise; a relation holds of classes exactly when it holds on a $U$-large set of indices. Intersecting finitely many large agreement sets shows that these interpretations are independent of representatives.

The Łoś theorem, which explains the construction's usefulness, saysHere is the proof. Induction on terms establishes the coordinatewise interpretation of atomic formulas. Finite intersections handle conjunction, and the ultrafilter property handles negation, since precisely one of a set and its complement is large. For an existential quantification, a witness class gives coordinate witnesses on a large set. Conversely, when the coordinate existential truth set is large, select a witness in each of those structures and a default element elsewhere. Its class is a witness in the ultraproduct. This uses choice. Structural induction on formulas now proves the theorem, with universal quantification obtained by negation.

Compactness. If every finite subset of a first-order theory $T$ has a model, take $I$ to be the finite subsets $\Gamma \subseteq T$ and choose $M_{\Gamma }\models \Gamma$. The cones $\{\Gamma :\Delta \subseteq \Gamma \}$ for finite $\Delta$ have the finite intersection property. Extend their filter to an ultrafilter by the ultrafilter lemma. For each $\phi \in T$, its cone is large, so the Łoś theorem makes the ultraproduct satisfy $\phi$. This proves the compactness theorem, including theories of arbitrary set size.

Elementary extensions and nonstandard elements. An ultrapower uses a fixed structure at every coordinate. The diagonal map sending $a$ to the class of the constant function $a$ is an elementary embedding by the Łoś theorem. For a nonprincipal ultrafilter on $\omega$, the class of $i\mapsto i$ in an ultrapower of the natural numbers exceeds every standard integer, because each corresponding tail is large. In an ultrapower of the real ordered field, the reciprocal of this element is positive and smaller than every positive standard reciprocal integer: an infinitesimal. These examples implement ordinary finite statements in a larger structure without claiming that every external subset or second-order assertion transfers.

Saturation. Such an ultraproduct over $\omega$ is countably saturated. To see the actual diagonal argument, list a finitely satisfiable type ${\phi }_0(x),{\phi }_1(x),\dots$ with parameters in the ultraproduct and fix representatives for those parameters. For each $n$, the set $E_n$ of coordinates admitting a simultaneous witness to its first $n$ formulas belongs to $U$ by the Łoś theorem. Arrange that the $E_n$ decrease and put $D_n=E_n\cap \{i:i\ge n\}$. The $D_n$ decrease, belong to $U$, and have empty intersection. At coordinate $i$, choose a witness to the first $m(i)$ formulas, where $m(i)$ is the largest $n$ with $i\in D_n$, or choose a default element if there is no such $n$. For each fixed $n$, $m(i)\ge n$ on the large set $D_n$. Therefore the resulting class realizes every formula. This proves countable saturation of an ultraproduct over omega; it does not assert saturation at all larger cardinalities.

Algebraic limits. Take finite fields ${\mathbb{F}}_p$ indexed by the primes and a nonprincipal ultrafilter. Their ultraproduct is a field of characteristic zero: for every fixed positive integer $n$, only finitely many primes divide $n$, so $n\cdot 1\ne 0$ on a large set. Every first-order sentence true in all finite fields holds in this infinite field, and more generally so does any sentence true for all but finitely many of the factors. This is a way to create an infinite field retaining uniform first-order information from finite fields. It does not make the field algebraically closed: the first-order sentence that every element is a square already fails in infinitely many of the factors.

Large cardinals. A countably complete ultrafilter gives a well-founded membership ultrapower of the universe. If it had an infinite descending chain represented by $f_n$, each setwould be large. Countable completeness makes ${\bigcap }_n{A}_n$ nonempty, giving an actual infinite membership descent at any index in the intersection, contrary to foundation. The Mostowski collapse therefore gives a transitive target and an ultrapower embedding $j:V\to M$.

For a measure on a measurable cardinal $\kappa$, every function $\kappa \to \alpha$ with $\alpha <\kappa$ is constant on a large set: otherwise intersect the fewer than $\kappa$ complements of all its fibres. Consequently $j$ fixes the ordinals below $\kappa$. The class of the identity function is below $j(\kappa )$ and above every constant class below $\kappa$, since all tails are large. Thus $j(\kappa )>\kappa$ and its critical point is $\kappa$. Fine ultrafilters on $P_{\kappa }(\lambda )$ that are normal ultrafilters on small subsets and kappa-complete yield the stronger embeddings witnessing supercompact cardinals.

These applications share a single principle: an ultraproduct preserves precisely the first-order information seen by its ultrafilter. Principal ultrafilters merely select a factor; nonprincipal ones can produce new sizes, elements and saturation. Existence of the needed ultrafilters and selection of coordinate witnesses are set-theoretic assumptions, and changing the ultrafilter may change the resulting model.

A BQO, or better-quasi-ordering, strengthens a well-quasi-ordering by testing arrays indexed by arbitrary barriers, rather than just sequences. Let $Q$ be a preorder. A barrier in better-quasi-order theory on an infinite $A\subseteq \omega$ is a family $B$ of nonempty finite increasing sequences such that no member is properly contained in another and every infinite subset of $A$ has a member of $B$ as its initial segment.

For barrier members write $s◃t$ if a finite increasing sequence $u$ has $s$ as an initial segment and has $t$ as an initial segment after deleting the first entry of $u$. A map $f:B\to Q$ is good when some $s◃t$ satisfy $f(s)\le f(t)$. The definition isBoth quantifiers matter: testing only barriers of one fixed finite length is insufficient.

For the singleton barrier $B=[A{]}^1$, shifted pairs are just $\{a\}◃\{b\}$ with $a<b$. Thus the BQO condition implies the ordinary well-quasi-ordering condition. Barrier arrays can also be viewed through continuous arrays in better-quasi-order theory $F:[A{]}^{\omega }\to Q$, with $Q$ discrete: set $F(X)=f(s)$ for the unique barrier initial segment $s$ of $X$. This is continuous because that value is fixed by a finite prefix, and comparing $X$ with $X\setminus \{\min X\}$ is exactly the shift comparison. The general continuous-array formulation is equivalent to the barrier definition; its converse uses refinement of fronts to barriers, rather than the incorrect assertion that every prefix-decision family is already a barrier.

For an illustrative positive example, every well-order is a BQO. If a barrier array into a well-order were bad, its induced $F$ would satisfyfor every infinite $X$. This is an infinite strict descent in a well-order, a contradiction. A finite antichain with equality is also a BQO: the finitely many fibres of the induced continuous array are open, so repeated use of the Open Ramsey theorem gives an infinite $A^{\prime }$ on which the array is constant. The comparison of an infinite subset of $A^{\prime }$ with its shift is then good.

The implication to a well-quasi-order is strict. The Rado order isIt is well-quasi-ordered: if one first coordinate occurs infinitely often, its second coordinates have an increasing pair; otherwise the first coordinates are unbounded, and a later one exceeds the second coordinate of a chosen earlier pair. But take the barrier $[\omega {]}^2$ and $f(\{m,n\})=(m,n)$. For $m<n<l$, the shift compares $(m,n)$ with $(n,l)$; their first coordinates differ and $n<n$ is false. Every shifted comparison therefore fails. This bad barrier array for the Rado order proves well-quasi-ordering does not imply better-quasi-ordering.

The stronger notion is designed for infinitary closure operations, such as powerset and infinite-sequence constructions, where a mere well-quasi-order can develop new bad arrays. The barrier definition records variable finite amounts of information from an infinite object and is consequently more robust than checking sequences alone.