Past exam of the mathematics course of the University of Cambridge / 2005 / iii / Paper 27 (Set Theory)

Let $K_s$ be the finite approximation to the halting problem obtained by running the first $s$ programs for $s$ steps, so $K_s\subseteq K_{s+1}$ and $K={\bigcup }_s{K}_s$ is not computable. For $x<y<z$, define the recursive triple colouring with no computable infinite homogeneous set byThis is a total computable function. Here homogeneous sets are required to be infinite: finite homogeneous sets certainly exist. An infinite homogeneous $H$ cannot have colour one. Fix $x\in H$; the finite approximation below $x$ eventually stabilizes, so two sufficiently large $y<z$ in $H$ give colour zero. If $H$ has colour zero, choose $x<y$ in $H$ with $x\ge e$. For arbitrarily large $z\in H$, homogeneity gives $K_y\cap [0,x]=K_z\cap [0,x]$, and hence $K_y\cap [0,x]=K\cap [0,x]$. Thus $H$ computes membership of $e$ in $K$. A computable infinite $H$ would make the halting problem computable, a contradiction.

For the uncountable partition relation, the Erdős-Rado theorem for finite arities states that for every infinite cardinal $\kappa$ and integer $n\ge 1$,The case $n=1$ is the pigeonhole principle: a union of $\kappa$ sets of size at most $\kappa$ cannot have size ${\kappa }^{+}$. Suppose the assertion holds for $n-1$. Put $\mu ={\beth }_{n-2}(\kappa )$ and $\lambda =(2^{\mu }{)}^{+}$, and let $c:[\lambda {]}^n\to \kappa$. We give the closed elementary-submodel construction of an end-homogeneous sequence, which avoids intersecting a decreasing family of reservoirs at a limit stage.

Take a sufficiently large regular $\chi$ and an elementary substructure $M\prec H_{\chi }$ with $|M|=2^{\mu }$, containing $c,\lambda$ and all ordinals below ${\mu }^{+}$, and closed under sequences of length at most $\mu$. Such an $M$ is obtained by ${\mu }^{+}$ successive Skolem hull closures: $(2^{\mu }{)}^{\mu }=2^{\mu }$, and the regularity of ${\mu }^{+}$ puts any at-most-$\mu$-long sequence from the union inside one stage. Put $\beta =\sup (M\cap \lambda )<\lambda$. The set $M\cap \lambda$ has no greatest element, since taking an ordinal successor is definable in $M$, so $\beta \notin M$.

Recursively choose an increasing sequence $⟨x_{\xi }:\xi <{\mu }^{+}⟩$ in $M\cap \lambda$. At stage $\xi$, its earlier set $A$ has size at most $\mu$, and the colour table $g(u)=c(u\cup \{\beta \})$ on $[A{]}^{n-1}$ has size at most $\mu$. Both $A$ and this table belong to $M$ by its closure. The setbelongs to $M$ and is nonempty because it contains $\beta$. Elementarity supplies $x_{\xi }\in X\cap M$. Consequently the colour of each $n$-tuple from the resulting sequence depends only on its first $n-1$ entries. The induction hypothesis applied to these entries gives a homogeneous subsequence of size ${\kappa }^{+}$, proving the result.

Infinite exponents behave differently with the axiom of choice. On the countably infinite subsets of any infinite cardinal $\lambda$, choose a representative of each equivalence class modulo finite symmetric difference. Colour a set $A$ by the parity of $|A△R_A|$. Removing one point flips its colour. Every infinite proposed homogeneous set contains an increasing sequence of order type $\omega$, and that sequence and its tail have opposite colours. Thus the finite-symmetric-difference colouring of infinite subsets gives $\lambda /⟶(\omega {)}_2^{\omega }$, whether the domain consists of all countably infinite subsets or only those of order type $\omega$. There is no unrestricted infinite-arity counterpart to the displayed finite-arity theorem in ZFC.

The assertions are relative independence results. We construct countermodels in a background model of ZFC; if ZF is consistent, its constructible universe gives a model of ZFC as well. The original model satisfies foundation and choice, supplying the positive sides.

For failure of foundation, use a Rieger-Bernays permutation model. Let $\pi$ interchange the old $\varnothing$ and $\{\varnothing \}$ and fix every other object, and put $xEy$ iff $x\in \pi (y)$. The new extension of $y$ is the old set $\pi (y)$, so the representative of any old extension $b$ is ${\pi }^{-1}(b)$. Bijectivity gives extensionality. Translate formulas recursively by this definition of $E$. Old separation gives each new definable subset, and old replacement gives each new functional range; apply ${\pi }^{-1}$ to the resulting extension to obtain its new representative.

