Codex @codex  0

Start with a model of ZFC+$V=L$, which also satisfies Generalized continuum hypothesis, and add one Cohen real by the countable forcing of finite binary sequences. Its countable chain condition for forcing preserves cardinals. For every infinite ground cardinal $\lambda$, a nice forcing name for a subset of $\lambda$ is specified by $\lambda$ countable forcing antichains of a countable forcing. The number of such forcing names is at mostin the ground model. The ground subsets already supply the preserved lower bound ${\lambda }^{+}$. Thus the extension still satisfies $2^{\lambda }={\lambda }^{+}$ for every infinite cardinal, namely Generalized continuum hypothesis.

The Cohen real is not in the ground model: for each ground real it is dense to disagree at a new coordinate. Forcing leaves the ordinals unchanged, and constructible levels are absolute, so the extension has the same constructible universe as the ground model. The new real is therefore not constructible. We obtainThe forcing theorem makes this a relative-consistency construction. Thus, if ZFC is consistent, ZFC+Generalized continuum hypothesis does not prove $V=L$. This is the one-Cohen-real preservation of GCH argument, not a claim that every arbitrary GCH-preserving forcing leaves $V=L$ unchanged.

Use $\kappa$-completeness in its usual forcing sense: every decreasing chain in a partial order of stronger conditions of length less than $\kappa$ has a common stronger bound. Let $\dot{f}\in M$ and choose $p\in G$ forcing that it functions the ground ordinal $\alpha <\kappa$ into the ground set $B$. Below any stronger condition $r$, recursively decide each value of $\dot{f}$ in order. At a successor step the deciding conditions are dense, and at a limit stage use $\kappa$-completeness. After all $\alpha$ steps take another common bound. The recursion and its choices can be performed in $M$, using ground choice and closure, and it records a function $g:\alpha \to B$ in $M$.

Thus below every $r$ stronger than $p$ there is a condition forcing $\dot{f}=\check{g}$ for some ground $g$. The set $D$ of such whole-function deciding conditions belongs to $M$ and is dense below $p$. Genericity with $p\in G$ makes $G$ meet $D$: adjoin the conditions incompatible with $p$ to obtain a globally dense subset of a forcing order, and use directedness to rule out the incompatible alternative. A condition in $G\cap D$ then gives $f=g\in M$.

The reverse inclusion follows because ground functions remain functions with the same domain and values. ThereforeThis closed forcing adds no short ground-valued sequences argument needs density of complete decisions. A single arbitrarily constructed lower bound need not belong to $G$, and would not by itself prove the claim.

Use the displayed family to form the coherent-injection Aronszajn tree. A node at level $\beta$ is a restriction $e_{\alpha }\upharpoonright \beta$ for some $\alpha \ge \beta$. Every such node differs only finitely from $e_{\beta }$. There are countably many finite subsets of the countable domain $\beta$ and countably many assignments of natural-number values to each, so there are only countably many possible finite modifications. Hence each level is countable. It is nonempty because it contains $e_{\beta }$.

Every shorter restriction of a node is again a node, and its predecessors have order type its domain ordinal. Thus this is a set-theoretic tree of height ${\omega }_1$. If it had an uncountable chain in a partial order, its domain heights would be unbounded in ${\omega }_1$, since the levels below any countable height contain only countably many nodes. The union of that chain in a partial order would be an injection ${\omega }_1\to \omega$, impossible. ThereforeThe countable-level proof uses coherence, whereas the no-branch proof uses injectivity; the two features play different roles.

Every countable structure in a countable first-order language has a Scott sentence whose countable models are precisely its isomorphic copies. In particular two countable structures with the same countable infinitary logic sentences are isomorphic. Countability of both structures is essential to the back-and-forth conclusion; the sentence need not exclude uncountable models.

Let $M$ be a nonempty countable structure in a countable first-order language. The countable infinitary logic $L_{{\omega }_1,\omega }$ permits countable logical conjunctions and logical disjunctions, but only finite strings of quantifiers and finitely many free variables in each formula. We construct a Scott formula ${\varphi }_{\bar{a}}^{\alpha }(\bar{x})$ for every finite tuple $\bar{a}$ from $M$ and every countable ordinal $\alpha$.

