Past exam of the mathematics course of the University of Cambridge / 2002 / iii / Paper 21 (Set Theory)

We use rooted-tree homeomorphic embedding: an injective vertex map preserves ancestors and lowest common ancestors, while an edge may map to a longer path. The root may map below the host root. Write $T⪯U$ for this relation. The assertion of Kruskal's tree theorem is that finite rooted trees form a well-quasi-ordering: every infinite sequence has $i<j$ with $T_i⪯T_j$.

We first supply the word lemma needed in the proof. In a well-quasi-order $Q$, every sequence has an infinite nondecreasing subsequence. Indeed, if no term had infinitely many later terms above it, successive choices beyond the finite sets of later dominators would give a bad sequence. Some term therefore has infinitely many later dominators; repeat the argument inside that infinite subsequence, which is still well-quasi-ordered, to build a chain.

Now order finite words over $Q$ by subsequence embedding with coordinatewise increase. Suppose a bad word sequence exists and choose one $w_0,w_1,\dots$ minimally: at each position use a word of least length allowing a bad continuation of the fixed prefix. No word is empty. Write $w_i=v_i{a}_i$, removing its last letter. Choose indices $i_0<i_1<\cdots$ with $a_{i_0}\le a_{i_1}\le \cdots$. The sequencewould also be bad. An old word embedding into $v_{i_j}$ embeds into $w_{i_j}$, contrary to the original badness; and $v_{i_j}⪯v_{i_l}$ would extend, using the last-letter comparison, to $w_{i_j}⪯w_{i_l}$. But $v_{i_0}$ is shorter than $w_{i_0}$, contradicting minimality. This proves Higman lemma, including its empty-word case.

Suppose next that there is a bad sequence of finite rooted trees, and choose a minimal bad sequence $T_0,T_1,\dots$ by vertex count. Let $\mathcal{S}$ consist of all proper rooted subtrees hanging below vertices of the $T_i$. This collection is well-quasi-ordered. Otherwise choose a bad sequence $S_0,S_1,\dots$ in $\mathcal{S}$. Its containing-tree indices can be selected strictly increasing, say $S_j$ is a proper subtree of $T_{i_j}$: a finite initial collection of containing trees has only finitely many proper subtrees, and a bad sequence cannot repeat an isomorphism class. Thenis bad. No earlier $T_l$ can embed into $S_j$, because $S_j⪯T_{i_j}$ and this would contradict the original sequence. The new tail is bad by construction. Since $|S_0|<|T_{i_0}|$, this contradicts minimality.

List each tree's immediate root subtrees in any chosen order. These are finite words in the well-quasi-order $\mathcal{S}$, so the word lemma gives $i<j$ for which the child word of $T_i$ embeds into that of $T_j$. Send the root of $T_i$ to the root of $T_j$, and use the chosen embeddings inside the selected, distinct target branches. The connecting paths from the target root to the images of the source children have disjoint interiors; lowest common ancestors in different branches are preserved. This constructs $T_i⪯T_j$, the final contradiction. Thus finite rooted trees are well-quasi-ordered by homeomorphic embedding. If labels lie in an arbitrary well-quasi-order, the same proof uses label-monotone embeddings; compare root labels and child words in their product well-quasi-order. The product property follows by taking a nondecreasing subsequence in the first coordinate and a good pair in the second.

For Friedman's finite form of Kruskal's theorem, fix $k$. Consider all finite bad prefixes $(T_1,\dots ,T_l)$ satisfying $|T_i|\le k+i$, up to rooted-tree isomorphism. They form a prefix tree. At each node there are finitely many possible next trees, because there are only finitely many rooted-tree isomorphism types on at most $k+l+1$ vertices. If prefixes of arbitrary length existed, the König infinity lemma would give an infinite branch, hence an infinite bad sequence, contrary to what we proved. Its height is therefore bounded. ConsequentlyThe same finite-prefix argument works with a fixed finite label alphabet, and more generally with any prescribed size bound $b(i)$ having only finitely many possibilities at each position. These are finite existence statements; no numerical estimate on $N$ is needed for the conclusion.

