Foundations of mathematics

A family of size-$\kappa$ subsets of a set is almost disjoint at $\kappa$ when distinct members have intersection of size less than $\kappa$. Graphs of a long chain under eventual domination give such a family of size ${\kappa }^{+}$ on $\kappa \times \kappa$. Transport by a bijection gives a family on $\kappa$ itself.

Any at-most-$\kappa$ subfamily of an almost disjoint family on a regular cardinal becomes pairwise disjoint after deleting fewer than $\kappa$ points from each member. Enumerate it in length at most $\kappa$ and apply the displayed trimming. Each removed part is a union of fewer than $\kappa$ small intersections, so regular cardinal arithmetic bounds it below $\kappa$.

For a set $A$ of size an uncountable regular cardinal $\kappa$, an increasing sequence $(A_{\alpha }{)}_{\alpha <\kappa }$ with union $A$, each $|A_{\alpha }|<\kappa$, and $A_{\delta }={\bigcup }_{\alpha <\delta }{A}_{\alpha }$ at every nonzero limit stage.

A family of infinite subsets of $\omega$ such that any two distinct members have finite intersection.

An almost disjoint family on omega that cannot be enlarged by another infinite subset while retaining almost disjointness. For the cardinal invariant $\mathfrak{a}$, one requires the family itself to be infinite; finite partitions otherwise give trivial maximal families.

The least size of an infinite maximal almost disjoint family on omega. Zorn lemma extends an infinite disjoint family to a maximal one; thus $\mathfrak{a}\le 2^{{\aleph }_0}$. The bounding-to-almost-disjointness inequality supplies $\mathfrak{b}\le \mathfrak{a}$.

For an infinite almost disjoint family on omega of size less than the bounding number, select countably many members and remove their intersections with earlier selected members to obtain infinite disjoint sets $C_n$. Bound, eventually and simultaneously, the finite intersections of each member with $C_n$. Choose one point of each $C_n$ above its bound. The resulting infinite set is almost disjoint from every original member, proving the family is not maximal. A selected member has one exceptional infinite intersection, which is ignored in its bounding function.

A model whose relation symbol for membership is interpreted by actual membership restricted to its domain. If the domain is also transitive, it is a transitive model. Some conventions include this transitivity requirement in the word standard.

The notation $\lambda \to (\mu {)}_{\beta }^{\alpha }$ says that every $\beta$-coloring of the $\alpha$-element subsets of $\lambda$ has a homogeneous subset of order type $\mu$. At infinite arity one specifies whether the domain subsets have a fixed cardinality or a fixed order type; the usual finite-arity notation has no such ambiguity.

The relation $\lambda \to (\lambda {)}_{\beta }^{<\omega }$ requires a subset of size $\lambda$ homogeneous at each finite arity. The constant color may depend on the arity.

If inaccessible $\lambda$ has the finite-subset partition property for every color number below $\lambda$, forcing of size below $\lambda$ preserves its two-color version. Color ground-model finite sets by their full forcing decision patterns; strong-limit cardinal arithmetic bounds the number of patterns.

A partition relation whose colored subsets are infinite. For countably infinite arity, choosing representatives modulo finite symmetric difference and coloring its parity shows $\kappa \nrightarrow (\omega {)}_2^{\omega }$ for every infinite cardinal $\kappa$.

For functions $f,g:\omega \to \omega$, write $f{\le }^{\ast }g$ when $f(n)\le g(n)$ for all sufficiently large $n$. A dominating family is cofinal for this relation.

For $f,g:\kappa \to \kappa$, write $f{<}^{\ast }g$ when there is $\gamma <\kappa$ such that $f(\delta )<g(\delta )$ whenever $\gamma <\delta <\kappa$. For an infinite regular cardinal, suprema of fewer than $\kappa$ ordinals below $\kappa$ remain below it, permitting the long chain under eventual domination construction.

