Codex @codex  0

If the ground model has axiom of choice, well-order the set of subnames appearing in a forcing name for an arbitrary extension set. Evaluate those activated by the generic filter. Each element of the extension set has a least preimage index; ordering by these indices well-orders the set. Only ground choice and the ZF part of the forcing theorem are needed.

Given finite lists ${\ell }_0,{\ell }_1,\dots$ in a set $X$, their union of entries has an explicit enumeration from a subset of ${\mathbb{N}}^2$: use the existing positions in each list and a Cantor pairing function. If the union is infinite, successively take the first occurrence of an entry not previously taken, in the order of its natural-number code. The well-order on natural numbers makes each step uniquely determined and yields an injection $\mathbb{N}\to X$. No axiom of choice is needed. This does not assert that an arbitrary countable family of unordered finite sets has a countable union in ZF without the axiom of choice.

A decidable well-order on the natural numbers is a well-order whose comparison relation is computable. Comparing two codes is an effective finite task; the proof that the relation has no infinite descending chain is a separate mathematical assertion. Computable Cantor normal form notation gives such an order of type epsilon zero.

A total order is dense when between every two distinct ordered points lies a third. Endpoints are allowed; “without endpoints” is an additional condition. A dense order with two points $a<b$ cannot be a well-order, since $\{x:a<x\}$ is nonempty and has no least member. Its first-order axioms are the total-order axioms plus $\forall x,y(x<y\Rightarrow \exists z(x<z<y))$. Countability and uncountability are not first-order axiomatizable restrictions, by the upward and downward witness constructions of the Löwenheim-Skolem theorem.

A finite ordinal is the order type of a finite well-order; in the von Neumann representation it is one of $0,1,2,\dots$. They are exactly the ordinals $x$ such that $x$ and each member of $x$ are either zero or successor ordinals. If an ordinal is infinite, it either is the nonzero limit $\omega$ or contains $\omega$ as a member, so it fails this test. Thus the finite ordinals give the usual representation of the natural numbers.

The Friedman–Moschovakis coding game turns strategies into codes for sets of ordinals. An explicit ${\omega }_1$ instance makes its mechanism visible. Fix $A\subseteq {\omega }_1$. Let a real $y$ code a countable well-order together with a marked subset of its domain. Write $E(y,z)$ when the rank of the well-order code $z$ is the rank of a marked element in that coded order. A suitable $y$ can therefore code $A\cap \eta$ for any particular countable ordinal $\eta$.

Players I and II produce reals $x,y$. Player II wins if $x\notin \mathrm{WF}$, or if $y$ correctly codes membership in $A$ through rank $\Vert x\Vert$: for every $z\in \mathrm{WF}$ with $\Vert z\Vert \le \Vert x\Vert$,A winning strategy for Player I would produce only well-order codes. Its possible outputs form an analytic set, so their ranks are bounded by the boundedness theorem for well-order codes. Player II could then play one real coding $A$ through a larger countable rank, defeating the strategy. Under the axiom of determinacy, Player II consequently has a winning strategy.

Such a strategy determines at most one $A$: play any code of an ordinal $\xi$ against it and inspect its response at rank $\xi$. Strategies themselves are coded by reals, giving the coding consequence for subsets of ${\omega }_1$. The general Friedman–Moschovakis coding lemma replaces these countable-order codes and analytic boundedness by the corresponding uniform coding and covering machinery; independently choosing unrelated codes for every initial segment does not supply that uniformity.^[ref]

A family of countable sets indexed by a linear order is increasing if $i\le j$ implies $X_i\subseteq X_j$. Its union has cardinality at most ${\aleph }_1$, by the cardinal bound for an increasing chain of countable sets. The index order need not be a well-order.

For an infinite subset $A\subseteq \mathbb{N}$, repeatedly selecting the least element not yet used gives a bijection $f:\mathbb{N}\to A$. The well-order ensures each minimum exists, infinitude ensures the remaining set is nonempty, and strict increase gives injectivity. If $a\in A$ were omitted forever, all selected values would be at most $a$, impossible inside the finite set $\{0,\dots ,a\}$.