The independence statements are relative consistency statements. We construct models from an ambient model of ZFC; the construction is an interpretation and does not assume that the ambient model is transitive. Foundation is already true in the ordinary ambient membership structure, so its positive consistency direction is immediate.

For the negative direction, construct an extensional cumulative universe over Quine atoms. Let $A$ be a countably infinite set of formal symbols $q_a$. Give each $q_a$ the extension $\{q_a\}$. For a set $X$ of already constructed objects, let $S(X)$ be its unique representative: set $S(\{q_a\})=q_a$, and otherwise use a fresh tagged code $(1,X)$. Atom codes have a different tag. Begin with $U_0=A$ and putSet $W={\bigcup }_{\alpha }{U}_{\alpha }$. The interpreted membership relation $E$ gives $S(X)$ exactly the members $X$, and gives $q_a$ exactly the member $q_a$. This convention matters: creating a second representative for $\{q_a\}$ would violate extensionality. Every object is uniquely determined by its extension, so $E$ satisfies full extensionality. Every set-sized collection $X$ of objects has bounded construction rank, by ambient replacement, and hence has its representative $S(X)$ in $W$.

Here are the remaining axiom verifications. Empty set and pairing use $S(\varnothing )$ and $S(\{x,y\})$. If $E(y)=X$, its interpreted union is $S({\bigcup }_{x\in X}E(x))$. Its interpreted power set issince every subset extension has a unique representative. The pure, atom-free finite hierarchy supplies a copy of $\omega$ and an inductive set. For separation, translate an $E$-formula into the ambient language, with quantifiers restricted to the definable class $W$; ambient separation gives the appropriate subset of $X$, and $S$ represents it. For replacement, uniqueness in the interpreted functional relation gives an ambient definable functional image of the set $X$. Ambient replacement makes that image set-sized, and $S$ again represents it. These arguments also establish that all the operations used have bounded construction rank.

Ambient choice gives choice in $W$: choose a member from each nonempty extension in a set-sized family and represent the graph, using interpreted ordered pairs. But $q_{a}E{q}_a$, and the nonempty set with extension $\{q_a\}$ has no $E$-minimal member. ThusTogether with the ordinary model, this proves independence of foundation from the other ZF axioms, even when choice is retained.

To extend the construction to failure of choice, let the full permutation group of $A$ act on $W$ byThe singleton convention is equivariant, so this is an automorphism of $(W,E)$. An object has finite support if some finite $F\subseteq A$ has the property that every permutation fixing $F$ pointwise fixes the object. Retain objects all of whose membership descendants have finite support, stopping the hereditary recursion at the atomic self-loops. This gives the hereditarily finite-supported Quine-atom model $\mathcal{H}$; each $q_a$ belongs to it, with support $\{q_a\}$.

Extensionality persists because every retained object's members are retained. Empty set, pairing, infinity and union preserve hereditary finite support. For separation on a retained set $x$, the union of finite supports for $x$ and the formula's parameters supports the separated extension: permutations fixing those supports preserve satisfaction in $\mathcal{H}$. All its members are retained, so its representative is retained. For replacement, the same support fixes the functional range, because an automorphism must take the unique output at an input to the unique output at its transported input. Ambient replacement bounds that range; all its members are in $\mathcal{H}$, so its representative belongs to $\mathcal{H}$. Finally, the collection of all retained subset representatives of $x$ is an ambient set, contained in the full interpreted power set of $x$. A support of $x$ permutes this collection onto itself, and its members are retained. Its representative is therefore the internal power set in $\mathcal{H}$. This verifies every ZF axiom except foundation; foundation still fails at each $q_a$.

The atom set $A$ and the family $[A{]}^2$ of its two-element subsets have empty support and are retained. Suppose a choice function $f$ on $[A{]}^2$ were retained, with finite support $F$. Choose distinct $q_a,q_b$ outside $F$ and transpose them. The transposition fixes $f$ and fixes the unordered pair $\{q_a,q_b\}$, but moves whichever of its two members $f$ selects. Equivariance would require that selected member to be fixed, a contradiction. HenceThe full universe $W$ gives the corresponding positive-choice model. Choice is therefore independent of ZF without foundation. Unlike a permutation model with ordinary urelements, this model retains full pure-set extensionality: the atomic objects are self-membered sets, not empty objects exempted from extensionality.