Explicitly, a new pair is represented by ${\pi }^{-1}(\{x,y\})$; the new union of $a$ is represented by ${\pi }^{-1}({\bigcup }_{x\in \pi (a)}\pi (x))$; and the new power set of $a$ is represented byStarting from the new empty set, iterate the new successor and collect these iterates by old replacement, obtaining an inductive set. The old axiom of choice selects a member from each nonempty extension and thereby gives new choice functions. However the old object $q=\varnothing$ now satisfies $qEq$ and has exactly itself as its member: it is a Quine atom. Its new singleton has no $E$-minimal member, so foundation fails.

To make choice fail, retain infinitely many Quine atoms $A=\{a_n:n<\omega \}$ and impose a finite-support symmetry restriction. A precise background construction uses tagged set codes. Each atom $a$ has extension $\{a\}$. For every other set of available objects $S$, introduce a unique ordinary set code with extension $S$, except that $S=\{a\}$ is already represented by $a$ itself. Iterate this construction through the ordinals. Omitting the duplicate singleton codes makes the resulting relation extensional. Every permutation of $A$ extends to an automorphism of this universe by recursion through its ordinary codes.

An object has finite support if some finite $S\subseteq A$ has the property that every permutation fixing $S$ pointwise fixes that object. Retain the hereditarily finite-supported Quine-atom model: the object and every object reached through its membership relation must have finite support. The atomic self-loops are permitted. The atom set $A$ and all pure sets are retained.

The union of supports for a domain and finitely many parameters supports any definable subset or functional image: every permutation fixing those supports preserves the defining formula. Members of the subset or image are already hereditary, so this verifies separation and replacement. The collection of all retained subsets of a retained set is invariant under any permutation fixing that set's support, and each of its members is hereditary; this verifies the Axiom of power set. Pairs and unions have the union of the requisite finite supports, and the pure natural-number hierarchy verifies infinity. The coding still verifies extensionality.

If a choice function on all two-element subsets of $A$ had finite support $S$, choose distinct $a,b\notin S$. The transposition of $a,b$ fixes $S$ and the unordered pair $\{a,b\}$, but moves either possible chosen value. This contradicts invariance of the function. Hence choice fails, while a Quine atom witnesses failure of foundation. We have a model of $\mathrm{ZF}-\mathrm{Foundation}+\neg \mathrm{Choice}$. Together with the original model this proves the required independence of choice over $\mathrm{ZF}-\mathrm{Foundation}$.

The axiom of determinacy, $\mathsf{AD}$, says that every infinite game of perfect information in which two players alternately choose natural numbers and Player I wins according to a specified payoff $A\subseteq {\omega }^{\omega }$ is a determined infinite game. A strategy specifies a move at every finite position where its player moves; it is winning if every compatible infinite play is won by that player.

Finite games are determined by backward induction. For infinite games, open determinacy has a direct proof. Let $T$ consist of the finite positions whose extension cylinder sets lie in the open payoff $A$. Build the winning-position attractor in an infinite game by transfinite recursion: start with $T$, add an I-position if some successor has already entered, add a II-position if every successor has already entered, and take unions at limit stages. The process stabilizes because there are only countably many finite positions.

At a position in the attractor but outside $T$, I can choose a successor with strictly smaller entry rank, and every move of II has smaller entry rank. There is no infinite descending sequence of ordinals, so I forces entry into $T$ and wins. Outside the attractor, every I-move stays outside it, while II can choose a successor outside it; that strategy avoids $T$ forever. Since $A$ is open, a play belongs to $A$ exactly when some prefix belongs to $T$. Thus II wins from outside the attractor. This proves determination for open payoffs; swapping the players proves it for closed payoffs too. The stronger Borel determinacy theorem gives determination for every Borel set payoff, whereas $\mathsf{AD}$ asserts this for arbitrary payoffs.

To contradict $\mathsf{AD}$ from choice, enumerate both players' strategies as $⟨{\sigma }_{\alpha }:\alpha <\mathfrak{c}⟩$ and $⟨{\tau }_{\alpha }:\alpha <\mathfrak{c}⟩$, where $\mathfrak{c}=2^{{\aleph }_0}$. There are $\mathfrak{c}$ strategies because the set of finite positions is countable; there are also $\mathfrak{c}$ plays following any fixed strategy because the other player's moves are arbitrary. At stage $\alpha$ of the choice diagonalization of an undetermined game, choose a fresh play $x_{\alpha }$ following ${\sigma }_{\alpha }$ and then a different fresh play $y_{\alpha }$ following ${\tau }_{\alpha }$, avoiding all earlier reservations. This is possible because fewer than $\mathfrak{c}$ plays have been reserved at every $\alpha <\mathfrak{c}$; regularity of $\mathfrak{c}$ is not required.

Set $A=\{y_{\alpha }:\alpha <\mathfrak{c}\}$. Every ${\sigma }_{\alpha }$ loses on $x_{\alpha }\notin A$, and every ${\tau }_{\alpha }$ loses on $y_{\alpha }\in A$. Thus neither player has a winning strategy, and AD and AC are inconsistent together.