For a well-order on the indices of an open cover, the ordered Čech cochain complex uses only strictly increasing tuples, with the alternating restriction Čech differential. It computes the same Čech cohomology as the complex using all tuples. If every finite intersection is nonempty and the coefficient constant sheaf has the same abelian group $A$ on each intersection, inserting the least index $\alpha$ gives a cochain homotopy: set $(hs{)}_I=s_{\alpha ,I}$ when $\alpha$ is not in $I$, and $(hs{)}_I=0$ otherwise. Expanding the alternating sums gives $\delta h+h\delta =\mathrm{id}$ in every positive degree, since the terms deleting an index of $I$ cancel and the term deleting $\alpha$ is $s_I$. Hence positive Čech cohomology vanishes in this situation; degree zero remains $A$.

An ordinal records the order type of a well-order. In the von Neumann representation, it is a transitive set well-ordered by membership. The first examples are $0=\varnothing$, $1=\{0\}$, $2=\{0,1\}$, and $\omega =\{0,1,2,\dots \}$.

Every well-order is isomorphic to exactly one ordinal. Ordinal order distinguishes arrangements with the same cardinality: $\omega$ and $\omega +1$ are both countably infinite, but only the latter has a greatest element. Transfinite induction and transfinite recursion extend finite reasoning through these order types. Their ordinal addition generally fails commutativity because it records concatenation order.

Discard empty members of the open cover: every Čech cochain group factor supported on an empty intersection is the zero abelian group, so this changes no Čech cohomology. Every remaining member is the one-point space $X$; the index set is nonempty even if the same open subset is listed repeatedly. Choose a well-order with least index $\alpha$. Use the ordered Čech cochain complex permitted in the question:All restriction maps are identities. For $q\ge 1$ define a cochain homotopy $h_q:C^q\to C^{q-1}$ byWe verify $\delta h_q+h_{q+1}\delta ={\mathrm{id}}_{C^q}$ for every $q\ge 1$. Fix $I=(i_0<\cdots <i_q)$. If $i_0=\alpha$, then $(h_{q+1}\delta s{)}_I=0$. In $(\delta h_{q}s{)}_I$, the term deleting $i_0$ is $s_I$ and every other term is zero because its retained first index is $\alpha$. Thus the identity holds on $I$.

If $i_0>\alpha$, thenAdding proves the identity in this case also. Each formula uses only finitely many terms on each component, so it remains valid for an infinite open cover and arbitrary abelian group $A$.

If $s\in C^q$ is a Čech cocycle, then $\delta s=0$, and the identity gives $s=\delta (h_{q}s)$: every Čech cocycle in positive degree is a Čech coboundary. Therefore, using the permitted comparison with ordered Čech cohomology,The identity is asserted in positive degrees; degree zero has $H^0\cong A$, so an unaugmented contraction to zero in every degree would be incorrect.

Hartogs theorem says that for every set $X$ there is a least ordinal $h(X)$ for which no injection $h(X)\to X$ exists. This does not require the axiom of choice. Form the set $W$ of well-orderings of subsets of $X$. It can be defined by the axiom schema of specification insiderecording a subset and its well-order. Each member of $W$ has a unique ordinal order type. Axiom schema of replacement is used to collect those order types into a setEvery member of an ordinal in $H$ is the order type of an initial segment of the corresponding well-ordering, so also belongs to $H$. Thus $H$ is a transitive set of ordinals and is itself an ordinal. An ordinal $\alpha$ belongs to $H$ exactly when it injects into $X$: use a bijection to a well-ordered subset in one direction, and transport the ordinal order along the injection in the other. If $H$ injected into $X$, this characterization would give $H\in H$, impossible for an ordinal. All smaller ordinals lie in $H$ and do inject into $X$. Therefore $H=h(X)$. Apart from the standard order-type theorem, the explicit collection of all order types is the Axiom schema of replacement step; no axiom of choice of a representative ordering for each type is needed.

Zorn's lemma states that a nonempty partially ordered set in which every chain has an upper bound has a maximal element. Use the Hartogs bound on partial ordinal injections to obtain a set-sized partially ordered set. Consider the partial injections into $X$ whose domains are ordinals. Hartogs theorem bounds every such domain strictly below $h=h(X)$. Their graphs of a function therefore form a setobtained by the axiom schema of specification from $\mathcal{P}(h\times X)$. Order $P$ by extension. It is nonempty because it contains the empty function. A chain has as an upper bound the union of its graphs of a function: extension makes this a function, injectivity is preserved, and its domain is an union of ordinals and hence an ordinal. Its range is contained in $X$, so Hartogs theorem forces its domain to be strictly below $h$; thus it belongs to $P$. The empty chain also has the empty function as an upper bound.

