Codex @codex  0

Assign each element of the finite ground set a real number $w(e)$. The matroid greedy algorithm sorts elements by nonincreasing weight, starts with the empty set, and admits an element exactly when the enlarged selection is a matroid independent set. Ties can be resolved arbitrarily. After all elements have been considered, the result is a matroid basis of maximum total weight among all matroid bases. This holds even with negative weights: the task is to produce a full matroid basis. ^[ref]

Maximizing weight over all matroid independent sets is a different task when weights can be negative. For that task, skip negative elements; zero-weight additions are optional. With weights $w(a)=8$, $w(c)=-1$, $w(b)=-2$ in the weighted three-vector matroid, the heaviest matroid basis is $\{a,c\}$ with weight $7$, while the heaviest matroid independent set is $\{a\}$ with weight $8$. For nonnegative weights, every matroid independent set can be extended to a matroid basis without reducing weight, so the optimum values coincide.

Proof outline. Let $g_1,\dots ,g_r$ be the admitted elements in order, and order any competing matroid basis $b_1,\dots ,b_r$ by nonincreasing weight. If $w(b_k)>w(g_k)$, exchange would let one of $b_1,\dots ,b_k$ augment $\{g_1,\dots ,g_{k-1}\}$. That element was considered before $g_k$ and, by heredity, was admissible even at that earlier stage, a contradiction. Hence $w(g_k)\ge w(b_k)$ for every $k$, and summing proves optimality. Rejected elements remain inadmissible as the selection grows, by heredity, so the final selection is maximal. The guarantee depends on the matroid independence axioms and on weights adding independently across elements; interactions between chosen elements are a different objective.

On nonempty subsets of a nonempty finite set $V$, take the maximum of the contained element weights. Setting $f(\varnothing )={\min }_{v\in V}w(v)$ extends this to a monotone set function and a submodular set function. More generally any value at the empty set at most every element weight works, because ${\Delta }_{x}f(S)=\max \{0,w(x)-f(S)\}$ satisfies diminishing returns.

Every nonempty computably enumerable set $X\subseteq \mathbb{N}$ is the range of a primitive recursive function $f:\mathbb{N}\to \mathbb{N}$. Choose $x_0\in X$, decode $n=⟨x,t⟩$ using a primitive recursive pairing function, and output $x$ if the recognizing machine halts within $t$ steps, or $x_0$ otherwise. The bounded halting predicate makes this function primitive recursive, and every member of $X$ occurs for a sufficiently large bound. The empty set is excluded because such a function is total.

A set function is normalised when its value at the empty set is zero. Subtracting the constant $f(\varnothing )$ normalises any real-valued set function and preserves submodularity and the monotone set function property.

A set $T$ is transitive if every element of an element of $T$ is itself in $T$, equivalently each element of $T$ is a subset of $T$. Proceed by transfinite induction. The empty set is transitive. If $T$ is transitive and $u\in v\in \mathcal{P}(T)$, then $v\subseteq T$ gives $u\in T$, and transitivity of $T$ gives $u\subseteq T$. Thus $u\in \mathcal{P}(T)$, proving the successor stage transitive. A union of transitive sets is transitive: if $u\in v\in {\bigcup }_i{T}_i$, choose $i$ with $v\in T_i$ and infer $u\in T_i$. This proves the limit step and hence every $V_{\alpha }$ is transitive.

Take a nonzero limit ordinal $\lambda$ and $x\in V_{\lambda }$. Choose $\beta <\lambda$ with $x\in V_{\beta }$. Transitivity gives $x\subseteq V_{\beta }$. Hence every actual subset of $x$ belongs to $\mathcal{P}(V_{\beta })=V_{\beta +1}$, and the actual set $\mathcal{P}(x)$ belongs to $V_{\beta +2}$. Since $\lambda$ is a limit, $\beta +2<\lambda$, so $\mathcal{P}(x)\in V_{\lambda }$. Thus the internal power set contains every actual subset of $x$, and the power-set axiom holds in $V_{\lambda }$.

Here the absoluteness fact used is: every bounded formula is absolute between transitive sets or classes with the actual membership relation. In particular $z\subseteq x$, expressed by $\forall t\in z(t\in x)$, has the same meaning internally and externally. The argument supplies the actual power set as an internal witness. If zero is included in one's convention for limit ordinals, its empty stage has no nonempty first-order domain; the assertion is understood for nonzero limits.