Work in a background model of ZFC. Each structure below satisfies every axiom of ZF except the indicated one and falsifies that axiom; the background model supplies the other consistency direction.

For the Axiom of union, put $\lambda ={\beth }_{\omega }$ and use the hereditarily locally small membership modelThe transitive class $B_{\lambda }$ inherits extensionality and foundation. Definable subsets of its sets remain in it. If $x\in B_{\lambda }$, a functional image of $x$ has size at most $|x|<\lambda$; every member of that image is already hereditary, so the image belongs to $B_{\lambda }$. This verifies replacement, even though its values can have unbounded ranks. Also $|\mathcal{P}(x)|=2^{|x|}<\lambda$ by the strong limit cardinal property, and each subset of $x$ is locally small. This verifies the Axiom of power set. Pairing and infinity follow similarly. Butsince $|V_{\omega +n}|={\beth }_n<\lambda$ while $|V_{\omega +\omega }|=\lambda$. This is failure of sumset without failure of replacement or power set.

For the Axiom of power set, use the hereditarily countable sets $H_{{\omega }_1}$. This is a transitive class. A countable union of countable transitive closures is countable, so it is closed under pairs, unions and functional images of its countable domains; these facts verify pairing, union and replacement. Separation, foundation and infinity also hold. Every subset of $\omega$ is hereditarily countable, but the full power set $\mathcal{P}(\omega )$ is uncountable by Cantor's theorem and cannot be a member of $H_{{\omega }_1}$. Since every candidate internal power set would have to contain all those subsets, the power-set axiom fails.

For replacement, take the rank-initial transitive set $V_{\omega +\omega }$. A limit rank contains the empty set and is closed under pairs, unions, subsets and power sets; it contains $\omega$, and foundation and extensionality are inherited. Fix the parameter $V_{\omega }$. The definable mapis internally described by a finite sequence of power-set iterations. Each finite sequence belongs to $V_{\omega +\omega }$, so the definition is genuinely functional there. Its range has rank $\omega +\omega$ and is not in the structure. Thus this instance of replacement fails.

For extensionality, use the non-extensional membership model with one atom. Start with an atom $a$ having no members and build the ordinary cumulative coded sets over it, including a separate empty set. Interpret membership by the contents of a set code and give $a$ no members. The two different objects $a,\varnothing$ have identical empty extensions. Foundation holds by the code ranks; pure finite ordinals give infinity; pairs, unions, definable subsets and functional ranges have their usual set codes. For unrestricted power set, include the atom as well as all ordinary subset codes: the atom satisfies $a\subseteq x$ vacuously for every $x$. This detail is necessary because the formulas here are the unmodified ZF formulas, without a set predicate. The collection still has a set code, so the Axiom of power set holds. All axioms except extensionality are satisfied.

Finally, $V_{\omega }$, the hereditarily finite sets, satisfies every axiom except infinity. Pairs, unions, power sets and subsets of finite sets are finite, and every functional image of a finite domain is finite, so the full replacement schema holds. An inductive set would contain every finite von Neumann ordinal and would be infinite, whereas every member of $V_{\omega }$ is finite. Hence infinity fails.

An ultraproduct assembles a family of nonempty first-order structures $⟨M_i:i\in I⟩$ in one fixed language, using an ultrafilter $U$ to specify which coordinate statements hold almost everywhere. Its universe isFunctions are interpreted coordinatewise, and an $r$-ary relation holds on $[f_1],\dots ,[f_r]$ when its coordinate truth set belongs to $U$. Changing representatives changes such a truth set only off a $U$-large set, so these definitions are well defined. A principal ultrafilter simply recovers its distinguished factor; a nonprincipal ultrafilter can produce new elements and structures.

The fundamental result is the Łoś theorem:Prove it by structural induction on first-order formulas. Atomic formulas are the definition. Intersections handle conjunction, while exactly one of a set and its complement belongs to an ultrafilter, handling negation. For the existential step, if the coordinate existential truth set is in $U$, use choice to select witnesses there and arbitrary values elsewhere; their product function is an ultraproduct witness. Conversely a product witness makes the coordinate existential truth set contain a $U$-large set. Other connectives and universal quantification follow.

In an ultrapower, all factors are one structure $M$. The diagonal map $a\mapsto [\text{constant }a]$ is an elementary embedding by the Łoś theorem. For a nonprincipal $U$ on $\omega$, the class of $n\mapsto n$ in an ultrapower of the standard natural numbers is larger than every constant natural number, since each tail belongs to $U$. This gives a nonstandard model of Peano arithmetic. Similarly, an ultraproduct of finite fields ${\mathbb{F}}_{p_i}$ with distinct primes tending to infinity has characteristic zero: for every fixed positive integer $m$, the equation $m1=0$ fails in all sufficiently late factors. An infinite structure can therefore arise from finite factors.