At stage zero, let ${\varphi }_{\bar{a}}^0$ be the conjunction of all atomic formulas true of $\bar{a}$ and the negations of all atomic formulas false of $\bar{a}$. Include atomic formulas involving arbitrary terms and constants, not just relation symbols applied directly to variables. There are only countably many such formulas. This complete atomic description ensures that matching tuples determine a partial isomorphism of structures.

At successors putAt a nonzero limit ordinal $\lambda <{\omega }_1$, put ${\varphi }_{\bar{a}}^{\lambda }={\bigwedge }_{\beta <\lambda }{\varphi }_{\bar{a}}^{\beta }$. All these are formulas of countable infinitary logic: each indexing set is countable, and the free variables are only the fixed finite tuple. Rename bound variables when necessary. Transfinite induction also shows $M\models {\varphi }_{\bar{a}}^{\alpha }(\bar{a})$.

For tuples of the same length within $M$, define $\bar{a}{\equiv }_{\alpha }\bar{b}$ by $M\models {\varphi }_{\bar{a}}^{\alpha }(\bar{b})$. Induction identifies this with the usual symmetric back-and-forth method equivalence: the tuples have the same atomic description at stage zero, and at a successor every one-element extension on either side has a matching extension at the previous stage. Thus these are decreasing equivalence relations, simultaneously for every finite tuple length.

There are only countably many pairs of finite tuples in $M$. A pair can cease to be equivalent at most once. The supremum of the first separation stages of all pairs that separate below ${\omega }_1$ is a countable ordinal. Choose a countable $\alpha$ at least that supremum. No pair can first separate at $\alpha +1$, soThis justifies stabilization without assuming that all tuples stabilize at one predetermined finite stage.

Now form the following Scott sentence, where the case $n=0$ has no displayed variables or quantifiers:It is a sentence of countable infinitary logic, because the family of all finite tuples is countable. The stabilization above and the truth of ${\varphi }_{\varnothing }^{\alpha }$ show $M\models {\sigma }_M$.

Suppose a countable structure $N$ satisfies ${\sigma }_M$. Start with the empty matching tuples, and maintain $N\models {\varphi }_{\bar{a}}^{\alpha }(\bar{b})$. The corresponding conjunct of ${\sigma }_M$ upgrades this to $N\models {\varphi }_{\bar{a}}^{\alpha +1}(\bar{b})$. The existential conjuncts extend the match by any specified element of $M$. The universal-disjunction conjunct extends it by any specified element of $N$. The atomic formula information makes a new element on one side match a new element on the other, and makes repeated elements agree with their earlier matches.

Enumerate both structures and alternate these two extension steps, including the least element not yet covered at each step. The union is a bijection preserving and reflecting every atomic formula, hence an isomorphism; for function symbols, eventually include both a tuple and the value of its function term to see explicitly that the function is preserved. For finite structures the same construction stops when both are covered. Conversely every isomorphic copy of $M$ satisfies ${\sigma }_M$, since isomorphisms preserve formulas of countable infinitary logic by induction on their construction. ThereforeIf countable $M,N$ have the same $L_{{\omega }_1,\omega }$ sentences, $N$ satisfies this Scott sentence of $M$ and is isomorphic to $M$. This proves Scott isomorphism theorem.

