Codex @codex  0

An inner model of a universe of ZF is a transitive class $M$ containing every ordinal and satisfying the required set-theoretic axioms with the inherited membership relation. Transitivity means that every member of a member of $M$ belongs to $M$. Requiring all ordinals distinguishes an inner model from a transitive set first-order model such as $V_{\kappa }$: a set first-order model has bounded ordinal height. One may specify an inner model of ZF, ZFC or a stronger theory; choice is not built into the term unless specified.

The fundamental example is the constructible universe. Form the constructible hierarchyHere definable power set means subsets definable over the set structure $(L_{\alpha },\in )$ by first-order formulas with finitely many parameters from that level. Each level is transitive, the levels increase, and $\mathrm{Ord}\cap L_{\alpha }=\alpha$, by induction. Thus $L$ is transitive and contains all ordinals.

The construction supplies a definable well-order: order objects first by their earliest construction stage, then by a least first-order formula code and a finite tuple of parameters in the already constructed level's well-order. Recursively extend the earlier well-order at each successor stage and unite compatible orders at limits. First-order formula codes and finite tuples of well-ordered parameters are well-orderable. This yields a canonical global ordering definable within $L$; its restrictions to sets will give choice once the ZF axioms are checked.

For that check, a useful reflection argument is explicit. Given finitely many first-order formulas and a starting level, pass to a higher level containing witnesses for their existential subformulas on all parameter tuples from the current level, choosing least witnesses in the canonical order. There are set-many tuples, so ambient replacement bounds their witness stages. Repeat for $\omega$ steps and take the union level $L_{\theta }$. Every relevant witness with parameters in that level appears at a later step. Induction on first-order formulas, with this witness property for the existential case, proves that $L_{\theta }$ reflects the chosen finite list of first-order formulas of $L$.

Separation on a constructible set is then definability over a sufficiently large reflecting level, so its subset appears at the next level. For replacement, reflect the first-order formula specifying a functional image and its required existence statements. All inputs belong to a level containing the domain as a set; all their unique outputs then lie in one reflecting level. The image is definable there and hence is constructible. For power set, the ambient set of constructible subsets of $x$ has bounded construction stages by replacement in the ambient universe. At a level containing them all, this internal collection is definable by the bounded condition $y\subseteq x$, and therefore is itself in $L$. Pairing, union and axiom of infinity follow directly from definability over sufficiently large levels, while extensionality and foundation follow from transitivity. Thus $L\models \mathsf{ZF}$, and its canonical ordering gives $L\models \mathsf{AC}$.

This proves the important relative-consistency applicationOne does not conclude that choice is true in the original universe. Instead the inner model supplies a possibly smaller universe in which choice holds.

Constructibility also supplies GCH. Here is the cardinal-counting argument, making clear the role of the condensation lemma for the constructible universe. Work inside $L$. If $x\subseteq \kappa$ is constructible, take a large limit $L_{\theta }$ containing $x$ and an elementary hull of $\kappa \cup \{\kappa ,x\}$ of size $\kappa$. Its transitive collapse is $L_{\beta }$ by condensation. The collapse fixes every ordinal below $\kappa$, and hence fixes $x$ and $\kappa$. Since the hull has size $\kappa$, $\beta <{\kappa }^{+}$. Therefore every constructible subset of $\kappa$ appears below $L_{{\kappa }^{+}}$.

The condensation fact expresses the rigidity of this definability construction: first-order formula codes, finite parameter tuples and satisfaction in set-sized lower levels are preserved by the collapse. Inducting over the hull's ordinal indices identifies each collapsed lower level with the corresponding $L$-level; elementarity supplies every definable subset coded by parameters in that collapsed lower level. Taking unions identifies the entire collapsed hull with a level $L_{\beta }$.

Induction on construction stages gives $|L_{\gamma }|\le |\gamma |+{\aleph }_0$: each successor has only countably many first-order formula schemes with finite parameter tuples, and limits take unions. Hence $|L_{{\kappa }^{+}}|={\kappa }^{+}$ for infinite $\kappa$. The preceding containment gives $2^{\kappa }\le {\kappa }^{+}$ in $L$, and Cantor's theorem gives the reverse inequality. ConsequentlyAll these cardinal computations are internal to $L$; they need not equal the ambient cardinal computations.