The constructible-universe interpretation gives $\mathrm{Con}(\mathrm{ZF})\Rightarrow \mathrm{Con}(\mathrm{ZFC})$. Thus the consistency assumptions in both displayed conclusions can equivalently be taken to be $\mathrm{Con}(\mathrm{ZF})$; no additional consistency strength is being used.

An inner model of ZF is a transitive class $M$ containing every ordinal, with inherited membership, such that each ZF axiom holds with all quantifiers restricted to $M$. Here transitivity means $x\in y\in M\Rightarrow x\in M$. For a proper class this is an axiom-by-axiom assertion, not an internal truth predicate for the whole class. An inner model can have fewer subsets of a given set than the surrounding universe; it need not have the same cardinals or the same continuum function.

Inner models prove relative consistency. If a theory $T$ proves that a definable class $M$ satisfies every axiom of $S$, an inconsistency proof from $S$ could be relativized to $M$ and become an inconsistency proof from $T$. Thus $\mathrm{Con}(T)\Rightarrow \mathrm{Con}(S)$. This reasoning concerns formal interpretations and needs no assumption that a given model of $T$ is externally well-founded.

The central example is the constructible universe. Definewhere $\mathrm{Def}(X)$ contains exactly the subsets definable over $(X,\in )$ using parameters from $X$. Satisfaction for a set structure is definable, so this recursion is available in ZF. Induction shows that the levels are transitive and increasing: if $a\in L_{\alpha }$, the subset $\{x\in L_{\alpha }:x\in a\}$ is $a$, so $a\in L_{\alpha +1}$. The ordinal part of $L_{\alpha }$ is $\alpha$, giving all ordinals in $L$.

For completeness, the main axiom mechanisms explain why this example works. Finite set operations on constructible parameters are definable at finitely many further stages. For a fixed finite family of formulas and parameters, close a sequence of levels under their least constructible witness stages and take its union; induction on formulas gives a reflecting level. Separation of a constructible set then occurs at the next definability stage. For replacement, ambient replacement bounds the construction stages of the unique constructible outputs; a reflecting level above that bound makes the range definable. For the internal power set of $a\in L$, use ambient separation to form $\mathcal{P}(a)\cap L$, bound the construction stages of its members, and at a sufficiently high level define the family of all subsets of $a$ in that level. Thus the internal power set is constructible even though some ambient subsets may not be. Foundation is inherited by transitivity, and infinity comes from $L_{\omega }$ and its successor stages.

There is a canonical well-order of $L$: order by first construction stage, then by the least definition code and finite parameter tuple, using the previously constructed well-orders for parameters. Each set in $L$ can be well-ordered by the restriction of this set-like class order; hence $L$ satisfies AC. Moreover the hierarchy computed inside $L$ is the same hierarchy, because definability over a fixed set structure and limit unions are absolute. Thus $L$ satisfies $V=L$. The further cardinal analysis of this hierarchy, encapsulated in the constructible universe theorem, gives GCH. ConsequentlyThis proves the relative consistency of choice, CH and GCH; in particular none can be refuted by ZF if ZF is consistent. The assertions here are internal to $L$: they do not assert CH in the ambient universe.

Inner models also isolate definable information. The relative constructible universe built with a set parameter retains that parameter and all ordinals while discarding unrelated sets. Such constructions help compare relative consistency strengths and identify which hypotheses survive passage to smaller universes; preservation of a large-cardinal property must be checked separately, not inferred merely from transitivity.

There is an important limitation, the constructible-universe obstruction to a uniform inner-model proof of failure of choice. Every inner model $M$ of ZF contains the ambient $L$. Indeed $L_{\alpha }^M=L_{\alpha }$ by induction: the same set structure has the same definable subsets at a successor stage, and both hierarchies take the same union at a limit. If the ambient universe satisfies $V=L$, this forces $M=V$. Thus inner models cannot uniformly produce a model of $\neg \mathrm{AC}$ or $V\ne L$ from every ZF universe. To prove the opposite independence directions one needs an outer-model or other interpretation technique, such as forcing or the non-well-founded symmetry construction in Question 2.