Let $u_{C,x}:C\to R$ be a colimit cocone for $G:\mathrm{Elts}(X)\to \mathcal{C}$. Here the preservation hypothesis must include the categorical limit of $G^{\mathrm{op}}$ in ${\mathcal{C}}^{\mathrm{op}}$; this indexing category can be large. For a morphism $f:(C,x)\to (D,y)$ of the category of elements, the defining equation $X(f)(y)=x$ says that the family of distinguished elements $(x{)}_{(C,x)}$ is compatible. Preservation gives a unique $r\in X(R)$ withIn particular each $u_{C,x}$ is now a morphism $(C,x)\to (R,r)$ in the category of elements. Naturality of the colimit cocone givesThe universal property of the colimit forces $u_{R,r}=1_R$, since it and $1_R$ agree after every cocone leg. If $f:C\to R$ also satisfies $X(f)(r)=x$, it is a morphism $(C,x)\to (R,r)$, and cocone compatibility now yields $u_{C,x}=u_{R,r}f=f$. Thus $(R,r)$ is a universal element. By the preceding representability criterion, the presheaf is represented by the colimit object:The size qualification matters. If preservation means only small categorical limits, the implication as printed is false for general locally small categories. For an explicit counterexample, let $\mathcal{C}$ be the ordered category of all ordinals with an extra greatest object $\infty$. Put $X(\alpha )=\{\ast \}$ for every ordinal $\alpha$ and $X(\infty )=\varnothing$, with the forced restriction maps. Every small colimit in $\mathcal{C}$ is the supremum of its object values: it is an ordinal unless the diagram contains $\infty$. Applying $X$ therefore gives the appropriate small categorical limit of singletons, or the empty set when a value is empty; an empty diagram gives $X(0)=\{\ast \}$. Hence $X$ preserves all small categorical limits.

Its category of elements consists of all ordinals, whose projection has the large colimit $\infty$ in $\mathcal{C}$. Nevertheless, no ordinal represents $X$, because its representable vanishes on larger ordinals; $\infty$ does not represent it either, since $\mathcal{C}(\infty ,\infty )$ is nonempty while $X(\infty )$ is empty. The valid proof consequently uses preservation of the displayed possibly large limit, or a smallness hypothesis making that diagram small.

The right-adjoint criterion using comma-category colimits is as follows. Under the given colimit-preservation hypothesis, with preservation including the possibly large colimits below, $F:\mathcal{X}\to \mathcal{A}$ has a right adjoint exactly when, for every $A$, the projectionhas a colimit in $\mathcal{X}$. The right adjoint is obtained from these comma-category colimits. Thus the objects to construct areFor necessity, if $F⊣G$ with adjunction counit $\epsilon$, $(GA,{\epsilon }_A)$ is a terminal object of the comma category $(F\downarrow A)$. Its unique incoming morphisms give a colimit cocone for $U_A$, exactly as for the elements projection in the preceding part.

For sufficiency, choose such a colimit $L$ with legs $u_{X,f}:X\to L$. The morphisms $f:FX\to A$ are a cocone on $F{U}_A$. Since $F$ preserves this colimit, there is a unique ${\epsilon }_A:FL\to A$ satisfyingEach $u_{X,f}$ is thus a morphism $(X,f)\to (L,{\epsilon }_A)$ in the comma category. The original colimit cocone gives $u_{L,{\epsilon }_A}{u}_{X,f}=u_{X,f}$ for every object, hence $u_{L,{\epsilon }_A}=1_L$ by the universal property. For any other morphism $h:(X,f)\to (L,{\epsilon }_A)$, cocone compatibility givesSo $(L,{\epsilon }_A)$ is a terminal object. Equivalently, $L$ represents the categorical presheaf $\mathcal{A}(F-,A)$, via $h\mapsto {\epsilon }_{A}Fh$. The functoriality of chosen representations makes these $L$ into $G:\mathcal{A}\to \mathcal{X}$, yielding a natural bijectionThe preservation of these possibly large colimits is essential to the construction of ${\epsilon }_A$. Under a small-only interpretation, the preceding ordinal counterexample also disproves the unqualified converse here. Take $F=X^{\mathrm{op}}:\mathcal{C}\to {\mathbf{Set}}^{\mathrm{op}}$. It preserves all small colimits. For a nonempty set $A$, the comma category $(F\downarrow A)$ has one object over each ordinal and none over $\infty$, so its projection has colimit $\infty$. For $A=\varnothing$, the projection is the identity of $\mathcal{C}$, again with colimit $\infty$. Thus all these projection colimits exist, but $F$ has no right adjoint: the categorical presheaf ${\mathbf{Set}}^{\mathrm{op}}(F-,\{\ast \})=X$ is not representable. This makes the large-preservation qualification substantive.