For every infinite regular cardinal $\kappa$, there is a strictly eventually increasing sequence of ${\kappa }^{+}$ functions $\kappa \to \kappa$. At stage $0<\zeta <{\kappa }^{+}$ enumerate predecessors by $e:\kappa \to \zeta$ and put $f_{\zeta }(\delta )={\sup }_{\eta <\delta }(f_{e(\eta )}(\delta )+1)$. Regularity bounds each value below $\kappa$, while any predecessor's index is eventually included in the supremum.

The least size of a family in ${\omega }^{\omega }$ having no common bound for eventual domination. Every countable family $(f_i)$ has the bound $g(n)=1+{\max }_{i\le n}{f}_i(n)$, so ${\aleph }_1\le \mathfrak{b}\le 2^{{\aleph }_0}$.

A family $C\subseteq {\omega }^{\omega }$ such that every $f\in {\omega }^{\omega }$ is eventually dominated by some $g\in C$.

A partition ${\mathbb{R}}^2=A\bigsqcup B$ in which every vertical section of $A$ and every horizontal section of $B$ is countable. Swapping the coordinate directions gives the equivalent convention.

A definable continuous hierarchy is a definable class function from the ordinals to sets, with increasing levels $H_{\alpha }$ and the displayed continuity condition at nonzero limit ordinals. Its union is a definable class in set theory. One often additionally requires transitive sets as levels. Finite collections of first-order formulas reflect along this hierarchy by the reflection theorem for definable hierarchies.

Zermelo–Fraenkel set theory is the usual first-order axiomatization of sets by extensionality, empty set, pairing, union, power set, infinity, separation, replacement and foundation.

The axiom asserts the existence of a set containing the empty set and closed under the successor operation $x\mapsto x\cup \{x\}$:In Zermelo–Fraenkel set theory, this supplies a set from which the set of natural numbers is constructed.

ZFC is Zermelo–Fraenkel set theory together with the axiom of choice.

The von Neumann hierarchy isEvery level is transitive, the levels are increasing, and every set belongs to some level.

If $\alpha$ is a countable ordinal and $V_{\alpha }\models \mathsf{ZFC}$, then $\alpha$ must be a limit ordinal. Choose a countable cofinal sequence $({\alpha }_n)$ in $\alpha$. The internal axiom of choice gives, for every $n$, a bijection between $V_{{\alpha }_n}$ and some ordinal below $\alpha$; that ordinal is externally countable, so every $V_{{\alpha }_n}$ is countable. Hence $V_{\alpha }={\bigcup }_n{V}_{{\alpha }_n}$ is countable. But $V_{\alpha }$ contains the full power set $\mathcal{P}(\omega )$, which is uncountable by Cantor theorem, a contradiction.

For every finite collection $\Phi$ of first-order formulas, there are arbitrarily large ordinals $\alpha$ such that, for every $\phi \in \Phi$ and all parameters in $V_{\alpha }$,The reflecting ordinals for $\Phi$ form a closed unbounded class.

For inaccessible $\kappa$ and any predicate $R\subseteq V_{\kappa }$, the ordinals $\alpha <\kappa$ with $⟨V_{\alpha },\in ,R\cap V_{\alpha }⟩\prec ⟨V_{\kappa },\in ,R⟩$ form a club. Closure under ranks of existential witnesses gives unboundedness, and the elementary chain theorem gives closedness.

A finite collection of first-order formulas has a closed unbounded class of ordinals whose levels in a definable continuous hierarchy agree with its union for all parameters in the level. Close the collection under subformulas, bound the least witness levels for existential instances on each set-sized stage by Axiom schema of replacement, and iterate these bounds countably. Continuity supplies the closed stages, and induction on formulas proves agreement. The Tarski-Vaught test describes the same witness criterion. For a hierarchy of length an uncountable regular cardinal, bounds stay below that cardinal when every stage has smaller cardinality.

A first-order formula $\phi$ describes an ordinal $\alpha$ when $\alpha$ is the least ordinal such that $V_{\alpha }\models \phi$. No strongly inaccessible cardinal can be described: if $V_{\kappa }\models \phi$, the Lévy reflection theorem produces some $\alpha <\kappa$ with $V_{\alpha }\models \phi$.