For the effective counterexample, let $K$ be the diagonal halting set and let $K_s$ be the finite approximation obtained by running the first $s$ programs for $s$ steps. For $x<y<z$, define the recursive triple colouring with no computable infinite homogeneous set byThis is a total recursive two-coloring: only bounded computations are involved. An infinite homogeneous set $H$ cannot have color one. Fix $x\in H$ and take $y,z\in H$ sufficiently large that every halting computation with index at most $x$ that ever halts has already halted by stage $y$; then the color is zero. If $H$ has color zero, it computes $K$: given $e$, find $x<y$ in $H$ with $x\ge e$ and inspect $K_y(e)$. Agreement with every later stage $z\in H$, and the unboundedness of $H$, give $K_y\cap \{0,\dots ,x\}=K\cap \{0,\dots ,x\}$. Hence this is the correct answer. The set $K$ is not recursive: a purported halting decider would produce a program that halts exactly when the decider says it does not halt on its own index. Thus there is no recursive infinite homogeneous set. Here infinite is essential: every finite subset is recursive, and sets with fewer than three elements are vacuously homogeneous.

A precise finite-arity Erdős-Rado theorem for finite arities iswhere ${\beth }_0(\lambda )=\lambda$ and ${\beth }_{r+1}(\lambda )=2^{{\beth }_r(\lambda )}$. We prove the closed elementary-submodel construction of an end-homogeneous sequence and then induct. We work with AC, as in the usual cardinal partition calculus.

Put $\theta =(2^{\mu }{)}^{+}$, where $\mu$ is infinite, and let $c:[\theta {]}^{m+1}\to \lambda$ with $\lambda \le \mu$ and $m\ge 1$. Choose a regular cardinal $\chi$ large enough that this coloring and its domain belong to $H_{\chi }$, the sets of hereditary size below $\chi$. There is $M\prec H_{\chi }$ of size $2^{\mu }$ containing $c,\theta ,\mu$, every ordinal below ${\mu }^{+}$, and closed under externally given sequences of length at most $\mu$. Here is the closure construction: start with a Skolem hull of the named parameters and the ordinals below ${\mu }^{+}$; iterate hulls after adjoining all at-most-$\mu$-sequences of the preceding hull for ${\mu }^{+}$ stages. Every stage and the union have size $2^{\mu }$, since $(2^{\mu }{)}^{\mu }=2^{\mu }$ and ${\mu }^{+}\le 2^{\mu }$. The elementary chain theorem gives elementarity. Any sequence of at most $\mu$ members of the final union lies in a bounded stage, because ${\mu }^{+}$ is regular, and is added at the next stage. This proves the required closure.

Let $\beta =\sup (M\cap \theta )$. Regularity of $\theta$ gives $\beta <\theta$, and $\beta \notin M$: otherwise $\beta +1$ would also belong to $M\cap \theta$. Recursively choose increasing $x_{\alpha }\in M\cap \theta$ for $\alpha <{\mu }^{+}$ so that, for every $m$-subset $u$ of the earlier points,To justify the recursion, the earlier sequence has length at most $\mu$, hence belongs to $M$. There are at most $\mu$ constraints. All their points and color values are in $M$, so their coded table belongs to $M$ by closure, even though $\beta$ itself is external to $M$. The supremum of the earlier points, plus one, also belongs to $M\cap \theta$ and is below $\beta$. Thus $\beta$ witnesses in $H_{\chi }$ that a point above that bound satisfying the table exists. Elementarity supplies such a point in $M$. This completes the recursion.