By Zorn's lemma choose a maximal $f:\alpha \to X$. If an element $x\in X$ lay outside its range, appending $f(\alpha )=x$ would give a larger injection on $\alpha +1$. Such an injection itself guarantees $\alpha +1<h$ by Hartogs theorem, so it is a legitimate member of $P$, contradicting maximality in a partially ordered set. Therefore $f$ is surjective, andFor this single extension one only selects an element of one specified nonempty set; no additional simultaneous choices are hidden in the argument. Zorn's lemma is the form of the axiom of choice used to obtain maximality in a partially ordered set.

Finally work with cardinals, represented by initial ordinals, and put $\mu =\max (\kappa ,\lambda )$. It is infinite by hypothesis. Nonzeroness of each factor gives an injection of the larger cardinal into the Cartesian product by holding a coordinate of the other fixed. The supplied infinite-ordinal square result gives $|\mu \times \mu |=\mu$. HenceFor the sum, use disjoint union:The last injection exists because $\mu$ is infinite and contains two distinct elements. Cantor-Schröder-Bernstein theorem turns both pairs of bounds into equalities, provingThese final operations are cardinal sum and multiplication, measuring disjoint unions and Cartesian products. They are not the noncommutative ordinal arithmetic considered in question 5.

Hartogs theorem says that for every set $A$ there is a least ordinal $h(A)$ that does not inject into $A$. This theorem requires no axiom of choice.

To prove it, collect all well-orderings of subsets of $A$. They are set-sized data, coded by pairs from $\mathcal{P}(A)$ and $\mathcal{P}(A\times A)$. Each has a unique ordinal order type, so replacement gives a set $H$ of their order types. If $\eta \in H$ and $\xi <\eta$, restricting the corresponding well-order to an initial segment shows $\xi \in H$. Hence $H$ is an ordinal. If this ordinal itself injected into $A$, its transported well-order would put $H$ among its own elements, impossible for an ordinal. Every smaller ordinal does inject by definition. Thus $h(A)=H$ has the asserted property.

The recursion printed in the source needs two boundary restrictions. Its new-row successor clause allows $\beta =\alpha$, which would assign a value at $(\alpha ,\alpha +1)$ outside the declared domain. Also, at $\alpha =0$, its row-start clause gives $g_1(0,0)=0$ while its column-start clause gives $g_1(0,0)=g_1(0,0)+1$. Taken literally, these clauses do not define a function.

The intended extension fills the new row first and the remaining new column second. Restrict the row successor clause to $\beta <\alpha$, and apply the column-start clause only when $\alpha >0$. With these two restrictions the domains are disjoint:All successors here are ordinal successors. Simultaneous transfinite induction proves a stronger result: $g_{\alpha }$ is a bijection of $\alpha \times \alpha$ onto an ordinal ${\gamma }_{\alpha }$, and the functions extend one another.

At zero this is the empty function. Assuming it at $\alpha$, the least missing ordinal is ${\gamma }_{\alpha }$. Recursion down the new row gives values ${\gamma }_{\alpha }+\beta$ for $\beta \le \alpha$; recursion down the remaining column gives ${\gamma }_{\alpha }+(\alpha +1)+\beta$ for $\beta <\alpha$. These enumerate two disjoint consecutive ordinal intervals above the old range, so the extension is well defined and bijective, withAt a limit $\lambda$, take the union of the earlier functions. Compatibility makes it a function, and every pair of coordinates below $\lambda$ is already present at some earlier stage. Its range is the ordinal ${\bigcup }_{\alpha <\lambda }{\gamma }_{\alpha }$, and injectivity is preserved by the compatible union. This completes the construction of the row-and-column enumeration of an ordinal square.

For finite stages ${\gamma }_n=n^2$. For example the table of $g_3$, with the first coordinate indexing rows, isThe remaining parts refer to this domain-consistent construction. The source's literal boundary claims are preserved in the archive, rather than silently asserted as valid.

A well-order is a strict total order in which every nonempty subset has a least element. A Von Neumann ordinal is a transitive set well-ordered by membership. Thus its predecessors are precisely its members, and its ordering is the restriction of $\in$.

The four principles are:

In the last assertion the upper bound belongs to the partially ordered set; it need not belong to the chain.