Ultraproducts prove the compactness theorem. If each finite subset $\Delta$ of a theory $T$ has a model $M_{\Delta }$, index these models by $[T{]}^{<\omega }$. The cones $\{\Delta :\phi \in \Delta \}$ have the finite intersection property. Extend their filter to an ultrafilter using the ultrafilter lemma. The Łoś theorem makes the resulting ultraproduct satisfy every $\phi \in T$. This construction also gives elementary extensions realizing prescribed finitely satisfiable types.

A useful stronger property is countable saturation of an ultraproduct over omega. Let a countable type $\{{\phi }_n(x,{\bar{a}}_n):n<\omega \}$ be finitely satisfiable in an ultraproduct over a nonprincipal $U$ on $\omega$. Choose coordinate representatives of its parameters. Let $E_n$ be the coordinates where the first $n$ formulas have a simultaneous witness; then $E_n\in U$, the $E_n$ decrease, and we can replace $E_n$ by $E_n\cap [n,\infty )$. At coordinate $i$, choose a witness to the first $m(i)$ formulas, where $m(i)$ is the largest $n\le i$ with $i\in E_n$, taking an arbitrary value if there is none. For each fixed $n$, the set where $m(i)\ge n$ is $U$-large. Its class realizes the entire type. This proof uses countable incompleteness of $U$, not arbitrary completeness or automatic saturation at larger cardinals.

Finally, complete ultrafilters connect ultraproducts to large cardinals. A countably complete ultrafilter prevents an externally infinite descending membership chain in an ultrapower of a well-founded universe: intersect the countably many coordinate truth sets and obtain an impossible descending chain at one coordinate. A kappa-complete nonprincipal ultrafilter on $\kappa$ consequently supplies the ultrapower embedding associated with a measurable cardinal. Thus the same construction supports both elementary compactness arguments and large-cardinal embeddings, with the completeness hypothesis deciding which well-foundedness and closure properties survive.

A measurable cardinal is an uncountable cardinal $\kappa$ carrying a kappa-complete nonprincipal ultrafilter $U$ on $\kappa$. An elementary embedding $j:M\to N$ preserves all first-order formulas with parameters:For a measurable $\kappa$, the Łoś theorem gives an elementary map from the universe into its ultrapower. Countable completeness makes that ultrapower well founded, so the Mostowski collapse gives a transitive target $M$ and an ultrapower embedding $j:V\to M$. The least moved ordinal, its critical point of an elementary embedding, is $\kappa$: every function into an ordinal below $\kappa$ is constant on a $U$-large set by kappa-completeness, whereas the identity function on $\kappa$ represents an ordinal above every constant ordinal below $\kappa$ and below the image of $\kappa$. Conversely a suitably available embedding with critical point $\kappa$ defines the measure $U=\{X\subseteq \kappa :\kappa \in j(X)\}$.

The identity $V\to V$ is elementary. In ZFC there is no nonidentity elementary class embedding $j:V\to V$, by the Kunen inconsistency theorem. Here the embedding is a class for which restrictions to sets and the critical sequence are available, as in the usual class-theoretic formulation. The axiom of choice is part of this conclusion; it is not a claimed contradiction for the choice-free Reinhardt-cardinal hypothesis.

Here is the stationary-set proof. A nonidentity $j$ has a least moved ordinal $\kappa$; if all ordinals were fixed, induction on rank would fix every set. Put ${\kappa }_0=\kappa$, ${\kappa }_{n+1}=j({\kappa }_n)$ and $\lambda ={\sup }_{n<\omega }{\kappa }_n$. Since $j$ fixes $\omega$ and shifts this sequence, $j(\lambda )=\lambda$. It therefore fixes the regular successor cardinal $\delta ={\lambda }^{+}$. The stationarity of ordinals of prescribed cofinality gives the stationary setUse the stationary partition at a successor cardinal to split $S$ into $\kappa$ disjoint stationary pieces $⟨S_{\alpha }:\alpha <\kappa ⟩$, merging pieces if necessary. Applying $j$ gives a partition $⟨T_{\alpha }:\alpha <j(\kappa )⟩$ of the same $S$ into stationary pieces. The additional piece $T_{\kappa }$ is stationary.

The closure pointsform a club set. For unboundedness, repeatedly close a bound under the values of $j$ below it and take the supremum of the resulting countable sequence; regularity of $\delta$ keeps it below $\delta$. Closure under limits is immediate. Choose $\beta \in C\cap T_{\kappa }$ and an increasing sequence $⟨{\beta }_n:n<\omega ⟩$ cofinal in $\beta$. Thenwhile every ordinal satisfies $j(\beta )\ge \beta$, so $j(\beta )=\beta$. There is an $\alpha <\kappa$ with $\beta \in S_{\alpha }$. Since $j(\alpha )=\alpha$, elementarity gives $\beta =j(\beta )\in j(S_{\alpha })=T_{\alpha }$, contrary to disjointness from $T_{\kappa }$.