The sequence is end-homogeneous: on any increasing $(m+1)$-tuple from it, the color depends only on its first $m$ entries. Define the induced $m$-tuple coloring by $g(u)=c(u\cup \{\beta \})$. For the induction, the arity-one assertion ${\lambda }^{+}\to ({\lambda }^{+}{)}_{\lambda }^1$ is the infinite pigeonhole principle: a union of $\lambda$ sets each of size at most $\lambda$ has size at most $\lambda$. At step $r\ge 1$, take $\mu ={\beth }_{r-1}(\lambda )$, so $\theta ={\beth }_r(\lambda {)}^{+}$. The constructed sequence has size ${\mu }^{+}={\beth }_{r-1}(\lambda {)}^{+}$. The induction hypothesis makes $g$ constant on a subset of size ${\lambda }^{+}$; end-homogeneity makes $c$ constant on its $(r+1)$-subsets. This proves the theorem. In particular $\lambda ={\aleph }_0$ gives an uncountable homogeneous set for every finite-arity coloring with countably many colors, on a sufficiently large cardinal.

There is no unrestricted infinite-exponent analogue under AC. For any infinite cardinal $\kappa$, choose one representative $R$ from each equivalence class of $[\kappa {]}^{\omega }$ modulo finite symmetric difference. Color $X$ by the parity of $|X△R|$. Removing one element of $X$ leaves it in the same class and reverses the parity. Every infinite proposed homogeneous set contains both a countably infinite $X$ and $X\setminus \{x\}$, so cannot be homogeneous. Thus the finite-symmetric-difference colouring of infinite subsets provesThe contrast is between arbitrary colorings at countably infinite arity and the finite arities of the theorem; restrictions on the definability of an infinite-arity coloring can change the problem.

The saturated model condition in degree $\kappa$ means that a first-order model $M$ realizes every one-variable complete type over a parameter set $A\subseteq M$ of size less than $\kappa$. Equivalently every finitely satisfiable such complete type is realized, since it can be extended to a complete type. Without a specified degree, saturated usually means $|M|$-saturated. Countable saturation means ${\aleph }_1$-saturation, including complete types over countably many parameters.

Here is a general saturated elementary extension theorem, with proof: for every infinite regular cardinal $\kappa$, every first-order structure $M$ has a $\kappa$-saturated elementary extension. At a stage $M_{\alpha }$, list all complete types over its subsets of size less than $\kappa$. There is a set of them, since their formulas lie in a set-sized language. Add a witness constant for each complete type to the elementary diagram of $M_{\alpha }$, together with every formula in that complete type evaluated at its witness constant. A finite part mentions finitely many complete types and finitely many formulas from each; each finite conjunction is realizable in $M_{\alpha }$, and the witnesses for different complete types are unconstrained relative to each other. Thus the finite part is satisfiable. The compactness theorem produces an elementary extension $M_{\alpha +1}$ realizing all those complete types. At limits take elementary unions, justified by the elementary chain theorem.

Iterate for $\kappa$ stages and put $N={\bigcup }_{\alpha <\kappa }{M}_{\alpha }$. If $A\subseteq N$ has size below $\kappa$, regularity bounds the stages at which its elements enter, so $A\subseteq M_{\alpha }$ for some $\alpha <\kappa$. A complete type over $A$ consistent with $N$ is finitely satisfiable in $M_{\alpha }$: each finite conjunction is an existential formula with parameters from $M_{\alpha }$, and elementarity transfers its truth from $N$. The complete type is therefore realized in $M_{\alpha +1}$. This provesFor a singular desired degree, apply the theorem at a larger regular cardinal. If $M$ is infinite and an uncountable regular $\kappa$ satisfies ${\kappa }^{<\kappa }=\kappa$, with $|L|<\kappa$ and $|M|\le \kappa$, the construction can keep every stage of size $\kappa$. There are then at most $\kappa$ parameter sets and complete types, and downward Löwenheim-Skolem gives that size after each extension; adding $\kappa$ distinct elements initially ensures final size exactly $\kappa$. The resulting model is saturated in the unqualified sense. The cardinal-arithmetic hypothesis belongs to this size refinement, not to the general existence theorem.