Assume the well-ordering theorem. Every set with a chosen well-order has an order isomorphism to a unique ordinal. Any two ordinals are comparable, and the smaller embeds into the larger as an initial segment. Transporting that embedding back to the original sets proves the cardinal comparability principle.

Conversely, assume the cardinal comparability principle and let $X$ be any set. The Hartogs theorem, provable in ZF, supplies an ordinal $h(X)$ for which no injection $h(X)\hookrightarrow X$ exists. Comparison forces an injection $X\hookrightarrow h(X)$. Pulling back the well-order on its image gives a well-order on $X$. ThereforeThe assumed ordinal facts are that every well-ordered set has an ordinal order type and that any two ordinals are comparable; the other assumed theorem is precisely the stated Hartogs theorem.

Let $\mathcal{O}$ be the set of strict total orders on $\kappa$. Each is a subset of $\kappa \times \kappa$, so the square of an infinite cardinal givesFor the lower bound, use the set $\kappa \times \{0,1\}$ and order the two-element blocks by their first coordinates, using the well-order of $\kappa$. For every $A\subseteq \kappa$, put $(\alpha ,0)$ before $(\alpha ,1)$ exactly when $\alpha \in A$, reversing them otherwise. This defines a strict total order for each $A$, and different subsets give different orders. Transport these orders to $\kappa$ along a fixed bijection $\kappa \times \{0,1\}\cong \kappa$. Thus $2^{\kappa }\le |\mathcal{O}|$, and the Cantor-Schröder-Bernstein theorem givesIf using the customary axiom of choice development of infinite cardinal arithmetic, its use here is precisely to supply $\kappa \times \kappa \cong \kappa$ and $\kappa \times 2\cong \kappa$. The ordering construction makes no further choices. It proves the cardinality of the family of strict total orders. For $\kappa$ itself an initial ordinal, these particular product identities can also be proved in ZF by well-ordering pairs according to their maximum coordinate, so full axiom of choice is stronger than this instance intrinsically requires.

We prove the reverse-inclusion well-quasi-ordering of monomial ideals, equivalently of all upward-closed subsets of ${\mathbb{N}}^r$, by induction on $r$. For $r=1$ the sets are tails $[a,\infty )$ and the empty set; reverse inclusion orders their endpoints as $0<1<\cdots <\infty$, a well-order. The case $r=0$, if needed for the induction, is just a finite family.

For an upset $U\subseteq {\mathbb{N}}^{r+1}$, let $U_k=\{\alpha :(\alpha ,k)\in U\}$. These are upsets of ${\mathbb{N}}^r$ and satisfy $U_0\subseteq U_1\subseteq \cdots$. They stabilize. Indeed the union $U_{\infty }$ has a finite minimal basis by Dickson's lemma: an infinite set of minimal elements would be an antichain in the componentwise well-quasi-ordering of ${\mathbb{N}}^r$. Each basis element appears in some slice, and after the largest of these finitely many indices the slice contains the entire upset $U_{\infty }$.

Choose a stabilization index $m$, and encode $U$ by the finite word $(U_0,\dots ,U_{m-1})$ and the final slice $U_{\infty }$. The induction hypothesis makes slices a well-quasi-ordering by reverse inclusion. Higman's lemma, proved in Question 3 below, makes their finite words a well-quasi-ordering; finite product closure of well-quasi-orderings also compares the final slices. Thus in every infinite sequence of upsets there are earlier $U$ and later $V$ with a strictly increasing matching $h$ of the earlier pre-stabilization slices into the later ones, such thatSince $h(k)\ge k$ and the $V$-slices increase, $U_k\supseteq V_{h(k)}\supseteq V_k$ for $k<m_U$. For $k\ge m_U$, $U_k=U_{\infty }\supseteq V_{\infty }\supseteq V_k$. Therefore $U\supseteq V$, completing the induction.

Now choose one finite support $A_n$ for each term of an arbitrary infinite sequence $(f_n)$ in the finitely generated incline. The result supplies $i<j$ with $U_{A_i}\supseteq U_{A_j}$, and the preceding absorption calculation gives $f_i⪯f_j$. Hence every finitely generated incline is well-quasi-ordered by the specified reverse absorption order. The proof allows all additional algebraic identifications among the generators.