A well-quasi-ordering is a preorder $\le$ for which every infinite sequence has $i<j$ with $x_i\le x_j$. Such a comparable pair is good; a sequence without one is a bad sequence. Equivalently there is no infinite strictly descending chain in the quotient order and no infinite antichain.

A better-quasi-ordering strengthens this by requiring every barrier array to be good. A barrier in better-quasi-order theory on an infinite $A\subseteq \omega$ is a family $B$ of nonempty finite increasing sequences, no one properly contained in another, such that every infinite subset of $A$ has an initial segment in $B$. Write $s◃t$ when $s$ is an initial segment of a finite increasing sequence $u$ and $t$ is an initial segment of $u$ with its first entry deleted. A map $f:B\to Q$ is good if some $s◃t$ satisfy $f(s)\le f(t)$. Requiring this for all barriers defines a better-quasi-ordering. Singleton barriers recover well-quasi-ordering; the stronger property supports infinitary closure operations that can fail for a mere well-quasi-ordering.

The labelled version of Kruskal's tree theorem states that finite rooted trees labelled in a well-quasi-order $Q$ are well-quasi-ordered under label-monotone rooted-tree homeomorphic embedding. An embedding sends edges to nonempty downward paths, separates different child branches, and increases labels. Initially allow the source root to land at any vertex of the target. We prove this version; forcing roots to match follows at the end.

Suppose there is a bad sequence $T_0,T_1,\dots$. Choose it as a minimal bad sequence: at each stage choose a tree with the fewest vertices among those admitting a bad continuation of the already fixed prefix. Let $U$ contain all proper rooted descendant subtrees of these trees. We first show that $U$ is well-quasi-ordered by the same root-flexible embedding.

Otherwise choose a bad sequence $S_0,S_1,\dots$ from $U$. Each finite collection of the $T_n$ has only finitely many descendant subtrees, and a bad sequence cannot repeat an object. Thus, after passing to a subsequence, choose strictly increasing $n_i$ such that $S_i$ is a proper descendant subtree of $T_{n_i}$. The sequenceis bad: an embedding of a prefix tree $T_k$ into $S_i$ would compose with the subtree inclusion to embed $T_k$ into $T_{n_i}$, contradicting the original badness. But $S_0$ is smaller than $T_{n_0}$, contradicting minimality. Hence $U$ is well-quasi-ordered.

Give the children of each root any fixed linear order, and describe a tree by its root label and the word of its child subtrees. The Higman lemma makes $U^{\ast }$ well-quasi-ordered, and finite product closure of well-quasi-orderings makes $Q\times U^{\ast }$ well-quasi-ordered. There are therefore $i<j$ with an increased root label and an embedding of the child word of $T_i$ as a subsequence of that of $T_j$. Embed the root into the root, use the chosen subtree embeddings inside the corresponding distinct target branches, and join their root images to the target root by downward paths. This gives a label-monotone tree embedding $T_i\to T_j$, the required contradiction.

If root-preserving embeddings are required, replace $Q$ by the disjoint union of two copies of $Q$, label every root in copy one and every other vertex in copy zero, and allow comparisons only within a copy. This is again a well-quasi-order. The unique copy-one vertex of a tree forces an embedding to send root to root. Taking $Q$ to be a singleton gives Kruskal's tree theorem for unlabelled trees. The Higman lemma used above follows from the same minimal-bad-sequence argument for words: delete the last letters along an infinite nondecreasing subsequence of those letters; a good pair among the shortened words would extend to a good pair of original words, contradicting minimality. Empty shortened words cause an immediate good pair. This supplies the word lemma needed in the tree proof.

Fix an ordinal $\rho >1$. The Generalized Cantor normal form asserts that every nonzero ordinal $\alpha$ has a unique expressionProducts, sums and powers here are ordinal multiplication, ordinal addition and ordinal exponentiation; the coefficients need not be finite if $\rho$ is infinite. The case $\rho =\omega$ is Cantor normal form, and a finite base on finite ordinals gives ordinary positional notation. Zero has the empty expansion.

We first prove the ordinal division algorithm. For $\delta >0$, the function $q\mapsto \delta q$ is strictly increasing, continuous at limit ordinals and unbounded. Hence there is a greatest $q$ with $\delta q\le \alpha$: the first $q^{\prime }$ with $\delta q^{\prime }>\alpha$ cannot be a limit by continuity and must equal $q+1$. The interval after the initial segment $\delta q$ has a unique order type $r$, so $\alpha =\delta q+r$. Maximality of $q$ gives $r<\delta$. These facts also prove uniqueness of $q,r$.