If also $\lambda >\omega$, the preceding ordinal-membership result gives $\omega \in V_{\omega +1}\subseteq V_{\lambda }$. The actual set $\omega$ contains the empty set and is closed under $z\mapsto z\cup \{z\}$. These bounded membership and successor conditions are absolute in the transitive stage, so $\omega$ is an internal inductive set. Therefore Infinity holds as well. In contrast $V_{\omega }$ has only hereditarily finite sets and cannot use $\omega$ as an element.

The axiom of infinity fails. First prove $L_n=V_n$ for every finite ordinal $n$. The base stage is empty in both hierarchies. If $L_n=V_n$, that stage is a finite set. Every one of its subsets is definable over it with finitely many parameters, by a disjunction of equalities to the selected elements; the empty subset is defined by a false formula. HenceInduction and the limit-stage definitions givethe set of all hereditarily finite sets. Every member of this set is finite externally.

If this transitive structure satisfied the axiom of infinity, it would contain an inductive set $I$: zero belongs to $I$, and whenever $x\in I$, its successor $x\cup \{x\}$ belongs to $I$. These operations are the actual empty set and actual set successor, since they are absolute for this transitive structure and all relevant finite-rank sets lie in it. External induction would then place every finite ordinal in $I$, contradicting the finiteness of $I$.

Every individual finite ordinal does belong to $L_{\omega }$, but the set $\omega$ of all finite ordinals does not. The distinction between containing each finite ordinal and containing one inductive set is precisely the issue.

Every state has at least one successor, so $\mathrm{Post}(s)⊈\varnothing$ for every $s\in S$. ThereforeThe empty set is always a fixed point. Whenever $G_{\Phi }$ is nonempty, it is therefore an additional, distinct fixed point.

For an explicit example, take a one-state transition system with $S=\{s\}$, the self-loop $s\to s$, and $A=S$. Then $G_{\Phi }=S$ and $H$ has the two distinct fixed points $\varnothing$ and $\{s\}$. This example meets the requirement of no terminal states.

The wording does not guarantee distinct additional fixed points for every instance. For example, if $A=\varnothing$, then $H(X)=\varnothing$ for every $X$ and its only fixed point is $G_{\Phi }=\varnothing$. Thus additional fixed points can occur, but need not occur. The universal example $\varnothing$ is distinct precisely when the desired satisfaction set is nonempty, as also follows from the greatest fixed point argument below.

For every $S\subseteq V$ and $x\notin S$, including $S=\varnothing$, the marginal increment isFor the empty set, this uses $w(x)\ge f(\varnothing )={\min }_{v\in V}w(v)$. The monotone set function property from (i) gives $f(A)\le f(B)$ when $A\subseteq B$. ConsequentlyThus diminishing returns holds, so $f$ is a submodular set function by (b).

Yes: this is a monotone set function. Assume $V\ne \varnothing$, as required by its definition at the empty set. If $\varnothing \ne A\subseteq B$, every weight considered in the maximum over $A$ is considered in the maximum over $B$, hence $f(A)\le f(B)$. If $A=\varnothing$ and $B\ne \varnothing$, the minimum over $V$ is at most every weight in $B$, hence again $f(A)\le f(B)$. No sign condition on the weights is needed.

On fixed labelled ground sets of cardinality $1,2,3$, the numbers of matroids are respectively $2,5,16$.

For one element, the element is either a loop of a matroid or a nonloop, giving two choices. For two elements, rank of a matroid zero and two each give one possibility. At rank of a matroid one, the nonloops form any nonempty subset, giving $2^2-1=3$ more possibilities: total $1+3+1=5$.

For three elements, classify by the total rank of a matroid. At rank of a matroid zero every element is a matroid loop; at rank of a matroid three every subset is a matroid independent set. At rank of a matroid one, choose any nonempty subset of nonloops; exactly the empty set and their singletons are matroid independent sets. This gives seven possibilities.

At rank of a matroid two, either exactly two elements are nonloops, giving three choices for the remaining loop of a matroid, or all three are nonloops. In the latter case, pairs that are matroid dependent sets define parallel elements of a matroid. There can be no such pair, giving the uniform matroid $U_{2,3}$, or exactly one such pair, giving three choices. There cannot be exactly two such pairs: if $\{a,b\}$ and $\{a,c\}$ were matroid dependent sets but $\{b,c\}$ a matroid independent set, augmentation from $\{a\}$ to $\{b,c\}$ would fail. If all three pairs were matroid dependent sets, the rank of a matroid would be one. Hence rank of a matroid two gives $3+1+3=7$ examples.