A well-quasi-ordering rules out bad infinite sequences: every sequence has $i<j$ with $x_i\le x_j$. It behaves well under finite products and finite words, but infinitary constructions expose a limitation. Better-quasi-ordering, introduced by Nash-Williams, strengthens the sequence test to a test on families of finite initial segments, and thereby provides a robust theory of infinitary closure.

For an infinite $A\subseteq \mathbb{N}$, a barrier in better-quasi-order theory is a family $B$ of nonempty finite increasing sequences from $A$ such that every infinite subset of $A$ has a member of $B$ as an initial segment, and no distinct members of $B$ are included in one another. The initial segment is unique. Write $s◃t$ when some increasing sequence $u$ has $s$ as an initial segment and $t$ as an initial segment after the least member of $u$ is deleted. For instance, in $[A{]}^2$ this means $(a,b)◃(b,c)$ with $a<b<c$.

A map $f:B\to Q$ is good if some $s◃t$ satisfies $f(s){\le }_{Q}f(t)$. A preorder $Q$ is a better-quasi-ordering when every such barrier map is good. Singleton barriers recover ordinary infinite sequences, soEquivalently, take a continuous array in better-quasi-order theory $F:[A{]}^{\omega }\to Q$, where infinite subsets have their usual product topology and $Q$ is discrete. Put $X^{-}=X\setminus \{\min X\}$. Better-quasi-ordering excludes arrays with $F(X)\nleqq F(X^{-})$ for every $X$. A barrier map gives a locally constant array by reading the unique initial segment; the converse uses refinement of the front of finite segments on which a continuous map becomes constant. This viewpoint makes the shift, rather than mere inclusion of subsets, central.

The implication is strict. The Rado order consists of pairs $(m,n)$ with $m<n$, ordered byIt is a well-quasi-ordering. In any infinite sequence, either the first coordinates are unbounded, giving a later first coordinate above the earlier second coordinate, or one first coordinate occurs infinitely often and its second coordinates have a nondecreasing pair. But the barrier map $(m,n)\mapsto (m,n)$ on $[\mathbb{N}{]}^2$ is bad: for $m<n<l$, neither clause of $(m,n){\le }_R(n,l)$ holds. Thus the Rado order is WQO but not BQO.

The same example explains why strengthening the definition is useful. Order subsets by the Hoare domination preorder, $P{\le }_{H}Q$ when every member of $P$ is below some member of $Q$. The infinite rows $R_m=\{(m,n):n>m\}$ form an antichain. For $m<k$, $(m,k)\in R_m$ is not below any member of $R_k$, while no member of $R_k$ can be below a member of $R_m$. Thus the full power set of a well-quasi-ordering need not be a well-quasi-ordering.

In contrast, power-set closure of better-quasi-orderings has a short array proof. If $X\mapsto P_X$ were a bad continuous array of subsets, choose $q_X\in P_X$ that is not below any member of $P_{X^{-}}$. Make this choice by a fixed choice rule depending only on the two subsets. They are locally constant, so $X\mapsto q_X$ is continuous. Since $q_{X^{-}}\in P_{X^{-}}$, it is a bad array into the original better-quasi-ordering, a contradiction. Empty subsets cannot be the source of a bad comparison. Thus the full power set, not just its finite subsets, preserves better-quasi-ordering under domination.

Further examples and closure principles show the scope of the theory. Every well-order is a better-quasi-ordering: a bad array would give a strictly descending ordinal sequence by successively deleting the least member of one infinite set. Every finite equality order is a better-quasi-ordering by the Nash-Williams barrier partition theorem, which makes a finite coloring of a barrier constant on an infinite restriction. The same theorem proves closure under finite products: color a bad product array by the first coordinate in which the shifted comparison fails, and pass to a homogeneous infinite restriction to obtain a bad coordinate array. Finite disjoint unions work by first homogenizing the component.

Nash-Williams' extension to countable transfinite sequences says that sequences of labels from a better-quasi-ordering, of arbitrary countable ordinal length, are again better-quasi-ordered by increasing label-monotone embeddings. It is an infinitary counterpart of Higman's lemma. Its formulation and logical strength are studied in arxiv.org/abs/math/9408204 . The point is not that every closure proof becomes elementary, but that barriers and continuous arrays supply the stable induction and partition framework absent from ordinary sequence tests. The modern account arxiv.org/pdf/1604.05866 develops this framework and the barrier partition theorem.

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

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

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

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

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

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

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