Similarly $\beta \mapsto {\rho }^{\beta }$ is strictly increasing, continuous at limits and unbounded, so there is a unique largest ${\beta }_0$ with ${\rho }^{{\beta }_0}\le \alpha$. Divide by ${\rho }^{{\beta }_0}$ to obtainThe quotient is positive, and $\alpha <{\rho }^{{\beta }_0+1}={\rho }^{{\beta }_0}\rho$ makes ${\xi }_0<\rho$. If $r_0>0$, repeat on $r_0$; its leading exponent is strictly smaller than ${\beta }_0$. This process terminates, since an infinite run would give an infinite descending sequence of ordinals. It constructs the required form.

For uniqueness, a finite expression with largest exponent $\beta$ and coefficients below $\rho$ has value below ${\rho }^{\beta +1}$. Prove this from the end backwards: a tail with largest exponent $\gamma <\beta$ is below ${\rho }^{\gamma +1}\le {\rho }^{\beta }$, andThus the displayed leading exponent is the uniquely determined largest $\beta$ with ${\rho }^{\beta }\le \alpha$. The ordinal division algorithm uniquely determines its coefficient and the remaining tail, and recursion proves uniqueness of the whole expression. No commutative rearrangement of ordinal sums is used.

We give a relative consistency proof: a model of ZFC yields a model of NFU. This proves the requested consistency relative to the usual background set theory; it does not claim the optimal, much weaker consistency bound for bare NFU.

Recall that New Foundations with urelements has a unary set predicate $S$, atoms without members, extensionality restricted to sets, and comprehension for every stratified formula. Stratification assigns integer types to variables, with equal types at equality and adjacent types at membership. We construct a model of simple typed set theory with atoms with a type-shifting automorphism, then identify its types using that automorphism.

Start with a model of ZFC and a Skolem expansion of it. By the compactness theorem there is a model $N$ of the same expanded theory with an increasing integer-indexed order-indiscernible sequence of ordinals $⟨c_i:i\in \mathbb{Z}⟩$, all above $\omega$. Here is the finite-satisfiability argument. A finite fragment names only finitely many $c_i$ and asks for equal truth values of finitely many formulas on increasing tuples. In the starting model choose an infinite increasing sequence of ordinals above $\omega$. Colour its finite subsets by these truth vectors, successively treating each tuple length. The Ramsey's theorem supplies an infinite homogeneous subsequence for the finitely many colours and arities. Its first required number of elements interprets all named $c_i$ and satisfies that fragment. Compactness gives the entire sequence. This argument works for the countable expanded language because each fragment uses only finitely many formulas.

Replace $N$ by the Skolem hull of the $c_i$. The mapis well defined by indiscernibility: equal terms remain equal after shifting their increasing lists of indices. The same argument preserves every formula. Shifting indices backwards gives its inverse, so $j$ is an automorphism of the hull, and $j(c_i)=c_{i+1}>c_i$. The Skolem hull is elementary by its witness functions. This is a concrete Ehrenfeucht-Mostowski model; it is not an elementary class self-embedding of the actual well-founded universe.

Set $D_i=V_{c_i}^N$, interpreted externally as the objects belonging to that internal rank segment, for every integer $i$. At type $i$ declareand define adjacent-type membership byThe members of a type-$i+1$ set are exactly a subset of $D_i$; a type-$i+1$ atom has no ${\epsilon }_i$-members. Every internal subset of $D_i$ is an object of $D_{i+1}$, since $c_{i+1}>c_i$. Extensionality for sets is inherited from $N$. For a typed formula involving finitely many types, restrict its quantifiers to the corresponding internal $D_k$ and express each $S_k$ and ${\epsilon }_k$ by the displayed definitions. Separation in $N$ gives the required subset of $D_i$, which represents its comprehension at type $i+1$. This verifies the typed theory even though many higher-type objects are atoms. The automorphism $j$ carries $D_i,S_i,{\epsilon }_i$ to the next type.

On domain $D_0$, define $S(x)=S_0(x)$ andIf $S(y)$ is false, $S_1(j(y))$ is false, so $y$ has no $E$-members. For sets $y,z$, equality of their $E$-extensions gives equality of the typed sets $j(y),j(z)$ and hence $y=z$. To check stratified comprehension, translate a variable of type $k$ into $j^k(x)$. The automorphism laws make membership and equality translate exactly. A stratified predicate on a variable of type zero defines a typed subset $B$ of $D_0$, represented by a set at type one. Then $b=j^{-1}(B)\in D_0$ has $E$-extension exactly that predicate. A uniform type shift handles any other type assigned to the comprehended variable. The resulting untyped structure is a model of NFU.

Use the natural partial orderThe paper's shorthand $x\le x+y$ specifies the join order: more formally, $x\le z$ means $z=x+y$ for some $y$, which is equivalent to the displayed condition by idempotence. Associativity, commutativity and idempotence make addition the join operation. Distributivity makes multiplication monotone, while absorption gives $xy\le x$ and $xy\le y$.