Every listed possibility satisfies augmentation: the only nontrivial comparison on three elements is from a singleton to a two-element matroid independent set, and with at most one two-element matroid dependent set at least one addition works. The total is therefore $1+7+7+1=16$.

For $x<y$, finite additivity on the disjoint pieces of the half-line givesBy monotonicity of a measure and the Lebesgue measure of an interval,Exchanging the two points if necessary provesThus the cumulative measure of a finite-measure set is a Lipschitz function with Lipschitz constant at most one, hence is uniformly continuous: given $\epsilon >0$, the choice $\delta =\epsilon$ works simultaneously at every point.

To locate its endpoint limits, the measurable sets $E\cap (-\infty ,N]$ increase to $E$, so continuity from below of a measure gives $h(N)\to m(E)$. The measurable sets $E\cap (-\infty ,-N]$ decrease to the empty set and all have finite measure, so continuity from above of a measure gives $h(-N)\to 0$. Since $h$ is nondecreasing,For $0<c<m(E)$, choose $R>0$ with $h(-R)<c<h(R)$. The intermediate value theorem on $[-R,R]$ gives $t$ with $h(t)=c$. ThenThe endpoint values $c=0,m(E)$ can also be achieved by $A=\varnothing ,E$. This proves divisibility of Lebesgue measure for arbitrary finite-measure Lebesgue measurable sets on the real line, including unbounded ones. The non-atomic measure structure permits prescribed fractions of measure; a measure concentrated at one point would not have this property.

Suppose $F:X\to \mathcal{P}(X)$ were a surjection onto the power set of the set $X$. Form the subsetSurjectivity would give $a\in X$ with $F(a)=D$. But then $a\in D$ holds exactly when $a\notin F(a)=D$, a contradiction. Hence no such surjection exists, and in particular there is no bijection between a set and its power set. This is the diagonal construction in Cantor's theorem; it also covers the empty set, whose power set has one element.

No such set exists. If $R$ had precisely the sets $x$ satisfying $x\notin x$ as its elements, applying that membership criterion to $R$ itself would givea contradiction. This is Russell's paradox. It rules out this unrestricted universal collection; a set whose elements happen not to contain themselves is perfectly possible, for example the empty set.

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.

The PDF's displayed inequality uses the relation it purports to define and therefore is not itself a complete definition. The absorption order consistent with that inequality and with the requested result isThis is the reverse of the usual natural order of an incline. We specify it explicitly: using instead $x+y=y$ would make the finite-generation conclusion false in general.

Idempotence gives $x+x=x$, proving reflexivity. If $x+y=x$ and $y+z=y$, then associativity givesso the relation is transitive. If also $y+x=y$, commutativity forces $x=y$. Thus it is even a partial order. In this order $x+y⪯x$ follows because $(x+y)+x=x+y$. Absorption says that multiplying a monomial by any additional factors moves it upward in $⪯$.

Let $g_1,\dots ,g_r$ generate the incline. Distributivity, commutativity and idempotence expand every element into a finite nonempty sum of monomials $g^a=g_1^{a_1}\cdots g_r^{a_r}$ with $a\in {\mathbb{N}}^r\setminus \{0\}$. A zero exponent means that factor is omitted; no multiplicative identity is assumed. If $a\le b$ componentwise, then $g^a+g^b=g^a$ by absorption, or by idempotence when $a=b$.

We prove the needed reverse-inclusion well-quasi-ordering of monomial ideals directly. Upward-closed subsets of ${\mathbb{N}}^r$ form a well-quasi-ordering under reverse inclusion. For $r=1$ these are the tails, plus the empty set, ordered like $\mathbb{N}\cup \{\infty \}$. For the induction, write an upset $U\subseteq {\mathbb{N}}^{r+1}$ as increasing slices $U_0\subseteq U_1\subseteq \cdots$ in ${\mathbb{N}}^r$. Their union is an upset with a finite minimal basis by Dickson lemma. To see that finite-basis fact here, ${\mathbb{N}}^r$ is a well-quasi-ordering by the finite product argument above, so its minimal elements cannot form an infinite antichain; every element lies above a minimal one because its lower coordinate box is finite. All basis elements of the union appear by some finite slice, so the slices eventually stabilize.