An explicit ultraproduct version is useful too. In a countable language let $U$ be a nonprincipal ultrafilter on $\omega$ and $N={\prod }_{i<\omega }{M}_i/U$, where each factor is nonempty. Enumerate a countable finitely satisfiable complete type, including its chosen parameter representatives, as ${\phi }_1(x),{\phi }_2(x),\dots$. By the Łoś theorem, the set $A_n$ of coordinates where the first $n$ formulas have a simultaneous witness belongs to $U$. PutThese are decreasing members of $U$. At coordinate $i$, let $k(i)$ be the greatest $n\le i$ with $i\in B_n$, if there is one. Choose a witness to the first $k(i)$ formulas there, and an arbitrary element when there is none. For fixed $n$, every coordinate in $B_n$ has $k(i)\ge n$, so the chosen function satisfies ${\phi }_n$ on a $U$-large set. Its ultraproduct class realizes the whole complete type. A countable language over a countable parameter set has only countably many formulas, so this proves countable saturation of a nonprincipal ultraproduct over omega.

For NFU, we give the rank-indiscernible construction of an NFU model explicitly. NFU has a unary predicate $S$ for sets, atoms have no members, extensionality applies to sets, and comprehension applies to every stratified formula. A stratification assigns integer types to variables so that equality uses equal types and $x\in y$ requires $\mathrm{type}(y)=\mathrm{type}(x)+1$. A unary set predicate adds no type difference.

Start with the actual set structure $B=(V_{\omega +\omega },\in )$. This structure satisfies extensionality and every pure-membership separation instance: the subset defined in a set $a$ of rank below $\omega +\omega$ still has rank below $\omega +\omega$. We do not assert that $B$ satisfies replacement or all of ZFC. Expand it by Skolem functions. In it use the sequence of rank objects $V_{\omega +n+6}$, $n<\omega$. For two such objects $d<e$ in sequence order, we havewith quantifiers in $B$. The second statement holds because every subset of $V_{\alpha }$ belongs to $V_{\alpha +1}$, and the later rank is at least $\alpha +1$.

Introduce constants $d_i$, $i\in \mathbb{Z}$, and require them to be order indiscernibles in the Skolem language, satisfying these two assertions whenever $i<j$. Also require $V_{\omega +5}\subseteq d_i$ for every $i$; this fixed rank object is first-order definable in $B$. Every finite part of these requirements together with $\mathrm{Th}(B^{\ast })$ is satisfiable: color finite increasing tuples of the original rank sequence by the truth values of the finitely many formulas mentioned, and use Ramsey's theorem to get a homogeneous subsequence. The rank assertions hold for every increasing tuple there. The compactness theorem gives a model of the full theory. In its Skolem hull $N$ generated by the $d_i$, the integer shift extends to an automorphism $j$ with $j(d_i)=d_{i+1}$, by the term-transport proof of the Ehrenfeucht-Mostowski theorem. Thus $N$ still satisfies extensionality and all pure-membership separation instances, andThis is a set-sized first-order model; no satisfaction predicate for a proper-class universe is being assumed.

Externally let $D_i=\{x\in N:N\models x\in d_i\}$. The automorphism bijects $D_i$ onto $D_{i+1}$. Interpret a typed structure with sort $i$ equal to $D_i$. At sort $i+1$, declare $y$ a set exactly when $N\models y\subseteq d_i$; otherwise it is an atom. Define adjacent-sort membership byThe guard is necessary: a typed atom might have some ordinary $N$-members in $D_i$, and those must not become its typed members. Set-extensionality follows from extensionality in $N$, because the ordinary members of a typed set all lie in $D_i$. For any typed formula on sort $i$, its quantifiers can be restricted to the corresponding $d_l$, its set predicates replaced by subset assertions, and its memberships replaced by the guarded relation. This is an ordinary pure-membership formula of $N$ with finitely many parameters. Separation gives its extension $X\subseteq d_i$, and the displayed closure assertion gives $X\in d_{i+1}$. It is therefore a typed set witnessing comprehension. The automorphism shifts these sorted domains and preserves the set flags and guarded memberships.

Collapse the types onto $D_0$. DefineObjects not satisfying $S$ have no $E$-members. If two sets have the same $E$-members, their images under $j$ are subsets of $d_0$ with the same ordinary members, so are equal by extensionality of $N$; injectivity of $j$ gives equality of the original objects.