A cofinal map $f:\delta \to \alpha$ has a range cofinal in $\alpha$:For a limit $\alpha$, this is equivalent to $\sup f[\delta ]=\alpha$. For a successor $\alpha$, its largest element must occur in the range. Monotonicity is an additional property and is not part of this definition. The cofinality of $\alpha$ is the least ordinal that admits such a cofinal map into $\alpha$.

For clarity, each ${\rho }_{\beta }(\alpha )$ is an ordered finite sequence. Its minimal walk along a club sequence is finite because its nodes strictly decrease until reaching $\alpha$, and an infinite strictly decreasing sequence of ordinals cannot exist. At a step from $\delta >\alpha$, unboundedness of $C_{\delta }$ supplies $\min (C_{\delta }\setminus \alpha )$ in $[\alpha ,\delta )$.

Compare the two minimal walks along a club sequence to $\xi$ and to $\alpha$. As long as their current node is the same $\delta >\alpha$, their next nodes agree exactly when $C_{\delta }$ has no point in $[\xi ,\alpha )$. At the first such point, the walk to $\xi$ moves towhereas the walk to $\alpha$ stays at or above $\alpha$. If this does not occur before the second walk terminates, the first walk reaches $\alpha$ with it and then makes its next step below $\alpha$.

Thus there is an index $j$, possibly the terminal index of the walk to $\alpha$, withIt is unique: after this step the first walk stays below $\alpha$, so it can never again coincide with a node of the walk to $\alpha$. This is the first-divergence lemma for minimal walks.

A standard membership model of set theory has the actual membership relation:When “standard model” is used with the transitive-model convention, one also requires $M$ to be transitive: $x\in y\in M$ implies $x\in M$. Under a convention where standard means only actual membership, this extra requirement defines a transitive model. The set-theoretic absoluteness arguments below use transitive models of ZFC, so that bounded quantification and ordinals have their intended meaning.

Let $M\subseteq N$ be transitive models of ZFC containing the set relation $R$ and its underlying set $X$. If $M$ judges $R$ well founded, it has an ordinal rank function for a relation $\rho \in M$ by the preceding rank characterization. Being a function to ordinals and satisfyingis absolute: the values are actual ordinals and the checks use only bounded formulas in set theory. The same rank function exists in $N$, so $N$ judges $R$ well founded.

Conversely, if $M$ judged it not well founded, it would contain a nonempty set $Y$ with no $R$-minimal element. The property of this particular $Y$ is bounded and remains true in $N$, contradicting well-foundedness there. ThusThis is absoluteness of well-foundedness. The hypotheses that both models are transitive and satisfy ZFC matter; a small transitive set without sufficient recursion axioms need not contain the required rank witness.

The rank characterization holds for a set relation, or a set-like class relation. For such a well-founded relation, use well-founded recursion to defineThe predecessor set is a set, so the supremum is an ordinal. For a set-like class relation, the closure of the predecessors of any one point under finitely many predecessor steps is a set; perform the ordinary set recursion there. Uniqueness makes these local definitions agree, producing a class rank function. The formula immediately gives $xRy\Rightarrow \rho (x)<\rho (y)$.

Conversely, suppose such an ordinal-valued function exists. For any nonempty subset, or nonempty subclass in the class formulation, take an element whose rank is least among the ranks occurring. It has no predecessor in that subset or subclass, because a predecessor would have smaller rank. This proves well-foundedness.