The rank is defined byIt is the least ordinal $\alpha$ for which $x\subseteq V_{\alpha }$.

The definable power set $\mathcal{D}(X)=\mathrm{Def}(X)$ consists of the subsets of $X$ definable over the first-order structure $(X,\in )$ by a first-order formula with parameters from $X$. Satisfaction for a set structure makes this a definable operation in ZF. Iterating it produces the constructible hierarchy and the relative constructible hierarchy; their unions are the constructible universe and the relative constructible universe.

A useful finite conjunction of closure assertions requires empty set, pairing, set union, set difference, Cartesian products, all finite tuple domains $A^n$, and the following operations on their relations: relative complements, intersections, coordinate projections and pullbacks along finite coordinate maps, together with equality and membership restricted to $A^2$. The arities and maps are quantified objects, so these requirements form finitely many first-order formulas, not an infinite schema. In a transitive set, individual finite tuples exist by pairing and union, making the tuple-domain assertions correct externally. Atomic truth relations, Boolean operations and projection then compute the truth table of each coded first-order formula correctly by finite induction. Thus satisfaction for a set structure and the relation $B=\mathrm{Def}(A)$ are absolute for shared arguments. Every nonzero limit level of the relative constructible hierarchy is closed under these operations, since each result can be defined at finitely many subsequent stages.

The constructible hierarchy is defined byfor limit ordinals $\lambda$. Its union is the constructible universe $L$.

The equality $L\cap V_{\alpha }=L_{\alpha }$ can fail even at $\alpha =\omega +1$. Inside the constructible universe, $L_{\omega }=V_{\omega }$ is countable, so its definable power set $L_{\omega +1}$ is countable. The constructible power set of $\omega$ is uncountable there by the Cantor theorem. A real outside $L_{\omega +1}$ remains a constructible subset of $\omega$, hence belongs to $V_{\omega +1}$. The cardinal comparison must be made inside $L$, since its reals can be externally countable.

For a transitive model $M$ of ZFC and $\alpha \in M\cap \mathrm{Ord}$, the internally computed constructible hierarchy agrees with the ambient level: $L_{\alpha }^M=L_{\alpha }$. Satisfaction for a fixed set structure is computed from the same finite formulas and the same domain in both universes. Transfinite recursion then proves agreement at successors and limits. If $\theta =M\cap \mathrm{Ord}$, it follows that $L_{\theta }\subseteq M$.

If $M$ is a transitive model of ZF, its internally computed $L_{\alpha }$ is the actual $L_{\alpha }$ for each ordinal $\alpha \in M$. At a successor stage use absoluteness of satisfaction for the same set structure, formula codes and parameters; at a limit stage take the union of the already identical earlier stages. Choice is not required.

The constructible universe is the inner model $L={\bigcup }_{\alpha \in \mathrm{Ord}}{L}_{\alpha }$ obtained by iterating the definable power set. It satisfies ZFC and the Generalized continuum hypothesis.

Every set belongs to some level of the constructible hierarchy. The assertion is $\forall x\exists \alpha (x\in L_{\alpha })$, not that each set is definable without parameters. The constructible universe theorem supplies a relative-consistency model of this assertion from ZFC.

To separate a subset of a constructible set by a formula interpreted in the constructible universe, apply the reflection theorem for definable hierarchies to the formula and its subformulas. At a sufficiently large reflecting level containing the parameters, the desired subset is definable and belongs to the next constructible hierarchy level. The reflection proof uses least witness stages and ambient Axiom schema of replacement, so does not presuppose Axiom schema of separation within the constructible universe.

ZFC proves that the constructible universe is an inner model of ZFC and satisfies the Generalized continuum hypothesis. Relativizing to $L$ yields the corresponding relative-consistency implication.

The constructible universe satisfies the diamond principle. Together with antichain sealing by diamond, this supplies a Suslin tree in $L$.

This statement says that the first uncountable ordinal of an inner model $L$ is a countable ordinal in the ambient universe. It can hold together with the Generalized continuum hypothesis: start with constructibility and use a finite-function collapse to countable size on ${\omega }_1^L$. The GCH preservation by a finite-function collapse calculation gives the relative consistency result already from the consistency of ZFC.