To verify every stratified comprehension instance, assign a variable $v$ its stratification type $t(v)$ and translate its value $a\in D_0$ to $j^{t(v)}(a)\in D_{t(v)}$. Equality is preserved. An atomic $E(x,y)$ translates to the guarded adjacent-sort membership because $t(y)=t(x)+1$; the unary predicate $S(y)$ translates to $j^{t(y)}(y)\subseteq d_{t(y)-1}$. Induction on formulas, using the domain bijections for quantifiers, preserves truth. If the free variable $x$ has type $t$, typed comprehension produces its extension $X\subseteq d_t$, with $X\in d_{t+1}$. Put $b=j^{-(t+1)}(X)\in D_0$. Then $S(b)$ holds, and for every $a\in D_0$,This is exactly the required NFU set. No formula containing the external automorphism $j$ has been used in a separation or comprehension scheme; $j$ only transports values after the pure formula is formed.

The construction also permits the usual infinity requirement. The ordinary $\omega$ and its successor graph $f$ are definable in $N$, hence fixed by $j$, and lie below $V_{\omega +5}$, so belong to all the required domains. Under $E$, the members of $\omega$ are still its ordinary $N$-members. The new Kuratowski pair satisfiesSince $j(f)=f$, membership of this pair in $f$ under $E$ is equivalent to $⟨x,y{⟩}_N\in f$. Thus $f$ is an internal injection of $\omega$ into itself omitting zero, giving a Dedekind-infinite set.

We have built a model of NFU, with infinity if it is included in the formulation, in ordinary ZFC metatheory:In particular $\mathrm{Con}(\mathrm{ZFC})\Rightarrow \mathrm{Con}(\mathrm{NFU})$. This proof does not assume $\mathrm{Con}(\mathrm{ZFC})$ as an additional internal axiom: its starting structure is the set $V_{\omega +\omega }$, not a model of ZFC.

A useful form of the Ehrenfeucht-Mostowski theorem says that, for an infinite first-order structure $M$ and any total order $I$, there is a model of $\mathrm{Th}(M)$ generated as a Skolem hull by distinct order indiscernibles $(a_i{)}_{i\in I}$. Every order automorphism of $I$ extends uniquely to an automorphism of the specified Skolem expansion of that hull. The model can be obtained inside an elementary extension of a Skolem expansion of $M$; the generated hull itself need not contain $M$.

Choose a Skolem expansion $M^{\ast }$ by iteratively adjoining witness functions: for each existential formula in the current language choose a function returning a witness whenever one exists, with an arbitrary value otherwise. Repeat for countably many rounds. Every formula in the final language uses finitely many symbols, so has a witness function from a later round. Thus the expansion is Skolemized for its own formulas, as required for elementarity of its hull. Add constants $a_i$ for $i\in I$ to the complete theory of $M^{\ast }$, require them to be distinct, and impose the schemefor every formula in the Skolem language. If an elementary extension of $M^{\ast }$ is desired, also add its elementary diagram with separate names for its elements.

Every finite part of this theory is satisfiable. Choose infinitely many distinct elements $b_0,b_1,\dots$ of $M$. For each of the finitely many arities in that fragment, color increasing index tuples by the finite vector of truth values of the formulas occurring. Repeated applications of the infinite Ramsey theorem give an infinite subset on which all these vectors are constant. Interpret the finitely many $a_i$ in increasing-index order from that subset. This satisfies the finite indiscernibility requirements and distinctness, while the elementary diagram is satisfied by the named original structure. The compactness theorem gives a structure $N^{\ast }$ satisfying the whole theory.

Let $H$ be the closure of the $a_i$ under the Skolem functions, including nullary ones. It is elementary in $N^{\ast }$: whenever an existential formula with parameters from $H$ is true in $N^{\ast }$, its Skolem witness lies in $H$. This is the Tarski-Vaught test, whose proof is induction on formulas, using precisely this witness property for the existential step. Hence the reduct of $H$ is a model of $\mathrm{Th}(M)$.