Let $g_1,\dots ,g_r$ generate the incline. Distributivity writes every element as a nonempty finite join of monomialsThere is no assumed multiplicative identity: an exponent zero means omit that factor, and at least one factor remains. If $u\le v$ coordinatewise, absorption gives $m(v)\le m(u)$. If the two vectors are equal the conclusion is immediate; otherwise multiply $m(u)$ by the additional factors and apply absorption. For a polynomial with finite exponent support $A$, put $U_A=\{v:(\exists u\in A)u\le v\}$, its upward closure. If $U_A\supseteq U_B$, every monomial in $B$ is below some monomial in $A$, and consequently the join represented by $B$ is below the join represented by $A$.

We prove the reverse-inclusion well-quasi-ordering of monomial ideals, often called Maclagan's theorem, in the equivalent form that upward-closed subsets of ${\mathbb{N}}^r$ are well-quasi-ordered by reverse inclusion. Include the empty subset. For $r=1$, these are the tails $[n,\infty )$ and the empty set, corresponding to $\mathbb{N}\cup \{\infty \}$ in its usual well-order.

Induct on $r$. For an upward-closed $U\subseteq {\mathbb{N}}^r$, its slices $U_k=\{v\in {\mathbb{N}}^{r-1}:(v,k)\in U\}$ increase with $k$. Their union is upward closed and has finitely many minimal elements by the Dickson lemma; all those elements have appeared by some finite slice. Thus the slices eventually stabilize. Encode $U$ by the finite word of its pre-stabilization slices and its final stable slice. By the induction hypothesis, the slice order given by reverse inclusion is a well-quasi-ordering. The Higman lemma and finite product closure of well-quasi-orderings make these word-and-tail encodings well-quasi-ordered.

For a good pair of encodings $U,V$, an increasing subsequence map $f$ satisfies $U_k\supseteq V_{f(k)}$ at every pre-stabilization position of $U$, and the final slice of $U$ contains the final slice of $V$. Since $f(k)\ge k$ and the $V$ slices increase, $U_k\supseteq V_k$ before stabilization. Afterwards the final-slice comparison also gives $U_k\supseteq V_k$. Hence $U\supseteq V$, proving the induction. The use of Higman lemma is essential: finite-subset reverse domination does not preserve an arbitrary well-quasi-order, as the Rado order shows.

Given any infinite sequence of incline elements, choose a finite monomial support $A_i$ for each. The result just proved gives $i<j$ with $U_{A_i}\supseteq U_{A_j}$, hence $x_i\ge x_j$. Every finitely generated incline is therefore well-quasi-ordered by its reversed natural order.

Distributivity makes multiplication order-preserving for the natural order: if $u+v=v$, then $xu+xv=x(u+v)=xv$, so $xu\le xv$. It also expands every generated expression into a finite join of monomials, as used in solution.

Idempotence gives the join order $x\le y⟺x+y=y$. Reflexivity follows from $x+x=x$; antisymmetry follows from commutativity; if $x+y=y$ and $y+z=z$, associativity gives $x+z=x+(y+z)=(x+y)+z=z$. Thus it is a partial order.

Absorption says $xy\le x$; commutativity also gives $xy\le y$. Iterating this inequality shows that a monomial with larger exponents is smaller in the natural order. This is the link from exponent vectors to the reverse-inclusion well-quasi-ordering of monomial ideals in solution.

Interpret the assertion in the usual well-founded, class-theoretic version of Zermelo set theory, including foundation, class comprehension and separation with class parameters. Classes are not extra sets. The axiom of limitation of size, in the form used here, says that every proper class is in bijection with the universe $V$.

First derive replacement. Let a functional class relation map a set $a$ onto its image class $B$. If $B$ were proper, the limitation axiom would give a bijection $h:B\to V$. Its composite with the original map would be a surjection $g:a\to V$. Class-parameter separation formsSurjectivity gives $d\in a$ with $g(d)=D$, whence $d\in D$ iff $d\notin D$, a contradiction. Thus $B$ is a set, proving each instance of replacement. The argument also gives class replacement when the functional class is a parameter.

The class $\mathrm{On}$ of ordinals is proper: were it a set, its union and successor would be ordinals larger than every ordinal in it. Limitation gives a bijection $e:\mathrm{On}\to V$. Ordering $V$ by the ordinal indices of $e$ gives a global well-order; each nonempty set has a member with least index. Choosing that member defines global choice.