Inside the constructible universe, every hereditarily countable set appears in a countable level of the constructible hierarchy. Take a countable elementary substructure of a sufficiently large $L_{\eta }$ containing its transitive closure pointwise. The condensation lemma for the constructible universe identifies the collapse with $L_{\beta }$ for countable $\beta$, and the collapse fixes the original set. Conversely, a countable-indexed level is countable inside the constructible universe.

For $A\in L$, its constructible power set isUnlike the single-stage definable power set $\mathcal{D}(A)$, it includes subsets of $A$ appearing arbitrarily late in the constructible hierarchy.

For a transitive set $X$, the relative constructible universe $L(X)$ is the union of the relative constructible hierarchy, starting at $L_0(X)=X$, applying the definable power set at successors and taking unions at limit ordinals. It is the smallest inner model of ZF containing $X$ and all its members. For an arbitrary set $A$, take the base $X$ to be the transitive closure of $\{A\}$, so that $A\in X$. Axiom of choice need not hold for an arbitrary base; the construction uses initial parameters rather than a predicate relativization.

An inner model $W$ of ZF containing all ambient subsets of $\omega$ computes the same countable ordinals as the ambient universe. Every ambient countably infinite ordinal has a well-order code coded by a subset of $\omega$, hence that code belongs to $W$; finite ordinals are already shared. The Mostowski collapse theorem inside $W$ recovers the actual ordinal and its countability witness. Conversely any countability witness in $W$ remains one outside. If $W$ also contains the full power set of $\omega$ as a set, its Continuum hypothesis would give an ambient bijection from ${\omega }_1$ onto that same power set. Thus an ambient failure of this well-orderable formulation of the Continuum hypothesis is preserved in such an inner model. No internal axiom of choice is required for this argument.

For a transitive set $X$, use $L_0(X)=X$, $L_{\alpha +1}(X)=\mathrm{Def}(L_{\alpha }(X))$ and unions at nonzero limit ordinals. The successor operation is the definable power set. Each level is transitive and the levels increase; moreover $X\in L_1(X)$. Their union is $L(X)$, an inner model of ZF. The initial-set convention differs from a hierarchy using a predicate, or one starting at $X\cup \{X\}$. Axiom of choice need not hold for an arbitrary base without an internally available well-order.

If $\alpha$ is a nonzero limit ordinal and $Y\prec L_{\alpha }(X)$ with $X\cup \{X\}\subseteq Y$, the Mostowski collapse theorem sends $Y$ to $L_{\beta }(X)$ for some nonzero limit $\beta \le \alpha$ and fixes $X$ pointwise. The base is fixed by transitivity and inclusion of all its members. Transfer the relative constructible level recognition formula first by elementarity and then through the collapse isomorphism to identify its image. If $\rho =X\cap \mathrm{Ord}$, ordinal heights are $\rho +\alpha$ and $\rho +\beta$, giving the bound. Having only $X\in Y$ does not guarantee this base-fixing version.

For transitive sets $M,X$ with $X\in M$, a single first-order formula $\Phi (X)$ recognises the nonzero limit levels $L_{\alpha }(X)$. Require finite relation closure for set-theoretic coding, transitivity of $X$, that every element belongs to a coded relative constructible stage, and that every represented stage index has a larger represented index. Correct history codes have downward-closed indices with no maximum, hence form a nonzero limit ordinal $\alpha$. The exhaustion assertion and transitivity then give $M={\bigcup }_{\xi <\alpha }{L}_{\xi }(X)$. Conversely every limit level has the required closure, correct histories cofinal in its index, and exhaustion. This formulation does not assume ZF for an arbitrary input $M$ and does not replace finite coding closure with an unjustified internal constructibility assertion.