For an order automorphism $\sigma :I\to I$, defineThis is well-defined. If two terms denote the same element, write their equality as a formula on the combined increasing tuple of their indices; indiscernibility preserves that formula after transport by $\sigma$. The same argument preserves every relation and function. Applying ${\sigma }^{-1}$ gives the inverse, so $\hat{\sigma }$ is an automorphism. Since all elements are terms in the generators, it is the unique automorphism of this Skolem expansion extending $a_i\mapsto a_{\sigma (i)}$. This proves the theorem.

One may require the indiscernibles to lie in any specified infinite sequence of the starting structure, or to satisfy additional finite-tuple properties holding along that sequence: the same finite satisfiability proof chooses its homogeneous subsequence there. This strengthened form is what the rank-domain construction of NFU uses. Uniqueness is asserted in the Skolem expansion, not for all automorphisms of its reduct.

For $A\subseteq {\omega }^{\omega }$, let the players alternately choose natural numbers, producing $x\in {\omega }^{\omega }$; I wins exactly when $x\in A$. A strategy assigns a move to each finite position at which its player moves. It is winning if every compatible completed play is won by that player. A game is determined when one player has a winning strategy. The axiom of determinacy is

We can prove determinacy for open and closed payoffs, including clopen payoffs; finite games are covered by backward induction. Here is the full open-payoff argument. For an open $A$, let $W_0$ consist of finite positions whose entire cylinder of continuations is contained in $A$. Recursively putand take unions at limits. Since positions form a set, this process reaches a fixed point $W$. More explicitly, a strict increase at each stage would assign a distinct position to each stage beyond the Hartogs bound of the position set, which is impossible; for natural-number moves the least newly added position in a fixed enumeration makes that assignment explicit.

If the initial position belongs to $W$, I can win. At an I-position first added at a successor stage, choose the least move to a position of smaller first-entry rank. At an II-position first added at a successor stage, every successor already has smaller rank. A play following this strategy cannot have an infinite strictly descending sequence of ordinal ranks, so reaches $W_0$ in finitely many steps; all its further continuations lie in $A$. If the initial position is outside $W$, II keeps the play outside $W$: at an I-position no successor is in $W$, and at an II-position at least one successor is outside $W$, so II chooses the least such move. The play never reaches a winning prefix. Since $A$ is open, membership in $A$ would have been certified by some finite prefix, so the resulting play is outside $A$. Thus every open game is determined. Applying this argument to the open complement of a closed payoff, with the players' objectives interchanged, proves closed determinacy too. The argument needs no choice of moves beyond taking the least available natural number.

To refute AD under AC, first use binary moves. There are $\mathfrak{c}=2^{{\aleph }_0}$ strategies for each player, since its positions form a countable set. Enumerate them as $({\sigma }_{\alpha }{)}_{\alpha <\mathfrak{c}}$ and $({\tau }_{\alpha }{)}_{\alpha <\mathfrak{c}}$. Each fixed strategy admits exactly $\mathfrak{c}$ compatible plays: the other player's arbitrary binary sequence determines the completed play injectively. Recursively choose a play $u_{\alpha }$ following ${\sigma }_{\alpha }$ and a play $v_{\alpha }$ following ${\tau }_{\alpha }$, each different from all earlier reservations and from each other. This is possible because at stage $\alpha$ fewer than $\mathfrak{c}$ plays have been reserved. No regularity assumption on $\mathfrak{c}$ is used: every ordinal $\alpha <\mathfrak{c}$ has cardinality below $\mathfrak{c}$, and doubling an infinite smaller cardinal does not reach $\mathfrak{c}$.

Set $B=\{v_{\alpha }:\alpha <\mathfrak{c}\}\subseteq 2^{\omega }$. Strategy ${\sigma }_{\alpha }$ loses on $u_{\alpha }\notin B$, while ${\tau }_{\alpha }$ loses on $v_{\alpha }\in B$. Thus this binary game is undetermined. Turn it into a natural-number game by declaring that the first player to play a number outside $\{0,1\}$ loses. Formally its I-payoff isA winning strategy in this game could not prescribe an illegal move after a compatible legal history, since the opponent could thereby win. Its restriction to legal histories would therefore give a winning binary strategy, contradicting the construction. Hence the choice diagonalization of an undetermined game provesThis does not contradict open or closed determinacy: the diagonal payoff has no such regularity requirement.