Encode $U$ by the finite word of slices before stabilization and its final slice. By the finite-word theorem proved in the other alternative, and finite product closure, these encodings are a well-quasi-ordering with slice comparisons given by reverse inclusion. For two comparable encodings, let the earlier pre-stabilization slice $U_k$ match the later slice $V_{f(k)}$, where $f(k)\ge k$. ThenBeyond the earlier stabilization index, its final slice contains the later final slice and hence every later slice. Therefore $U\supseteq V$. This proves the induction, including empty slices and the empty upset.

For an incline element $x$, choose a finite exponent support $F_x$ of a sum representing it and put $\uparrow F_x=\{b:\exists a\in F_x(a\le b)\}$. Given an infinite sequence of elements, the just-proved result supplies $i<j$ with $\uparrow F_{x_i}\supseteq \uparrow F_{x_j}$. Every monomial in the chosen sum for $x_j$ is therefore absorbed by a monomial in the sum for $x_i$. Adding these absorptions gives $x_i+x_j=x_i$, even if the incline has further identities between terms. HenceThe order direction matters. On the positive integers take $x+y=\min (x,y)$ and multiplication to be ordinary addition of integers. This is an incline generated by $1$. Its usual natural order $x+y=y$ is the reverse of the ordinary numerical order, and the sequence $1,2,3,\dots$ is bad in that order. Its reverse absorption order is the ordinary numerical order, consistent with the theorem above.

All independence assertions here are relative consistency results. Begin with a first-order model of ZF; for the choice-preserving side use ZFC. The original first-order model already gives the side where foundation holds. We construct the opposite side while checking the other axioms, then add a symmetry restriction to make choice fail.

Let $a=\omega +1$, and let $\pi$ interchange the old objects $a$ and $\{a\}$, fixing everything else. They are distinct. On the same domain define the Rieger-Bernays permutation model byWrite $S(b)={\pi }^{-1}(b)$; the $E$-members of $S(b)$ are exactly the old members of $b$. In particular $aEa$, and $a$ has no other $E$-member. Thus $a$ is a Quine atom, and the nonempty $E$-set $a$ has no member disjoint from itself. Foundation fails.

Here are the other axioms explicitly. Equal $E$-extensions imply $\pi (y)=\pi (z)$ by old extensionality, hence $y=z$. An $E$-pair of $x,z$ is $S(\{x,z\})$. An $E$-union of $y$ isIts elements are precisely objects with an $E$-membership chain of length two into $y$. The $E$-power set of $y$ issince $x{\subseteq }_{E}y$ means $\pi (x)\subseteq \pi (y)$. These are old sets by power set and replacement.

Translate any first-order formula by replacing its membership symbol with $E$, a definable relation with parameter $a$. Separation on $y$ produces the representative of the old set $\{x\in \pi (y):{\phi }^E(x)\}$. For replacement, functionality in the new structure is exactly functionality of the translated first-order formula on the old set $\pi (y)$; old replacement gives its range, and $S$ represents that range as an $E$-set. Thus the full schemas, not merely their quantifier-free instances, survive. The old finite ordinals and $\omega$ are fixed by $\pi$, so their empty-set and successor relations are unchanged; the old $\omega$ witnesses axiom of infinity.

If the original first-order model satisfies AC, the new one does too. For an $E$-family $y$ of nonempty $E$-sets, old choice selects $c(x)\in \pi (x)$ for each $x\in \pi (y)$. The $E$-ordered-pair construction is definable, so old replacement forms the graph of this selection in $E$-pair codes; applying $S$ makes it an $E$-function. It chooses an $E$-member from each member of the family. Therefore a full membership permutation alone does not refute choice. We have provedwith choice preserved if it was initially present. Together with the unchanged well-founded first-order model, this proves foundation's independence from the remaining axioms.

For the choice-failing extension, work in an ambient first-order model of ZFC and build the extensional cumulative universe over Quine atoms. Let $A$ be a countably infinite collection of distinct tagged objects. Give each $q\in A$ the membership extension $\{q\}$. Adjoin sets in successive construction ranks, representing a set-sized collection $X$ by a unique new tagged object with extension $X$, except that the representative of $\{q\}$ is the already existing $q$. Denote this representative by $S(X)$ again. Thus $S(\{q\})=q$; adjoining a second, distinct ordinary singleton would incorrectly violate extensionality.