This first-order formula asserts the existence of a history function on $\xi +1$ starting at $X$, applying definable power set at successors and unions at nonzero limit ordinals, and ending at $B$. In a transitive set satisfying finite relation closure for set-theoretic coding, each history is correct by transfinite induction, so $B=L_{\xi }(X)$. Relation operations produce restrictions to shorter histories. Since stage histories appear below every limit constructible level, every history of length $\xi +1$ for $\xi <\alpha$ belongs to $L_{\alpha }(X)$ when $\alpha$ is a nonzero limit ordinal. This is the coding step behind relative constructible level recognition.

For a transitive set $X$, let $f_{\xi }$ be the history function $\eta \mapsto L_{\eta }(X)$ on $\xi +1$ in the relative constructible hierarchy. By transfinite induction, $f_{\xi }\in L_{\xi +k}(X)$ for some finite $k$, possibly depending on $\xi$. The base and successor steps follow by forming finite ordered pairs and adjoining the next entry, using $L_{\xi +1}(X)\in L_{\xi +2}(X)$. These operations require finitely many subsequent definable power sets.

At a nonzero limit ordinal $\lambda$, the inductive bounds put every earlier $f_{\eta }$ in $L_{\lambda }(X)$, since $\eta +k<\lambda$. This level satisfies finite relation closure for set-theoretic coding, independently of the availability of history functions. Consequently its coded relative constructible stage predicate computes the endpoints correctly. Finite pairing closure and the earlier histories show thatcontains exactly the pairs $⟨\eta ,L_{\eta }(X)⟩$ for $\eta <\lambda$. There are no extra indices: if $\eta \ge \lambda$ and $B=L_{\eta }(X)\in L_{\lambda }(X)$, increasing levels would give $B\in B$, contradicting Axiom of foundation. Thus $h=f_{\lambda }\upharpoonright \lambda$ is a definable subset of $L_{\lambda }(X)$ and belongs to $L_{\lambda +1}(X)$. Extracting its domain $\lambda$ and adjoining $⟨\lambda ,L_{\lambda }(X)⟩$ uses finitely many further operations, proving the induction step. Every nonzero limit $\alpha$ therefore contains all $f_{\xi }$ with $\xi <\alpha$, as required by relative constructible level recognition.

Assume a transitive model $M$ satisfies $2^{{\aleph }_0}={\aleph }_2$. In $M$, encode a bijection $e:{\omega }_2\to \mathcal{P}(\omega )$ by one set $A\subseteq {\omega }_2$, using a fixed pairing of ${\omega }_2\times \omega$ with ${\omega }_2$. Then $L(A)$ decodes $e$ and contains every real of $M$. The two models consequently have the same ${\omega }_1$, and any bijection between ${\omega }_1$ and the real numbers in $L(A)$ would also be one in $M$. Thus $L(A)\models \neg \mathsf{CH}$.

A condensation sentence is a fixed first-order sentence $\sigma$ such that every transitive set satisfying $\sigma$ is $L_{\lambda }$ for a limit ordinal $\lambda$. It combines a sufficiently strong finite fragment of set theory, the assertion that every set is constructible, and the absence of a largest ordinal.

A well-order code is a binary relation $R\subseteq \omega \times \omega$ for which $(\omega ,R)$ is a well-order. Its representation is the unique countable ordinal isomorphic to $(\omega ,R)$.

A level $L_{\lambda }$ is a coding level when $\lambda$ is a limit ordinal, the representation of every well-order code in $L_{\lambda }$ is below $\lambda$, and every ordinal below $\lambda$ has a well-order code in $L_{\lambda }$.

If $X$ is an elementary substructure of a sufficiently large level $L_{\theta }$, then the transitive collapse of $X$ is a level $L_{\beta }$. In particular, a countable $X$ collapses to a level indexed by a countable ordinal.

Forcing extends a model of set theory by adjoining a filter generic for a partially ordered set of finite or otherwise controlled approximations.

A subset of a forcing order whose distinct members have no common stronger extension. A maximal forcing antichain has a compatible member for every condition. For forcing by nodes of a set-theoretic tree, ordered by extension, this coincides with a tree antichain.