Conversely assume replacement and global choice. Ordinary choice well-orders each rank segment, and global choice selects such a well-order uniformly, since the collection of well-orders of each fixed rank segment is a nonempty set. Order all sets first by their rank of a set and then by the selected order within that rank. The resulting global order is set-like: the predecessors of any element are contained in a rank segment and form a set. Restrict it to a proper class $A$. By transfinite recursion, enumerate $A$ in this order. It cannot be exhausted at a set ordinal, since replacement would then make $A$ a set. Every member appears, because its predecessors form a set, whose well-order has an ordinal order type. Hence $A$ has order type $\mathrm{On}$. The same applies to $V$, and composing the two enumerations gives a bijection $A\cong V$. Thus limitation of size is equivalent to replacement plus global choice in this class-theoretic setting.

The Fodor lemma, also called Fodor's theorem, states: if $\kappa$ is a regular uncountable cardinal, $S\subseteq \kappa$ is stationary and $f:S\to \kappa$ is regressive, meaning $f(\alpha )<\alpha$ for every nonzero $\alpha \in S$, then some fibre $f^{-1}(\{\xi \})$ is stationary.

Delete zero from $S$, which preserves stationarity. Suppose no fibre is stationary. For each $\xi <\kappa$, choose a club set $C_{\xi }$ avoiding that fibre. The diagonal intersectionis a club. To prove unboundedness, start above an arbitrary bound and choose a strictly increasing sequence ${\alpha }_n$ with ${\alpha }_{n+1}$ in every $C_{\xi }$ for $\xi \le {\alpha }_n$. The intersection of these fewer-than-$\kappa$ clubs is club by club filter completeness. Put $\alpha ={\sup }_n{\alpha }_n<\kappa$. For any $\xi <\alpha$, every sufficiently late ${\alpha }_n$ lies in $C_{\xi }$, so its closure gives $\alpha \in C_{\xi }$. Thus $\alpha \in C$. For closure of $C$, let $\alpha <\kappa$ be a limit point of $C$; for each $\xi <\alpha$, the members of $C$ above $\xi$ witnessing that limit lie in $C_{\xi }$, and closure gives $\alpha \in C_{\xi }$.

Stationarity supplies $\alpha \in S\cap C$. Since $f(\alpha )<\alpha$, we have $\alpha \in C_{f(\alpha )}$, but that club was chosen to avoid the fibre containing $\alpha$. This contradiction proves the theorem. For completeness, club filter completeness follows by a similar diagonal sequence: cycle through fewer than $\kappa$ clubs over $\omega$ rounds, each time choosing a larger member of the next club. Regularity keeps the supremum below $\kappa$, and every club is visited cofinally often in the construction, so its closure contains the supremum. Their intersection is also closed.

Put $\mu =\mathrm{cf}(\lambda )$ and choose an increasing cofinal sequence of infinite cardinals $⟨{\lambda }_i:i<\mu ⟩$ below $\lambda$. Since $\lambda$ is a strong limit cardinal, $2^{{\lambda }_i}<\lambda$ for every $i$. Encode a subset $A\subseteq \lambda$ by its restrictions $⟨A\cap {\lambda }_i:i<\mu ⟩$. Cofinality makes this encoding injective, givingThe second inequality chooses an injection of each restriction set into $\lambda$. Conversely,since $\mu \le \lambda$ and an infinite cardinal satisfies $\lambda \cdot \mu =\lambda$. The two inequalities prove the singular strong limit power-set identityThis does not assume the singular cardinals hypothesis or determine either side as ${\lambda }^{+}$. The strong-limit assumption is what bounds each restricted power set.

Use ZFC and infinite input sets, the usual scope of the stated claim. For a finite set of size $n$, its Hartogs number is $n+1$, which is a finite successor cardinal rather than an aleph. Without the axiom of choice, one cannot silently identify every infinite input with an aleph, and the asserted conclusion needs those hypotheses.

The Hartogs number $h(X)$ is the least ordinal that does not inject into $X$. It is an initial ordinal: if it were equinumerous with a smaller ordinal $\alpha <h(X)$, composing that bijection with an injection $\alpha \to X$ would contradict its definition. With choice, well-order an infinite $X$ and put $|X|=\kappa ={\aleph }_{\eta }$. Every ordinal below ${\kappa }^{+}$ has cardinal at most $\kappa$ and injects into $X$, whereas ${\kappa }^{+}$ does not. Hence the Hartogs numbers under choice satisfyTo prove regularity, suppose $\mathrm{cf}({\kappa }^{+})=\mu <{\kappa }^{+}$. Since ${\kappa }^{+}$ is a successor cardinal, $\mu \le \kappa$. Choose a cofinal sequence $⟨{\alpha }_i:i<\mu ⟩$ below ${\kappa }^{+}$. Each ${\alpha }_i$ has cardinal at most $\kappa$, and choice givesBut cofinality makes this union all of ${\kappa }^{+}$, a contradiction. Therefore $\mathrm{cf}({\kappa }^{+})={\kappa }^{+}$, and every infinite-input Hartogs value is a regular initial successor aleph. Conversely every successor aleph occurs by taking $X$ to be its predecessor cardinal.