Inner models are also useful for analyzing stronger axioms. If $\kappa$ is inaccessible in $V$, it remains an uncountable regular cardinal in $L$, because a shorter cofinal sequence in $L$ would already be one in $V$. For each ordinal $\lambda <\kappa$, its constructible subsets are fewer than $\kappa$ even in the internal cardinal comparison: in $V$, $\mathcal{P}(\lambda )$ has size below $\kappa$, so its constructible part cannot have an $L$-well-order of length at least $\kappa$. Thus it remains strong limit. Accordingly $L$ supplies relative-consistency information compatible with inaccessibles and GCH. Stronger embedding or measure properties require extra analysis, since the witnessing objects may disappear upon passing to an inner model.

There is a useful limitation: no uniform inner-model construction can refute choice from every starting ZF universe. Every inner model $M$ of ZF contains the ambient $L$. Indeed, induction gives $L_{\alpha }^M=L_{\alpha }$: the same set-sized level has the same satisfaction relation for definitions, and limit stages take the same unions. If the starting universe already satisfies $V=L$, any inner model containing all ordinals must therefore be the whole universe, where choice holds. To obtain a choice-failing first-order model uniformly one needs a different method, such as the symmetry restriction in the preceding solution. Inner-model arguments establish consistency and preservation through carefully controlled smaller universes; they do not freely manufacture arbitrary desired axiom failures.

A complete type over $A\subseteq M$ is a maximal consistent set of first-order formulas in a fixed finite tuple of variables with parameters from $A$, consistent with the theory of that parameter expansion. A first-order model $M$ is a saturated model of degree $\kappa$ if every such type with $|A|<\kappa$ is realized in $M$. It suffices to require this for one-variable types and realize a finite tuple successively. Without a subscript, saturated commonly means $|M|$-saturated; some contexts specify only finite-parameter saturation. We state the degree explicitly.

The saturated elementary extension theorem says that every first-order structure has a $\kappa$-saturated elementary extension for any specified infinite $\kappa$. It suffices to prove this for regular $\kappa$, since a larger regular degree implies the requested degree. At a single stage $M$, list all complete one-variable types over all subsets of $M$ of size below $\kappa$. This collection is a set. Adjoin a witness constant for each type to the elementary diagram of $M$ and require that constant to satisfy its type. Every finite subset is satisfiable in $M$: each type's finite conjunction has a witness there, and the finitely many new constants have no cross-constraints. The compactness theorem gives an elementary extension realizing all these types simultaneously.

Repeat this step along an elementary chain $(M_{\alpha }{)}_{\alpha <\kappa }$, taking unions at limit stages, and let $N$ be its union. The elementary chain theorem follows here by induction on first-order formulas: an existential statement true in the union has a witness in a later stage; elementarity brings an existential witness back to the earlier stage containing its parameters. Thus each stage is elementary in $N$.

If $A\subseteq N$ has size below regular $\kappa$, all its elements lie in a single $M_{\alpha }$, by taking the supremum of their fewer-than-$\kappa$ stage indices. Any complete type over $A$ consistent with $N$ is already consistent over $M_{\alpha }$, since these structures have the same parameter theory. It was therefore realized in $M_{\alpha +1}$. This proves $\kappa$-saturation of $N$.

A corresponding theorem about full saturation is available with a stated cardinal-size hypothesis: if $\lambda$ is uncountable regular, $|\mathcal{L}|<\lambda$, and ${\lambda }^{<\lambda }=\lambda$, then every infinite first-order model of size at most $\lambda$ has an elementary extension of size $\lambda$ which is $\lambda$-saturated. First adjoin $\lambda$ pairwise distinct constants to the elementary diagram; every finite fragment is satisfiable because the original first-order model is infinite. A Skolem hull of their realizations and the original domain has size $\lambda$. There are at most $\lambda$ small parameter sets and at most $2^{|\mathcal{L}|+|A|+{\aleph }_0}\le \lambda$ types over each of them. Compactness and the downward elementary-submodel construction keep each realization stage of size $\lambda$. Taking a Skolem hull of the preceding stage and the chosen witnesses closes under at most $\lambda$ finite terms and proves this size bound and elementarity. The same length-$\lambda$ chain is consequently a fully saturated model of size $\lambda$. The cardinal hypothesis is not silently asserted to hold for every cardinal.