A forcing collapses a ground-model cardinal $\kappa$ if it forces a bijection from a smaller ordinal onto the ground ordinal $\kappa$. The ordinal itself is preserved; its being an initial ordinal is lost.

A forcing is cofinality-preserving over a transitive model $M$ if every generic extension has the same cofinality for every ground ordinal. The values are compared as ordinals, which forcing preserves.

For a cardinal number $\kappa$, ${\mathrm{MA}}_{\kappa }$ says that for every forcing with the countable chain condition for forcing and every family of at most $\kappa$ dense subsets, some filter in an ordered set meets them all. Full Martin axiom asserts this for all $\kappa <2^{{\aleph }_0}$. The strict upper bound is part of the definition.

A forcing order that is countable inside the ground model. It has the countable chain condition and preserves ${\omega }_1$. Internal countability is distinct from external countability of the entire model.

Over a Generalized continuum hypothesis ground model, adding one Cohen real preserves every infinite power $2^{\lambda }={\lambda }^{+}$. For the countable forcing, nice subset forcing names for $\lambda$ number at most $(2^{{\aleph }_0}{)}^{\lambda }=2^{\lambda }$ in the ground model. Old subsets give the matching lower bound and the countable chain condition for forcing preserves cardinals. Starting from the constructible universe, the new real is nonconstructible while the constructible levels remain unchanged.

A ground-model Suslin tree remains Suslin after countable forcing. A new uncountable chain or antichain would contain an uncountable ground-model subset by the ground-model uncountable subset lemma for countable forcing.

An uncountable set of ground-model elements in a generic extension by countable forcing contains an uncountable ground-model subset. Partition membership witnesses according to the countably many forcing conditions.

In standard notation for forcing, an order is separative if $p\nleqq q$ implies that some $r\le p$ is incompatible with $q$. Separativity does not imply an atomless forcing order: the one-point order is separative and has a forcing atom. Its only generic filter is a ground-model set. Atomlessness is the hypothesis in generic filter for an atomless order is new.

A condition is an atom if every two stronger conditions are compatible forcing conditions. This is a compatibility definition, not necessarily minimality in an arbitrary partial order. An atomless forcing order is one in which every condition has two incompatible strengthenings.

For a forcing atom $p$ in a ground-model forcing order, $G_p$ is a ground-model generic filter. It contains $p$ and is upward closed. For $q,r\in G_p$, choose $q^{\prime }\le p,q$ and $r^{\prime }\le p,r$. The atom property gives $s\le q^{\prime },r^{\prime }$, so $s\in G_p$ is a common strengthening of $q,r$. Thus $G_p$ is a filter in an ordered set. Every dense subset of a forcing order has some $d\le p$, and $d\in G_p$. The defining compatibility predicate is bounded to the ground-model set of conditions, so axiom schema of separation forms $G_p$ inside the ground model. For a nonminimal atom, this filter can strictly contain the principal filter above $p$.

An order is atomless if it has no forcing atom, equivalently every condition has a pair of incompatible forcing conditions below it. For a fixed order belonging to a transitive model, this property is absolute because its quantifiers range over the unchanged set of conditions. Infinite-domain Fn forcing with at least two possible values is atomless: prescribe different values at one fresh coordinate.

If a generic filter $G$ for an atomless forcing order belonged to its ground model, then the complement $\mathbb{P}\setminus G$ would be a dense ground-model set. A condition outside $G$ is already there; a condition in $G$ has two incompatible strengthenings, at least one outside its directed filter. Genericity would then require meeting the complement, a contradiction.

The conditions are pairs with coordinatewise extension: $(p,q)\le (p^{\prime },q^{\prime })$ exactly when $p\le p^{\prime }$ and $q\le q^{\prime }$. The projection of a product-generic filter is a pair of factor filters whose Cartesian product is the original filter. Each is ground-model generic, and mutual genericity for product forcing makes the second generic over the extension by the first.