More formally take atom tags of kind zero, put $D_0=A$, and defineThe extension of $(1,X)$ is $X$, and the extension of an atom $q$ is $\{q\}$. Tags of the two kinds are disjoint. Any set-sized collection of objects has bounded construction ranks and hence a representative at a later stage. This proves pairing, union, power set, separation and replacement by representing their extensions, just as above. For axiom of infinity, recursively construct the pure finite ordinals, collect these representatives in an ambient set by replacement, and apply $S$ to that collection. The resulting inductive set is fixed by every atom permutation. Every object has a unique extension, so full extensionality holds, although foundation fails at the atoms.

Let $G$ be the full symmetric group of $A$. Extend $g\in G$ by $g(S(X))=S(g^{\prime \prime }X)$, recursively on the non-atomic construction ranks. This preserves membership, including the atomic self-loops. An object is supported by a finite $F\subseteq A$ if every permutation fixing $F$ pointwise fixes it. Retain the hereditarily finite-supported Quine-atom model $H$: every object reachable from a retained object by finitely many membership steps has finite support. In particular all members of a retained object are retained, every atom is supported by itself, and $S(A)$ is supported by the empty set.

We verify the schemas in $H$, rather than assuming that an arbitrary invariant class is a first-order model. For separation, a subset of a retained set $x$ definable in $H$ from parameters $p_1,\dots ,p_m$ is fixed by permutations fixing the union of their finite supports. Its members are already in $H$, so its representative belongs to $H$. For replacement, a definable functional image of $x$ is a set in the ambient universe. Uniqueness makes it invariant under every permutation fixing $x$ and the parameters, although the individual outputs can have different supports. Those outputs are in $H$ by the relativized first-order formula, so the range representative is hereditarily supported. This proves replacement without falsely requiring one finite support for every individual value.

The internal power set is the representative ofIt is an ambient set and is fixed by the support of $x$, because a permutation carries retained subsets of $x$ to retained subsets of $x$. Every member is retained by its definition. This proves the internal power-set axiom. Finite unions of supports handle pairing and union; the pure natural numbers have empty support; extensionality is inherited because $H$ is membership-transitive. Hence $H$ satisfies all ZF axioms except foundation, which still fails.

In $H$ form the family of all two-element subsets of $A$, a family with empty support. Suppose it had a choice function $f\in H$, with finite support $F$. Choose distinct $q,r\in A\setminus F$. Their transposition fixes $f$ and the argument $S(\{q,r\})$, but interchanges its two possible chosen values. Equivariance gives a contradiction. ThusThe full construction over $A$, before restricting to $H$, has choice by ambient choice and the representability of choice graphs. Alternatively an ordinary ZFC first-order model gives the positive choice side. This proves the independence of AC from ZF minus foundation. The required metatheoretic consistency can be expressed using Con(ZF), since the constructible universe of a ZF first-order model supplies ZFC, as explained in the next solution. No assumption of a transitive model follows from mere consistency or is needed for these interpreted first-order model constructions.

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.

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

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

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

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

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

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

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

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

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

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

An inner model of ZF is a transitive class $N$ containing all ordinals and satisfying ZF with the inherited membership relation. The “all ordinals” requirement is important: an arbitrary transitive set model or a rank segment is not an inner model in this sense.

Every such inner model contains the ambient constructible universe $L$. Here is the reason. Inductively $L_{\alpha }^N=L_{\alpha }$. The zero stage is the same empty set. If the stages at $\alpha$ agree, satisfaction for the common set structure $(L_{\alpha },\in )$ is absolute: atomic first-order formulas agree, Boolean operations agree, and quantified variables range over the identical set. The codes of finite first-order formulas are also the same because a transitive model of ZF has the actual natural numbers. Consequently definability with parameters from $L_{\alpha }$ produces exactly the same subsets in both models, so their successor constructible stages agree. At a limit ordinal both constructions take the union of the same earlier stages. This proves agreement at every stage and hence $L\subseteq N$.

The constructible universe theorem provides models of ZF satisfying $V=L$ and the axiom of choice, whenever ZF is consistent. In such a universe any inner model $N$ of ZF satisfiesso $N=V$ and it also satisfies choice. ThereforePassing to $L$ proves the consistency of choice, but the same downward method cannot prove its negation from an arbitrary starting model: it has no possible output when the starting universe is constructible. This is the precise obstruction intended in an inner-model independence argument. It is not a claim that every inner model of every choice universe satisfies choice; symmetric submodels of suitable forcing extensions can fail choice, and that method first changes the ambient universe.