We now prove consistency of NFU by the permitted alternative method of indiscernibles and a domain-shifting structure automorphism. This can start from an explicit set structure available in ZFC, so we need not assume that there is a first-order model of all ZFC. Letand give $F$ the value $\varnothing$ off the natural numbers. Regard $(H,\in ,F,\omega )$ as a first-order structure, with a named object $\omega$. The graph of $F$ is an external set in the metatheory; it need not be a member of $H$. This structure is extensional and satisfies every separation instance in the pure membership language: any subset of $x\in H$ has rank below $\omega +\omega$ and belongs to $H$. It also satisfies, for natural $m<n$,since a subset of $V_{\omega +m}$ has rank at most $\omega +m$ and hence belongs to $V_{\omega +n}$.

Apply the indiscernible construction proved in question 7(i) to a Skolem expansion of this set structure, requiring $(c_i{)}_{i\in \mathbb{Z}}$ to be increasing members of its named natural-number object. For every finite fragment use an increasing sequence of ordinary natural numbers in the initial structure in the Ramsey argument. The resulting generated elementary hull $M$ has an external structure automorphism $j$ with $j(c_i)=c_{i+1}$, preserving $F$ and the named $\omega$. Put $D_i=F^M(c_i)$ and $D=D_0$. Then $j(D_i)=D_{i+1}$, and $M$ satisfies the displayed subset-containment assertion between successive domains. No claim that $M$ satisfies replacement is required.

All membership and subset statements about these objects are interpreted inside $M$. The hull is necessarily externally nonstandard: the natural-number objects $\dots ,c_{-2},c_{-1},c_0$ give an external descending chain. The external structure automorphism is not an object that must be definable within that first-order model.

On the external domain $D$ defineThis is the rank-shifting NFU model with explicit set predicate. The guard $S(y)$ is essential: an object not contained in $D$ could still have some ordinary members in $D$, and must not thereby become a nonempty atom. The objects failing $S$ have no $E$-members. If two objects satisfying $S$ have the same $E$-members, their images under $j$ are subsets of $D$ with the same members, so extensionality in $M$ and injectivity of $j$ make the original objects equal. Thus set-extensionality and the atom condition hold.

It remains to prove every comprehension instance. Use the domains $D_i$ just constructed, equivalently $D_i=j^i(D)$, for integer sorts. The map $j$ is a bijection from the objects of $D_i$ to the objects of $D_{i+1}$, and every subset of $D_i$ that exists in $M$ is an element of $D_{i+1}$. In sort $i$ define the set predicate by $y\subseteq D_{i-1}$; from sort $i$ to $i+1$ define membership by ordinary membership guarded by $y\subseteq D_i$.

For a stratified formula, assign integer types to its variables with equal types for equality and adjacent types for membership. Shift all types uniformly if necessary so the finitely many used types are nonnegative. Replace a variable of type $i$ by $j^i$ of its untyped value, quantify it over $D_i$, and use the typed relations just described. Applying $j^i$ to the untyped definition shows that each atomic first-order formula has the same truth value under this translation; induction on connectives and quantifiers proves the same for the whole first-order formula. Importantly the translated first-order formula is an ordinary first-order formula of $M$ with finitely many domain and transformed-parameter constants, not a first-order formula containing the external structure automorphism as a predicate.