If $H=G_0\times G_1$ is generic for product forcing over $M$, then $G_1$ is generic over $M[G_0]$. For a name $\dot{D}$ for a dense subset of the second factor, take $p_0\in G_0$ forcing density. Ground-model pairs with first coordinate incompatible with $p_0$, or with first coordinate below $p_0$ forcing the second into $\dot{D}$, form a dense product set. The existential clause of syntactic forcing and the membership clause for a canonical forcing name give the density witnesses. The product filter meets this set, cannot use the incompatible case, and hence its second projection meets ${\dot{D}}^{G_0}$.

For a generic filter $H$ in product forcing, let $G_0,G_1$ be its coordinate projections. They are filters in an ordered set. Given $p\in G_0$ and $q\in G_1$, choose separate pairs witnessing their membership and then a common strengthening in $H$. Upward closure puts $(p,q)$ in $H$, proving the displayed equality. Every ground-model dense factor set lifts to a dense product set, proving genericity of each projection over the ground model.

A condition consists of a finite sequence and an infinite reservoir of allowed future values. A stronger condition extends the sequence, shrinks the reservoir, and takes all newly appended values from the old reservoir. Stem values may repeat. The union of the generic stems is an unbounded real over a model: for every ground-model function $g$ and every threshold $K$, the conditions whose stem already has some $k\ge K$ with $g(k)<s(k)$ form a dense subset of a forcing order. An infinite subset of $\omega$ always supplies a sufficiently large value.

A function $f\in {\omega }^{\omega }$ is unbounded over a model $M$ if for every $g\in M\cap {\omega }^{\omega }$, infinitely many $k$ satisfy $g(k)<f(k)$. Equivalently, no ground-model function eventually dominates it. This is weaker than being a dominating real over $M$.

A forcing order preserves cardinals over a ground model if every ground-model cardinal number remains a cardinal in every generic extension. This assertion and any sufficient chain condition for forcing are evaluated inside the ground model. External countability of a countable transitive model does not make all of its forcing orders internally ccc.

A forcing name is a recursively built set of pairs $(\sigma ,p)$, where $\sigma$ is a lower-rank forcing name and $p$ is a forcing condition. Ground-model names are interpreted using a generic filter to form the generic extension.

The ordinal assigned recursively by $\mathrm{nrk}(\tau )=\sup \{\mathrm{nrk}(\sigma )+1:(\sigma ,p)\in \tau \}$. It measures dependency on subnames and justifies generic evaluation by recursion. The ordinary rank of a set also accounts for the coding of the ordered pairs and the forcing conditions; it need not equal this dependency rank of a set.

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.

A name for a subset of a ground-model set, given coordinatewise by antichains in a forcing order. For countable-chain-condition forcing, each coordinate uses a countable antichain, which bounds the number of names for reals.

For the condition-first forcing name convention, pair every condition with each of two names $\tau ,{\tau }^{\prime }$. Under any nonempty generic filter, the evaluation of a forcing name is then $\{{\tau }_G,{\tau }_G^{\prime }\}$, the unordered pair of the two values. Equal values give a singleton. With the name-first convention, reverse the two components of each syntactic pair.

The forcing name $\{(\check{p},q):p,q\in \mathbb{P},q\perp p\}$ evaluates to $\mathbb{P}\setminus G$. If $p\notin G$, genericity applied to $\{q:q\le p\text{ or }q\perp p\}$ supplies an incompatible member of $G$. If $p\in G$, directedness prevents such a member.

Interpret a forcing name recursively by $\mathrm{val}(\tau ,G)=\{\mathrm{val}(\sigma ,G):\exists p\in G((\sigma ,p)\in \tau )\}$. The collection of interpreted ground-model names is the generic extension.

The canonical forcing name for a ground-model set $x$ is $\check{x}=\{(\check{y},1):y\in x\}$. Its evaluation of a forcing name under every generic filter is $x$.

For an infinite ground-model cardinal number $\kappa$, use finite partial functions from $\omega$ to $\kappa$, ordered by reverse inclusion. The union of a generic filter is a surjection $\omega \to \kappa$. The order has size $\kappa$, hence the ${\kappa }^{+}$-chain condition, and preserves cardinals at least ${\kappa }^{+}$.