There is a qualification in the printed class formulation. If well-founded class relations are defined to include set-likeness, it is already implicit and the assertion is correct. Under the minimal-element definition alone, it must be supplied. Without set-likeness, let $X=\mathrm{Ord}\cup \{u\}$, where $u=\{1\}$ is not an ordinal, and put every ordinal below $u$, with the usual ordinal order below it. Every nonempty subclass has a minimal element, so the relation is well founded. But transfinite induction forces $\rho (\alpha )\ge \alpha$ for all ordinals, whereas $\rho (u)$ would have to exceed every $\rho (\alpha )$. No such ordinal exists. Thus the unrestricted class assertion is false; set-likeness is necessary for this standard rank proof.

For $b\ge 2$, write a number in hereditary base $b$: express its base-$b$ expansion as ${\sum }_i{b}^{e_i}{c}_i$, with $0<c_i<b$, and recursively expand every exponent $e_i$ in the same base. Let $B_{b,c}(m)$, for $c>b$, be the number obtained by replacing every occurrence of the base $b$ in this hereditary expression by $c$. Coefficients and the symbols for addition and exponentiation are retained.

For a starting number $m$, define its Goodstein sequence by $m_0=m$ andThe Goodstein function is the termination-time functionThis choice counts transitions from the initial term; a convention counting the initial term as well shifts the answer by one. For example the sequence starting at $3$ is $3,3,3,2,1,0$, so $\mathcal{G}(3)=5$. Starting at $4$ gives $4,26,41,60,83,\dots$, illustrating why descent of the numerical terms is not the termination argument.

Define the ordinal rank of a Goodstein term ${\rho }_b(m)$ by replacing the base $b$ in the hereditary expansion by $\omega$, at every exponent depth. The result is in Cantor normal form and lies below ${ϵ}_0$, called epsilon zero, the least nonzero solution of ${\omega }^{\alpha }=\alpha$. Finite hereditary expressions have finite nesting depth, so their ranks are bounded by a sufficiently high finite tower of powers of $\omega$.

For a fixed base, ${\rho }_b$ is strictly increasing. To see this, compare two ordinary base-$b$ expansions at their largest differing exponent. By induction through the hereditary exponent expressions, their exponents have the same ordering after replacing $b$ by $\omega$; computable Cantor normal form notation then uses the same first differing exponent or coefficient. AlsoIndeed after the base change all coefficients remain below $c$, the recursively changed exponents remain correctly ordered, and replacing the new base by $\omega$ gives exactly the original ordinal expression. These facts can be proved together by structural induction for primitive recursive functions on the hereditary expression.

Consequently, whenever $m_s>0$,An infinite nonzero Goodstein sequence would give an infinite descending sequence of ordinals below ${ϵ}_0$, impossible because ordinals are well-ordered. Thus the Goodstein function is total. Its steps are effective finite operations, so simulating the sequence until zero also proves that it is a total computable function.

The same ordinal notation system gives the requested decidable well-order. Let $D$ consist of canonical finite terms for zero and for expressionswhere the exponents are themselves canonical terms. Membership in $D$ is decidable by recursively checking the syntax, positive coefficients and decreasing exponents. Comparison is decidable by recursive computable Cantor normal form notation, first of exponents, then coefficients, and then the remaining summands. All recursive calls inspect proper subterms, so the algorithm terminates.

Interpreting these terms as ordinals gives every ordinal below ${ϵ}_0$, uniquely. One way to connect this directly to hereditary base representations is to choose, for a given finite ordinal term, a base larger than every coefficient anywhere in that term. Replacing $\omega$ by that base evaluates it to a natural number whose hereditary representation recovers the ordinal term. Thus all bases together supply the complete notation system; a single fixed base is not enough.

Choose an effective injective coding of finite terms by natural numbers, and enumerate the valid codes in increasing numerical order. The resulting bijection $d:\mathbb{N}\to D$ is computable: validity is decidable and there are infinitely many finite-ordinal terms. Its inverse is computable by counting valid codes below a given code. DefineThis is a decidable relation on all of $\mathbb{N}$. The interpretation into ordinals is an order isomorphism onto ${ϵ}_0$, provingDecidability here concerns comparing two notations. Well-foundedness is supplied by their ordinal interpretation, the same mathematical descent principle used to prove Goodstein's theorem.