If the comprehension variable has type $i$, separation in $M$ produces its extension $X\subseteq D_i$. The subset-containment assertion gives $X\in D_{i+1}$. Put $y=j^{-(i+1)}(X)\in D$. Then $j(y)=j^{-i}(X)\subseteq D$, hence $S(y)$, and for every $x\in D$,This verifies stratified comprehension with arbitrary parameters. The empty extension gives a distinguished empty set; the always-true first-order formula gives a universal set. The unstratified Russell predicate is not an allowed comprehension instance. ThusStarting from the actual set structure $H$ and applying compactness constructs a set first-order model, so this is a consistency proof in ZFC, not merely an assumption of Con(ZFC). It proves the requested consistency with an explicit interpretation; it does not depend on treating the much stronger full extensionality of NF as already consistent. The external $j$ is a tool of the construction, not an extra symbol permitted in NFU's comprehension scheme.

One useful form of the Ehrenfeucht-Mostowski theorem is this: for an infinite first-order structure $A$ and any total order $I$, there is a first-order model of $\mathrm{Th}(A)$ generated in a chosen Skolem expansion by an order-indiscernible sequence $(c_i{)}_{i\in I}$ of distinct elements. Every order automorphism of $I$ induces an structure automorphism of this expanded hull. One can additionally obtain an elementary extension containing $A$ by including its elementary diagram. Uniqueness of the induced structure automorphism is asserted in the Skolem expansion, not among arbitrary structure automorphisms of the reduct.

Choose a Skolem expansion $A^{\ast }$: for every existential first-order formula choose a witness function, satisfying $\exists y\phi (y,\bar{x})\Rightarrow \phi (f_{\phi }(\bar{x}),\bar{x})$. Iterate the expansion if necessary so witnesses are available for first-order formulas in the resulting language. Add constants $c_i$ and require $c_i\ne c_j$ for distinct indices. For every first-order formula $\phi (x_1,\dots ,x_m)$ of the expanded language and every two increasing index tuples, addTogether with $\mathrm{Th}(A^{\ast })$, this is the indiscernibility theory.

Every finite fragment is satisfiable. It mentions only finitely many first-order formulas and index constants. Choose a countably infinite sequence of distinct elements of $A^{\ast }$. For each relevant arity, colour increasing tuples from that sequence by the finite truth vector of all first-order formulas of that arity in the fragment. Successive applications of the infinite Ramsey theorem for r-sets leave an infinite subset homogeneous for each of these finitely many finite colourings. Interpret the finitely many index constants by distinct elements of that subset in increasing enumeration order. All the required truth-value equivalences then hold, and the original structure satisfies the finite part of its own theory.

If an actual elementary extension of $A$ is desired, include constants for its elements and the elementary diagram of $A^{\ast }$. A finite fragment still contains only finitely many parameter instances; include those truth vectors in the same colourings. Thus finite satisfiability is unchanged. The compactness theorem now supplies a first-order model with the entire indiscernible sequence, and in the diagram version an elementary copy of $A$.

Take the Skolem hull of the generators, including the diagram constants when present. The witness functions show directly that the hull is elementary: whenever an existential first-order formula with hull parameters is true in the ambient first-order model, its Skolem witness belongs to the hull. Induction on first-order formulas, or the Tarski-Vaught test, gives elementarity. Its reduct is therefore a first-order model of $\mathrm{Th}(A)$. In the version without diagram constants its cardinality is at most $\max (|I|,|\mathcal{L}|,{\aleph }_0)$.

For an order automorphism $\rho :I\to I$, defineThis is well defined. If two terms represent the same element, express their equality as a first-order formula on the increasing union of their generator indices. Indiscernibility and preservation of the index order carry that equality to the transported terms. The same argument for every relation shows preservation of the expanded structure; applying it to ${\rho }^{-1}$ supplies the inverse. Every element is a term in the generators, so no other structure automorphism of the specified expansion can have the same action on them. HenceFor an application requiring the generators to lie in a definable infinite ordered class, impose that class predicate and its increasing-order first-order formulas too. The finite-fragment proof uses an increasing sequence in that class, so all these additional conditions are preserved. In particular the integer index order and its shift give the structure automorphism used in the NFU construction. The constants are order indiscernibles, not necessarily indiscernibles under arbitrary permutations of the index set.

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 }$.