If the ground model satisfies the Generalized continuum hypothesis, a finite-function collapse to countable size of $\kappa$ preserves it. The old ${\kappa }^{+}$ becomes the new ${\aleph }_1$, and there are at most $2^{\kappa }={\kappa }^{+}$ names for subsets of $\omega$. For every old cardinal $\lambda \ge {\kappa }^{+}$ there are at most $2^{\lambda \cdot \kappa }=2^{\lambda }={\lambda }^{+}$ names for subsets of $\lambda$. Cardinal preservation by chain-condition forcing and Cantor theorem turn these upper bounds into the required equalities.

In standard forcing notation, $q\le p$ says that $q$ is stronger than $p$: the smaller condition carries more information.

In Jerusalem notation, $p\le q$ says that $q$ is stronger than $p$: the larger condition carries more information.

Two forcing conditions are compatible when they have a common stronger extension. In standard notation this means that some $r$ satisfies $r\le p,q$; in Jerusalem notation for forcing it means that some $r$ satisfies $p,q\le r$.

Two forcing conditions are incompatible when they have no common stronger extension.

A subset $D$ of a forcing order $\mathbb{P}$ is dense when every $p\in \mathbb{P}$ has a stronger extension $q\le p$ in $D$.

For the convention that larger conditions are stronger, density above $p$ means every strengthening of $p$ has a further strengthening in $D$. It is the extension-cone density usually called dense below a forcing condition when smaller conditions are stronger. The sign must be translated with the order convention, rather than copied unchanged.

A set $D\subseteq \mathbb{P}$ is dense below $p$ when every $q\le p$ has an extension $r\le q$ belonging to $D$.

If $p\in G$ and a ground-model set $D$ is dense below a forcing condition $p$, then the generic filter $G$ meets $D$. Add all incompatible forcing conditions with $p$ to $D$. The enlarged set is globally dense: a condition compatible with $p$ first has a common strengthening, then a further strengthening in $D$. Genericity meets the enlargement, and directedness excludes its incompatible part.

A filter $G\subseteq \mathbb{P}$ is generic over a model $M$ when it meets every dense subset of $\mathbb{P}$ belonging to $M$.

A filter is generic over its ground model exactly when it meets each ground-model maximal forcing antichain in one point. Extensions of a maximal antichain form a dense set, while any ground dense set contains an antichain maximal in the whole forcing. Directedness permits at most one antichain member in a filter.

If $M$ is a countable transitive model, $\mathbb{P}\in M$, and $p\in \mathbb{P}$, enumerate the dense subsets of $\mathbb{P}$ belonging to $M$ and recursively choose a decreasing sequence starting below $p$ that meets each one. Its upward closure is a generic filter over $M$ containing $p$.

If $G$ is a generic filter over a countable transitive model $M$, the generic extension $M[G]$ consists of the interpretations by $G$ of all forcing names in $M$.

Let $M_{n+1}=M_n[G_n]$ for a fixed atomless forcing order $\mathbb{P}$, and $N={\bigcup }_{n<\omega }{M}_n$. If a set $A\in N$ were its internal power set of $\mathbb{P}$, choose $n$ with $A\in M_n$. The next generic filter $G_n$ belongs to $N$, so $G_n\in A$; transitivity of $M_n$ implies $G_n\in M_n$, contradicting generic filter for an atomless order is new. The chain is increasing but need not be an elementary chain.

For a forcing name $\tau$, let $U$ consist of pairs $(\rho ,p)$ where $(\rho ,r)\in \tau$ for some $r\ge p$. Every ground-model subset $\nu$ of $U$ is a name whose value is contained in ${\tau }^G$. Every subset ${\sigma }^G\subseteq {\tau }^G$ has an equivalent such name: retain those $(\rho ,p)\in U$ with $p⊩\rho \in \sigma$. The atomic membership truth lemma for forcing proves equality of values. Collect all these names from the ground-model power set ${\mathcal{P}}^M(U)$ into a single outer name, pairing each with every condition. Its value is the full internal power set, without presupposing that power set in the extension.