# Independence of the Continuum Hypothesis: an
Intuitive Introduction

Serafim Batzoglou

<figure><img src="image_1.png" /></figure>

► To cite this version:

Serafim Batzoglou. Independence of the Continuum Hypothesis: an Intuitive Introduction. 2022. hal-03754893

HAL Id: hal-03754893

https://hal.science/hal-03754893v1

Submitted on 20 Aug 2022

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_2.png" /></figure>

Distributed under a Creative Commons CC BY 4.0 - Attribution - International License
# Independence of the Continuum Hypothesis: an Intuitive Introduction

Serafim Batzoglou

August 20, 2022

## Abstract

The independence of the continuum hypothesis is a result of broad impact: it settles a basic question regarding the nature of $N$ and $R$, two of the most familiar mathematical structures; it introduces the method of forcing that has become the main workhorse of set theory; and it has broad implications on mathematical foundations and on the role of syntax versus semantics. Despite its broad impact, it is not broadly taught. A main reason is the lack of accessible expositions for nonspecialists, because the mathematical structures and techniques employed in the proof are unfamiliar outside of set theory. This manuscript aims to take a step in addressing this gap by providing an exposition at a level accessible to advanced undergraduate mathematicians and theoretical computer scientists, while covering all the technically challenging parts of the proof.

# 1 Introduction

Infinity comes in different sizes. Circa 1874, Cantor proved that the countable infinity $N$ is strictly smaller than the continuum $R$ because there is no surjection from $N$ to $R$. The Continuum Hypothesis (CH) postulates that there is no infinity bigger than $N$ and smaller than $R$.

We are all familiar with the natural numbers and the real line, so asking whether there is a set of intermediate size is natural and basic. In his famous 1900 speech, Hilbert named the 23 most important open mathematical problems at the time and CH was number 1 on the list. Astonishingly, the question is independent of the axioms of set theory—essentially, independent of common mathematics. If a proof of either CH or “not CH” is found, the proof can be extended to a contradiction. Proving the independence of CH was a long journey from Cantor’s 1874 formulation, to Hilbert naming it as the number 1 open problem in 1901, to Gödel proving that CH is consistent with set theory in 1939, to finally Cohen settling the question in 1963 by proving that “not CH” is also consistent with set theory.

The independence of CH is one of the most important mathematical results of all time, and arguably one of the great accomplishments of human intellect. However, as Scott Aaronson indicated in his blog<fnref n="1" />, “perhaps no other scientific discovery of equally broad interest remains so sparsely popularized”. Aaronson and Timothy Chow (2007), who wrote an excellent readable exposition on the topic, call this an “open exposition problem”. My aim here, besides having fun writing on the topic, is to take a stab at this exposition problem aiming for an audience of computer scientists and amateur mathematicians, assuming discrete math or theoretical computer science major-level background. I aimed to write a manuscript that would have been helpful to me in my self study of the topic, and decided to forego brevity and instead motivate and elaborate on the key ideas and especially on the notion of “genericity”.

**Layers of complexity in understanding the proof.** The proof is generally considered exceptionally hard—especially in one direction, consistency of “not CH”. To prove this, Cohen devised the powerful technique of *forcing* that has since become a main workhorse of set theorists. There are three independent sources of complexity in this proof:

1. The general unfamiliarity of broad audiences with foundational mathematics: set theory, model theory and proof theory.

<footnote n="1">¹https://scottaaronson.blog/?p=4974</footnote>
2. As S. Aaronson described eloquently<fnref n="2" />, within the proof there are three distinct layers whose boundaries should stay crystal clear but are often confused. The first layer is syntactic and constructive, and is conducted outside of ZFC. It is a terminating algorithm that takes a ZFC proof of CH as input—as a string of letters—and converts it into a ZFC proof of contradiction. This layer can be conducted in a formal system such as Peano Arithmetic. The second layer is set theoretic, conducted within ZFC, and involves showing that theorems of ZFC can be reflected in a model M so that a ZFC proof of CH can be converted to a proof of CH within M. The third layer is again conducted within ZFC, and is the forcing construction within a model M “looking outside”. The set theoretic layers are highly non-constructive and involve transfinite constructions of sets with heavy use of the axiom of choice. Even so, seeing as syntax the proof is a fully specified terminating algorithm.

3. Third, the forcing construction itself is complex especially in the definition and motivation of *genericity*. This concept is usually introduced at the front without sufficient explanation or motivation, while its hidden purpose and power are made clearer later in the proof, when genericity allows defining the forcing relation that enables key ZFC axioms like Comprehension to be transferred from the model M to the bigger model $M[G]$. Here, I reverse the order of exposition from the end goal to the front: first motivate the need to transfer axioms “outside” M, and then introduce genericity as a natural way to accomplish that. Once this need to transfer axioms outside M is understood, one is *forced* to introduce genericity.

Once spelled out, the modular structure of the proof facilitates its understanding. First understand the main syntactic argument using forcing within ZFC as a black box, and separately understand the forcing construction.

**Recommended background for reading this manuscript.** The aim of this exposition is to require minimal background. Unfortunately, for this topic the minimal is still high: college-major-level mathematics or theoretical/algorithmic computer science is probably necessary. In addition, familiarity with first-order logic and especially with the classical theorems by Gödel—Incompleteness, Completeness and Compactness—is recommended. These results are highly accessible compared to the independence of CH. Readers are referred to background material on these topics (Kim B.<fnref n="3" />; Smith 2013; Nagel and Newman 2001; Stanford Encyclopedia of Philosophy<fnref n="4" />; Buildt 2014, Batzoglou 2021).

**Expositions of forcing and the continuum hypothesis.** Many excellent expositions of the independence of CH are available, even though most of them are aimed at the committed student of set theory or the specialist in the field. A few words on my self study of the topic may be helpful to a reader embarking in self study. After reading the respective chapters in Jech (2002)—an advanced comprehensive exposition of set theory that is probably not best for self study of forcing—I found Forcing for Mathematicians by Weaver (2014). The name says it all, and reading this brief book a couple of times made everything clear. Then I got additional insight by reading Smullyan and Fitting (2010). Additionally, Cohen's book (1966) is highly readable and clear. The highly readable high-level exposition by Chow (2007) might be a good place to start. Other references that are considered outstanding are Bell (1977) and Kunen (1980). The exposition here most closely follows the one by Weaver: the syntactic approach of introducing a symbol M postulated to be a countable transitive model, as well as the choices of foregoing Boolean algebras in favor of posets and using generic ideals rather than generic filters, are in my opinion excellent choices that clarify the presentation. In addition, I blend in useful elements from Smullyan and Fitting (2010) and Cohen (1966), reverse some of the order of the presentation to motivate the defined structures and especially genericity, and provide examples and discussion to help the reader absorb the concepts and proofs.

## 2 Overview

This section provides an overview of basic background material and a summary of the proof of independence of CH. The aim is to give the reader a lay of the land before delving into the long exposition in Sections 3 and 4.

<footnote n="2">²https://scottaaronson.blog/?p=4974</footnote>

<footnote n="3">³https://web.yonsei.ac.kr/bkim/goedel.pdf</footnote>

<footnote n="4">⁴https://plato.stanford.edu/entries/goedel-incompleteness/</footnote>
## 2.1 Levels of Infinity and the Continuum Hypothesis

A set A is bigger than a set B when there is no way to pair every element of A with a distinct element of B. Formally, a function $f: A \to B$ is 1-1 or an *injection* if distinct elements of A map to distinct elements of B; a *surjection* if every element of B is the image $y = f(x)$ of some element $x$ of A; and a *bijection* if it is injective and surjective. A bijection between A and B establishes that they are of the same size, while if no surjection exists then $|A| < |B|$. This is obvious for finite sets, and the same notion applies to infinite sets.

*Infinity comes in different sizes, and set theory can be thought of largely as the study of infinity.*

Importantly, a set is **countable** if there is a surjection from $\mathbb{N}$ to the set. Let's see some examples of countable sets:

* $\mathbb{N}^2 = \{(i, j) | i, j \in \mathbb{N}\}$. One simple way to enumerate $\mathbb{N}^2$ is (0, 0), (0, 1), (1, 0), (0, 2), (1, 1), (2, 0), (0, 3), ... by going through all pairs of sum 0, 1, 2, ... successively. Similarly, $\mathbb{N}^k$ is countable for any $k \in \mathbb{N}$: just enumerate the $k$-tuples of sum 0, 1, 2, 3, ... in order.

* A countable union of countable sets is countable. Let $A_1, A_2, A_3, \dots$ be countable sets. Each $A_i$ can be enumerated, $a_{i1}, a_{i2}, \dots$. Enumerate all of them in stages: at stage $k$ enumerate the $k$th element of sets $A_1, \dots, A_{k-1}$ followed by the first $k$ elements of $A_k$: $a_{1k}, a_{2k}, \dots, a_{(k-1)k}, a_{k1}, \dots, a_{kk}$. Every element in $\bigcup_{i=1}^{\infty} A_i$ is $a_{kl} \in A_k$ for some $k, l$ and it is thus enumerated at stage $\max\{k, l\}$.<fnref n="5" />

* $\bigcup_{k=1}^{\infty} \mathbb{N}^k$ is countable because it is a countable union of countable sets.<fnref n="6" />

However, $\mathbb{R}$ is bigger than $\mathbb{N}$. This is Cantor's famous theorem and has a simple proof. Let $x_1, x_2, x_3, \dots$ be an enumeration of all members of (0, 1). Represent $x_i$ by $0.x_{i1}x_{i2}\dots$, in decimal, following the convention that $0\dots x_{ik}99999\dots$ is picked over $0\dots (x_{ik} + 1)00000\dots$. Now construct $y = 0.y_1y_2\dots$ as follows: if $x_{ii} = 1$ let $y_i = 2$ and if $x_{ii} \neq 1$ let $y_i = 1$. Then, $y$ cannot be in the list because it differs from $x_i$ in its $i^{th}$ digit, contradicting the assumption that the $x_i$ is completely enumerate (0, 1). Therefore (0, 1) and $\mathbb{R} \supset (0, 1)$ are not countable. The size of infinity represented by the real line is called the **continuum**, denoted by $c$. The following are examples of sets of size continuum:

* $|(0,1)| = |\mathbb{R}|$: $f = (2x-1)/(x-x^2)$ is a bijection between (0, 1) and $\mathbb{R}$.

* $|\mathbb{R}| = |\mathbb{R}^k|$. Can you think of a way to show that? Here is a sketch: first, map them to (0, 1) and $(0, 1)^k$, respectively. Then, write $x \in (0, 1)$ in decimal: $x = 0.x_1x_2x_3\dots$ where $x_i \in \{0, 1, \dots, 9\}$. Again follow the convention that among $0.x_1\dots x_k99999\dots = 0.x_1\dots(x_k+1)00000\dots$, with $x_k \le 8$, the former is picked. Finally, interleave digits. For example, $(0, 1)^2$ maps to (0, 1) by mapping $(x, y) = (0.x_1x_2\dots, 0.y_1y_2\dots)$ to $0.x_1y_1x_2y_2\dots$.<fnref n="7" />

* $|\mathbb{R}| = |\mathbb{R}^\mathbb{N}|$. There is a bijection between $\mathbb{R}$ and the set of tuples $(x_1, x_2, \dots)$ with each $x_i \in \mathbb{R}$: first map $\mathbb{R}^\mathbb{N}$ to $(0, 1)^\mathbb{N}$. Then, each $(x_1, x_2, \dots)$ can be thought of as a $\mathbb{N} \times \mathbb{N}$ table of single digits $[x_{ij}]$ with $i, j \in \mathbb{N}$. By using the map from $\mathbb{N}$ to $\mathbb{N}^2$ just wrap those digits to a single sequence of digits $y_1, y_2, \dots$ that represents a single real number in (0, 1).

* $\mathcal{N} := \omega \to \omega$, the set of functions from $\omega$ to $\omega$, also known as the Baire space. It is easy to see that $|\mathcal{N}| = |\mathbb{R}|$; the members $r \in \mathcal{N}$ are infinite sequence over $\mathbb{N}$ and are often called reals.

Two concepts are key for measuring infinity: the concepts of ordinal and cardinal. Those concepts are covered in Section 3.2. For now, it suffices to say that ordinals are a way of counting past $\mathbb{N}$, in the following sense. Denote $\mathbb{N}$ with $\omega$ as is customary when we think of it as an ordinal. Its successor is defined to be $\omega + 1 := \omega \cup \{\omega\}$. This successor operator $x + 1 := x \cup \{x\}$ can be applied repeatedly to yield $\omega + 2, \dots, \omega \cdot 2 := \{0, 1, \dots, \omega, \omega + 1, \dots\}$, and continue to $\omega \cdot 3, \dots, \omega^2, \dots, \omega^3, \dots, \omega^\omega, \dots$, each of these sets being distinct from each other and well ordered. **Cardinals** are a way of sizing infinity;

<footnote n="5">⁵Note that to enumerate the sets, the axiom of countable choice is used.</footnote>

<footnote n="6">⁶Similarly, $\bigcup_{l=1}^{\infty} (\bigcup_{k=1}^{\infty} \mathbb{N}^k)^l$ is countable because it is a countable union of countable sets. Each of its member is an $l$-tuple $(w_1, \dots, w_l)$ where each $w_i$ is a $k$-tuple of elements $(n_1, \dots, n_k)$ where $n_j \in \mathbb{N}$, and $k_i : 1 \le i \le l$ and $l$ are all arbitrary $\in \mathbb{N}$. The above process can continue for $m$ steps $\bigcup_{i=1}^{\infty} ((\dots((\bigcup_{l=1}^{\infty} \mathbb{N}^k)^{l_1})\dots))^{l_m}$ for any $m$, yielding a countable set, call it $N_m$. The union of all these has a special name, $\varepsilon_0 := \bigcup_m N_m$ and is a countable union of countable sets, therefore countable.</footnote>

<footnote n="7">⁷Interleaving infinite decimals is a bit tricky. For example, de-interleaving 0.94040404... leads to 0.90000...., which is not allowed. It is a bit cumbersome but not hard to deal with this subtlety.</footnote>
for cardinals $κ, λ$ we say $κ < λ$ when there is no surjection from $κ$ to $λ$ (and consequently, there is a surjection but no bijection from $λ$ to $κ$).

**The power set.** Given any set $S$, the set of all its subsets is called the power set of $S$, denoted by $P(S)$ or by $2^S$, the latter notation emphasizing the equivalence between a subset and a function $g: S \to \{0, 1\}$ that chooses which elements of $S$ to include in the subset. $P(S)$ is always larger than $S$: assume for contradiction that there is a bijection $f: S \to P(S)$. Consider the subset $D$ of $S$ of elements that do not belong to their image under $f$: $D = \{s \in S \mid s \notin f(s)\}$.<fnref n="8" /> Since $f$ is a bijection, let $d \in S$ be the unique element such that $f(d) = D$. Is $d$ a member of $D$? Well, if $d \notin D$, then $d \notin f(d)$ so it satisfies the condition for being in $D$. But if $d \in D$, then $d \in f(d)$ so it does not satisfy the condition of being in $D$. This is a contradiction, therefore $f$ cannot be a bijection.

Therefore, the power set is always bigger than the original set. Infinite cardinals are ordered: $\aleph_0 = \omega, \aleph_1, \aleph_2, \dots, \aleph_\omega, \dots$. The *continuum hypothesis (CH)* states that there is no infinity strictly between $\mathbb{N}$ and $\mathbb{R}$, more commonly stated as $2^{\aleph_0} = \aleph_1$. The *generalized continuum hypothesis (GCH)* states that there is no infinity strictly between an infinite set and its power.

So, is there a set of size between $\mathbb{N}$ and $\mathbb{R}$? This is a simple question that ought to have a clear answer. Astonishingly, the question is independent of the rest of mathematics: if either case is proven, the proof can be converted to a proof of contradiction by a complex but well-defined algorithm. One thing becomes immediately clear: no set $S$ can be described mathematically and demonstrated to be between $\mathbb{N}$ and $\mathbb{R}$. In that sense, such a set does not exist. However, the existence or non-existence of such a set can be made into a new axiom that introduces no new contradiction to existing axioms, and which alters the properties of $\mathbb{R}$.

## 2.2 Outline of this manuscript

An outline/summary of the manuscript is provided below. *It is not self-contained* so some readers may wish to skip to Section 3.

Starting in Section 3, the manuscript covers preliminary background on axiomatic set theory, including the formulation of infinity in the concepts of ordinals and cardinals and the formulation of the universe(s) of sets, and model theory, or how to define mini-universes of elements (such as numbers, fractions, and in our case sets) that obey a collection of axioms. Readers familiar with the ZFC axioms, ordinals, cardinals, sets and classes, relativization and reflection, are welcome to skip these sections.

**Set theory.** Section 3.1 covers basic axiomatic set theory. All ordinary mathematics can be formalized using the versatile concept of a set. Familiar entities such as numbers, vector spaces, groups, graphs, and functions and relations over them, can all be expressed as sets. A collection of axioms that formalize the notion of a set can serve as a foundation of all mathematics. One such axiomatization is the Zermelo-Fraenkel set theory with the Axiom of Choice (ZFC). It includes the standard first-order logical axioms and inference rules, plus set-theory-specific axioms: seven axioms and two axiom templates that take as input a formula $\phi$ and generate an axiom where $\phi$ is a substring.<fnref n="9" /> In this way, ZFC is an infinite but compactly described (recursive) collection of axioms that specify properties of sets, upon which all mathematical concepts can be built.

Section 3.2 covers the basic concepts of ordinals and cardinals. The brief Section 3.3 covers the concept of proper class: a collection of sets that satisfy a ZFC formula that is "too large" to be a set. The collection of all ordinals is a canonical example of a proper class. In that section, the universe of sets as a "cumulative hierarchy" and the rank of each set within this hierarchy are also defined.

**Models.** Section 3.4 covers basic model theory. A model for a collection of axioms is a set together with an interpretation of the constants, functions and relations mentioned in the axioms within the set: constants are mapped to elements of the model, and functions and relations are mapped to functions and relations across the elements of the model. For example, consider the axioms of group theory: (1) associativity: $\forall x \forall y \forall z (x \cdot y) \cdot z = x \cdot (y \cdot z)$; (2) identity: $\forall x e \cdot x = x \cdot e = x$; (3) inverse:

<footnote n="8">⁸$D$ is always a subset of $S$ and thus a member of $P(S)$. If there is no $s$ in $D$, then $D$ is $\emptyset \in P(S)$, and therefore $f$ has to cover it.</footnote>

<footnote n="9">⁹The need for a separate axiom for every formula stems from a desire for all quantifiers to quantify over sets. A finite axiomatization would require quantifying over properties over sets, i.e., formulas. ZFC cannot "talk" about formulas.</footnote>
$\forall x \exists x^{-1} x \cdot x^{-1} = x^{-1} \cdot x = e$. $\mathbb{Z}$ is a model of group theory if the identity $e$ is mapped to 0, the function $\cdot(x, y)$ is mapped to $x + y$, and the inverse of $n$ is $-n$. The finite groups $\mathbb{Z}_n$ of addition modulo $n$ provide infinitely many additional models. Countless other models exist such as $I_h = A_5 \times \mathbb{Z}_2$, $SO(2)$ and $GL(n, \mathbb{R})$. Importantly, every logically consistent collection of axioms has a model. This is the famous Gödel completeness theorem. In this manuscript, a more specific result will play a key role: any finite consistent collection of axioms involving the $\in$ relation$^{10}$ admits a countable transitive set model $M$: a countable set $M$ such that whenever $x \in y \in M$ then $x \in M$. This result is called a **reflection principle** because the finite collection of axioms is **reflected** in the set $M$. As we will see, the reflection principle is not hard to prove but its use can be counter-intuitive and confusing. In the case of independence of CH, the subject matter is existence of uncountable sets and thanks to the reflection principle uncountability will be reflected/modeled within a countable set $M!$ This subtle point will be made clear in Section 3.4. Briefly, the definition of a set $S$ being “uncountable” within $M$ is that there is no function $f \in M$ that is a bijection from $\mathbb{N}$ to $S$.¹¹ Therefore, a set $S \in M$ can be countable “in reality” but uncountable with respect to $M$. This property will be key to a devious construction that explores it to “break” CH.

The statement that a given $S$ is uncountable is a ZFC formula Uncountable($x$) taking a single argument. To say that a set $S$ is uncountable within $M$, we **relativize** the formula Uncountable($x$) to $M$ by changing the "there is no surjection $f$ from $\mathbb{N}$ to $S$" to "there is no surjection $f \in M$ from $\mathbb{N}$ to $S$".

**Notation.** For every formula $\phi$, we denote by $\phi^M$ its version **relativized** to $M$ where all variables take values from $M$. Then $\aleph_1^M$, $\aleph_2^M$ and $(2^{\aleph_0})^M$ are the sets within $M$ that satisfy the formulas $\psi^M$ where $\psi$ is the formula that defines the properties of the corresponding set.

In the long Section 4, the manuscript outlines the proof of the independence of CH, omitting some details but covering all the technically and conceptually challenging parts, with commentary that is aimed at the non-specialist reader. A brief non self-contained summary follows here; concepts mentioned in this summary will be fully exposed in Section 4.

**Concluding sections.** Section 5 provides a bullet-point review of the proof so that the reader anchors the big picture in a summary format. Section 6 covers two key proofs that were omitted in the main exposition—the model-theoretic preliminary of Reflection including the Mostowski Collapse, and the proof of the consistency of CH using forcing. Section 7 covers alternative ways to prove independence of CH; all these alternatives use a form of forcing, so in a sense there is only one grand proof. Section 8 concludes with my personal remarks on lessons learned.

## 2.3 Non self-contained summary of the proof

The following summary provides a high-level map of the proof. Some readers may find this a useful introduction to the main structure and ideas of the proof. However, it is not self contained and many concepts will only become clear in the main exposition, so the reader can optionally skip to Section 3.

Assume for contradiction that there is a proof of CH. A proof is a list of formulas $\phi_1, \dots, \phi_n = \text{CH}$ that are either axioms or logical consequences of previous formulas in the list. The axioms in this list, plus finitely many additional axioms that will be needed, are all collected in a list that we may denote again by $\phi_1, \dots, \phi_k$. Using the Reflection Principle some countable transitive set $M$ reflects them. Therefore, CH is provable within $M$. CH says that $2^{\aleph_0} = \aleph_1$. Within $M$, these uncountable sets are represented by countable ordinals that are uncountable in $M$. Therefore there is a $(2^{\aleph_0})^M$ set, a $\aleph_1^M$ set, and so on. Each of these sets is a countable set that is uncountable in $M$ in the sense that there is no bijection in $M$ from $\aleph_0$ to that set. (As it turns out, $\aleph_0^M = \aleph_0$.) Now comes the fun part. Because $M$ is countable, we can expand it in some drastic ways: because $\aleph_2^M$ is countable, there exist $\aleph_2^M$-many distinct subsets of $\aleph_0$ that are not in $M$. Let $G$ denote a table of $\aleph_2^M$-many distinct rows, each of which is a subset of $\aleph_0$ not in $M$. Attaching $G$ to $M$ will not result in a model immediately, because $M \cup \{G\}$ will be missing new sets that are definable by the set theory axioms (covered in Section 3.1) using $G$ as a parameter. The idea is to attach $G$ as well as additional subsets so that the new expanded set, call it $M[G]$, is a model of ZFC.$^{12}$ Moreover, it should be ensured that $\aleph_2^{M[G]}$ is equal to $\aleph_2^M$ in the sense that the same exact countable

<footnote>$^{10}$The specific property needed from $\in$ here is extensionality: $x$ and $y$ are equal if and only if for all $z$, $z \in x$ if and only if $z \in y$.</footnote>

<footnote>$^{11}$If $M$ is a model of ZFC, then $\mathbb{N} \in M$.</footnote>

<footnote>$^{12}$Actually, it suffices that it is a model of the axioms required in the hypothesized proof of CH.</footnote>
ordinal plays the role of the second smallest uncountable infinity in both $M$ and $M[G]$. Extending $M$ with $G$ while making sure that the finite list of axioms we started with still provably hold in $M[G]$ is super delicate, and is done by a technique called **forcing**. Once this is accomplished, within $M[G]$ it is simultaneously true that $(2^N)^{M[G]} \ge \aleph_2^{M[G]}$ and also $CH^{M[G]}$, which says $(2^N)^{M[G]} = \aleph_1^{M[G]} < \aleph_2^{M[G]}$, a contradiction.

*The independence proof is an algorithm whose input is a ZFC proof of CH or "not CH" and whose output is a ZFC proof of contradiction.*

**The proof comes in two main parts:** (1) the logical part whereby a proof of CH (or $\neg$CH, which we will cover after the main exposition) is relativized to a countable transitive set $M$; (2) the forcing part of extending $M$ by adding the table $G$ of $\aleph_2^M$-many distinct rows, defining $M[G]$ that contains $M$ and $G$ as well as additional sets, and then showing that the resulting expanded set $M[G]$ is a model of the axioms used in the hypothesized proof of CH. The logical argument is not technically hard. However, it is a nasty source of confusion. The argument is carried out outside ZFC. It is an argument **about** the axioms of ZFC that can be expressed in informal mathematical language or carried out formally in Peano Arithmetic (PA). Importantly, it defines a terminating algorithm whose input and output are ZFC proof syntax. The forcing argument (2) is technically much harder. It is conducted within ZFC. It has different layers of “truth”: because of the models $M$ and $M[G]$, any sentence $\phi$ has in principle different truth values as $\phi$, $\phi^M$, and $\phi^{M[G]}$. For example $(2^N)^M$ is countable and at the same time uncountable$^M$. The proof breaks $CH^M$ not CH. This last point can be confusing and even infuriating. Nothing is concluded about the “true” truth value of CH. All that is shown is that if a proof of CH existed, the axioms used in the proof would cogently hold within a countable transitive set $M$, then an extension $M[G]$ would be demonstrated where the same axioms hold, and proofs of $CH^{M[G]}$ as well as $\neg CH^{M[G]}$ would go through resulting in contradiction. Does this mean that CH cannot hold? Not really. For example, CH can be appended as an axiom. Then the axiom can hold as $CH^M$ in a countable transitive $M$, and $M$ can be extended to $M[G]$ as before, but then the $CH^M$ axiom will not carry to $CH^{M[G]}$ so the “proof” of CH—a one-liner just stating the axiom—will not carry to $M[G]$ and no contradiction will ensue.

**Expanding the ground model with new subsets of $\aleph_N$.** In the second part, the ground model $M$ is expanded with a table $G$ that encodes $\aleph_2^M$-many distinct subsets of $\aleph_0$ that are not in $M$. For the resulting set $M[G]$ to be a model of ZFC it has to include all sets that are constructible from sets in $M$ combined with $G$. One way to construct new subsets is by taking preimages under $G$ as follows. $G$ is a table of $\aleph_2^M \times \aleph_0$ entries 0/1, each $(\alpha, k)$ entry indicating whether the $\alpha$th subset of $\aleph_0$ contains (1) or doesn't contain (0) element $k$. This table is not in $M$, however every finite subset of it is in $M$ because every model contains every finite set (and incidentally it also contains every Turing machine and every recursive function). Those finite subsets of $G$ are part of a larger collection that is in $M$, the collection of all finite subsets of any $\aleph_2^M \times \aleph_0$ 0/1 table, and $M$ does not know which ones are the former.$^{13}$ Let's denote by $\mathbb{P}$ the collection of finite fragments of any 0/1 table of size $\aleph_2^M \times \aleph_0$. Now, consider any element $x$ in $M$, and any relation $r$ in $M$ that is a subset of $x \times \mathbb{P}$. The preimage of $r$ by $G$, i.e., all elements $(y,p)$ of $x \times \mathbb{P}$ that are in $r$ and such that $p \subset G$, should also be in $M[G]$ because $M[G]$ has the $G$ “key”. This preimage operation can be repeated infinitely many times and all the results need to be in $M[G]$ if $M[G]$ has any hope of being a model. This need motivates the definition of $M[G]:$ it is precisely the collection of all such preimages. At first glance it would be wishful thinking that such a simple definition of $M[G]$ should work, and miraculously it does.

**Forcing the expanded set to be a model.** The next task is to show that $M[G]$ defined thus is a model. The desired property for $M[G]$ is that for every axiom of ZFC relativized to $M$, $\phi^M$, there is a ZFC proof of $\phi^{M[G]}$. To achieve that for certain strong axioms $\phi$ such as Comprehension, $\phi^M$ should be invoked to derive $\phi^{M[G]}$. However, when invoking $\phi^M$, there is no access to $G$; only to finite parts $p \in \mathbb{P}$ of $G$. So it turns out that to invoke $\phi^M$ to prove $\phi^{M[G]}$, the truth of $\phi^{M[G]}$ has to be decided on whether some finite $p \in \mathbb{P}$ is in $G$. Such a $p$ is said to **force** $\phi^{M[G]}$. This requirement immediately leads to the concept of genericity of $G$: because each property of $G$ is conferred by some finite $p \in M$, all properties of $G$ are generic with respect to $M$: no specific infinite “AND” of new properties can be formed. An infinite “AND” encoding a specific new property in $G$ not present in $M$, such as for example a specific new subset (as opposed to an unspecified, generic new subset), or the equality between two specific rows of $G$, would

<footnote>$^{13}$The expression "*M* does not know" is anthropomorphism for the syntactic fact that no statement pertaining to subsets in *G* relativizes to *M* and no set that isolates these subsets is a member of *M*.</footnote>
correspond to a sentence $\phi^{M[G]}$ that cannot be made true or false based on a finite $p \in M$. Genericity of $G$ is defined elegantly in terms of the concept of density of subsets of $\mathbb{P}$. $G$ is defined to be generic if it meets every dense subset $D \subset \mathbb{P}$, $D \in M$ with some $p \in D$ that is a subset of $G$, because to avoid $D$ would require the truth of a new infinite “AND”. It is then proven that a generic $G$ exists as long as $M$ is countable. And that’s why we insist on countable models. The relation between a sentence $\phi^M$ and the parts $p$ whose presence in $G$ ensures the corresponding sentence $\phi^{M[G]}$ is true is called the *forcing relation* in $M$. A key theorem shows that every sentence of $M[G]$ is forced true or false by the forcing relation in $M$. Based on that theorem, with some technical but not difficult proofs, $M[G]$ is shown to reflect the same list of axioms $\phi_1, \dots, \phi_k$, so that the $CH^{M[G]}$ proof goes through. At the same time it is shown that there are at least $N_2^{M[G]}$ subsets of $N_0$ in $M[G]$, which is a contradiction. This part of the proof utilizes an elegant argument involving combinatorics of infinite sets. The conclusion is that there cannot be a proof $\phi_1, \dots, \phi_n = \text{CH}$.

# 3 Preliminaries—Set Theory, Ordinals, Cardinals and Models

This section covers concepts that are prerequisite to understanding the proof of independence of CH in a manner meant to be intuitive and assuming minimal background: (1) ZFC, which axiomatizes the notion of a set, a versatile concept upon which all familiar mathematical structures can be built; (2) ordinals and cardinals, notions that enable “counting” beyond $N$ and comparing different sizes of infinity; (3) models and their ability to reflect the axioms of set theory.

## 3.1 Axiomatic Set Theory

Sets are a versatile concept that can represent any familiar mathematical structure. For example, numbers can be represented as sets by letting each number be the set of all smaller numbers, with 0 being the set $\emptyset = \{\}$. Ordered pairs $(x, y)$ can be represented as sets $\{{\{x\}}, \{x, y\}\}$ and sequences $(x_1, x_2, \dots, x_k)$ as nested pairs $(x_1, (x_2, (\dots, x_k)\dots))$. Functions $f: X \to Y$ can be represented as sets of ordered pairs $(x, y)$ with $x \in X$, $y \in Y$ such that for every $x$ in $X$ there is precisely one $(x, y)$ in $f$; $k$-ary relations over $X$ can be represented as subsets of $X^k$. Because of the versatility of sets, set theory has been the go-to notion as a foundation of mathematics.

However, defining what a set is is tricky. In 1901, Bertrand Russell posed his famous paradox, “the set of all sets that are not members of themselves” (and the “barber who shaves all those, and those only, who do not shave themselves”). Call this set $x$. Is $x$ a member of itself? A moment’s reflection reveals that $x$ is a member of itself if and only if $x$ is not a member of itself, a contradiction. Clearly, the notion of what a set is cannot be unconstrained.

To remedy such paradoxes, in 1908 Earnst Zermelo proposed the first axiomatic set theory. The axioms laid out constrained the notion of a set enough so as to avoid self-referential paradoxes like Russell's barber. However, as was discovered later by Abraham Fraenkel and others, the axioms were not powerful enough to yield certain sets whose existence was commonly assumed by mathematicians. After additions of axioms by Fraenkel, John von Neumann and others, the Zermelo-Fraenkel theory (ZF) with the Axiom of Choice (AC), commonly known as ZFC, was settled on. ZFC is designed to be powerful enough to prove the existence of all kinds of sets commonly assumed by mathematicians, but to refrain from constructs that lead to contradiction.<fnref n="14" />

In this section we will go over the formal axioms of ZFC, their meaning, and how they can be utilized to express familiar mathematical concepts. But first a few words on formal axiomatic systems.

### 3.1.1 Formal languages and proofs

Mathematicians typically write proofs in informal English interleaved with mathematical formulas. Informal proofs are understood to be shorthand for formal proofs that can be conducted entirely within a

<footnote n="14">¹⁴Many alternative axiomatizations exist. The von Neumann-Bernays-Gödel set theory (NBG) is an extension of ZFC that allows classes in addition to sets. Classes are collections of elements that are defined by a property—a formula—but which may be too big to form a set. Morse-Kelley set theory goes further, allowing classes to be defined by a property that has quantifiers that range over classes. The topic is rich and extensive, and beyond the scope here. For a review see the Stanford Encyclopedia of Philosophy (https://plato.stanford.edu/entries/settheory-alternative/).</footnote>
formal axiomatic system. Every proof is in principle machine-verifiable, otherwise it is not a proof.

A formal axiomatic system consists of a **language** of symbols and syntactic rules with which two types of objects can be composed: **terms**, which refer to objects in the domain and can be thought of as words of the language, and **formulas**, which are mathematical assertions and can be thought of as phrases of the language. Terms and formulas may contain free (input) variables, so their value can vary: terms with no free variables evaluate to a single item in the domain and formulas with no free variables—the **sentences** (also known as *statements*)—evaluate to true or false.<fnref n="15" /> A finite collection of **axioms** or axiom schemas (templates that capture a family of axioms) specify all the formulas that can be taken for granted.

**Logical axioms and inference rules.** Standard first-order logical axioms accompany the domain-specific axioms of a formal language. Many different axiomatizations of first-order logic are essentially equivalent.<fnref n="16" /> Then, **logical inference rules** specify how to derive a new formula from previous formulas. Again, there are many equivalent sets of inference rules, although some care needs to be taken that the inference rules interact well with the logical axioms and no contradictions are created.<fnref n="17" /> All such inference systems are complete in making all logically valid inferences (in one or more steps), a fact that we will take for granted.<fnref n="18" />

**Proofs within a formal system.** A **proof** of a formula $\phi_k$ is simply a list of formulas, $\phi_1, ..., \phi_k$ such that each $\phi_i$ either is an axiom or is logically derived from previous formulas in the sequence. A formula $\phi$ is a **theorem** of the language $\mathcal{L}$, denoted $\mathcal{L} \vdash \phi$ when there is a proof $\phi_1, ..., \phi_k = \phi$ of $\phi$. The validity of a proof can be syntactically checked by a mechanical procedure. Equivalently, the language and the proofs can be **arithmetized**, a procedure devised by Gödel that turns the question of validity of proofs into an arithmetic statement: “$\phi_1, ..., \phi_k$ is a valid proof of $\phi_k$” becomes “the number $\lceil (\phi_1, ..., \phi_k) \rceil$ is an encoding of a syntactically valid sequence of formulas that constitute a valid proof of the formula encoded by the number $\lceil \phi_k \rceil$”. Here, $\lceil s \rceil$ is meant to be a function that turns a string $s$ into a number. Readers not familiar with Gödel’s arithmetization and the incompleteness theorems may want to read on the topic and understand the theorem statement and scope as well as the proof idea before reading this manuscript (Kim B.<fnref n="19" />; Smith 2013; Nagel and Newman 2001; Stanford Encyclopedia of Philosophy<fnref n="20" />; Buildt 2014; Batzoglou 2021). CH is a prime example of the incompleteness phenomenon. Moreover, expression of recursive functions in Peano Arithmetic, which is a key component of Gödel’s incompleteness theorem’s proof, has great similarity to transfinite recursive definitions at the heart of ZFC. Such definitions are used heavily in the subsequent sections, including defining the universe of sets $V$, the class of names $N$, and the forcing-equality relation $\text{Force}^=$. Studying the proof of Gödel’s first incompleteness theorem is a good warm-up and a soft prerequisite for reading this manuscript.

<footnote n="15">¹⁵For example, with $\mathbb{R}$ as the domain $+, \cdot$ as binary operators and $>$, $<$, $=$ as binary predicates, 2.718, $2\pi r$, and $(x+y)^2$ are examples of terms; $1+1=2$, $x>y$, $\forall x \forall y (x+y)^2 = x^2+2xy+y^2$, $x < y+1$ are examples of formulas. The first and third are true sentences, the second is a formula whose truth depends on $x$ and $y$, and the fourth is a true formula with free variable $x$.</footnote>

<footnote n="16">¹⁶The following one is from the exposition of forcing by Weaver (2014):</footnote>

<footnote n="1">1. $\phi \rightarrow (\psi \rightarrow \phi)$</footnote>

<footnote n="2">2. $(\phi \rightarrow (\psi \rightarrow \chi)) \rightarrow ((\phi \rightarrow \psi) \rightarrow (\phi \rightarrow \chi))$</footnote>

<footnote n="3">3. $(\neg\phi \rightarrow \neg\psi) \rightarrow (\psi \rightarrow \phi)$</footnote>

<footnote n="4">4. $(\forall x(\phi \rightarrow \psi)) \rightarrow (\phi \rightarrow \forall x\psi)$, where $\phi$ is a formula that does not contain any free occurrences of $x$.</footnote>

<footnote n="5">5. $\forall x(\phi(x)) \rightarrow \phi(t)$ where $t$ is a term that does not share any variables with $\phi$.</footnote>

<footnote n="17">¹⁷The following three inference rules are in Weaver (2014): (1) from $\phi$ and $\phi \rightarrow \psi$ we can derive $\psi$; this principle is known as *modus ponens*. (2) From $\phi$ we can derive $\forall x\phi$ for any variable $x$, whether it appears in $\phi$ or not; this is *universal generalization*. In some systems it needs to be restricted to variables not free in $\phi$, depending on how it combines with other axioms and inference rules to potentially lead to contradictions. (3) From $\phi$ we can derive any $\phi'$ that constitutes a renaming of the variables of $\phi$. A renaming $\rho$ of variables is one where $\rho(x) \neq \rho(y)$ iff $x$ and $y$ are different variables. This avoids disasters like renaming $x < y \rightarrow \exists z (x+z=y)$ to $a < b \rightarrow \exists b (a+b=b)$.</footnote>

<footnote n="18">¹⁸For example, if we know $\phi$ and $\psi$ we can derive $\phi \land \psi$, if we know $\phi \rightarrow (\psi \lor \chi)$ then $\phi \rightarrow \psi$, and $\forall x \phi(x)$ implies $\phi(t)$ for any term $t$ that does not contain variables appearing in $\phi$.</footnote>

<footnote n="19">¹⁹https://web.yonsei.ac.kr/bkim/goedel.pdf</footnote>

<footnote n="20">²⁰https://plato.stanford.edu/entries/goedel-incompleteness/</footnote>
### 3.1.2 The axioms of ZFC

In the subsequent exposition we will assume that every item in the mathematical world is a set. This is not a necessary assumption in ZFC: for instance we could allow the existence of atoms (apple, orange, banana, Agamemnon, Julius Caesar, Cleopatra) that are not sets but can belong to a set. This generalization adds no power because all such atoms can be tokenized with numbers IDs and numbers can be represented as sets. So we will simplify and assume everything is a set.

The language of ZFC consists of the logical symbols $\wedge$, $\neg$, and $\forall$ from which additional familiar symbols $\vee$, $\to$, $\leftrightarrow$, $\exists$, $\exists!$, can be defined as shorthand<fnref n="21" />, the binary predicates $=$ and $\in$ from which other predicates such as $\notin$, $\ne$, $\subset$, $\subseteq$, connectors such as $\cap$, $\cup$ and abbreviations $\forall x \in y$, $\exists x \in y$ can be defined<fnref n="22" />, and a countably infinite collection of variables $x_0, x_1, x_2, \dots$. When we use “$x, y, z, \dots$” within formulas, those are meant to represent one of the valid variables $x_i$ of the language. Terms of ZFC are very simple: they are just the variables. Formulas are defined recursively to be either a ground formulas $x \in y$ and $x = y$ where $x, y$ are terms, or composites $\phi \wedge \psi, \neg\phi, \forall x \phi$ and so on, where $\phi, \psi$ are formulas and $x$ is a variable.

The axioms of ZFC include: (1) the standard first order logical axioms; (2) two axioms for equality: $x = y \rightarrow (x \in z \rightarrow y \in z)$ and $x = y \rightarrow (z \in x \rightarrow z \in y)$; (3) the domain-specific axioms presented below.

There are many equivalent formulations of ZFC. The following one is similar to the one by Kunen (1980). Notice that most of the axioms postulate the existence of a certain set. The aim is to make the notion of a set as expansive as possible while avoiding self-referential contradictions.

1. **Extensionality.** Two sets are equal if and only if they have the same elements. $\forall x \forall y (\forall z (z \in x \leftrightarrow z \in y) \leftrightarrow x = y)$.

2. **Pairing.** For any two sets, there exists a set that contains them as members. $\forall x \forall y \exists z (x \in z \wedge y \in z)$.

3. **Union.** For any set, the union of all its member sets is a set. $\forall x \exists u \forall y (y \in u \leftrightarrow (\exists z (y \in z \wedge z \in x)))$.

4. **Power.** For any set, there is a set of all its subsets. $\forall x \exists y \forall z (z \subseteq x \leftrightarrow z \in y)$.

5. **Infinity.** There is a set with infinitely many members. $\exists x (\exists e (\forall yy \notin e) \wedge e \in x \wedge (\forall z (xz \cup \{z\} \in x)))$.

6. **Foundation.** Any nonempty set has a member with which it shares no members. $\forall x (x \neq \emptyset \rightarrow (\exists y (y \in x \wedge y \in x = \emptyset)))$.

7. **Schema of Comprehension.** Let $\phi(x, y, w_1, ..., w_k)$ be a formula. There is a set that contains all elements $x \in y$ that satisfy $\phi$, for any choices of set $y$ and parameters (sets) $w_i$. $\forall y \forall w_1 \dots \forall w_k \exists z (\forall x x \in z \leftrightarrow (x \in y \wedge \phi(x, y, w_1, ..., w_k)))$.

8. **Schema of Replacement.** The image of a set under a class function falls within a set. Let $\phi(x, y, A)$ be any formula with free parameters $x, y, A$, such that for every $x \in A$ there is a unique $y$ making $\phi$ true. The formula $\phi$ can be thought of as a function that takes $A$ as input and specifies some set $B$ replacing all elements $x$ of $A$ with the $y$ that makes $\phi(x, y, A)$ true. However, $\phi$ is not always a function because the domain over which $A$ ranges is not specified. Instead, $\phi$ is a class function, and the reason for the terminology will become clear in Section 3.3. For now, it suffices to consider $\phi$ as any formula of the requisite property. Then, the Replacement Schema asserts that $B$ is a set that contains all the elements $y$ that are the image of set $A$ under $\phi$. $\forall A [(\forall x \in A \exists! y \phi(x, y, A)) \rightarrow \exists B (\forall x \in A \exists y \in B \phi(x, y, A))]$.

9. **Axiom of Choice (AC).** Given a set of nonempty sets, there exists a function that picks one element from each member set. To write down the axiom, it is convenient to use some shorthand: $\text{Fun}(f)$ for the condition of $f$ being a function, $\text{Dom}(f)$, $\text{Ran}(f)$ for the domain and range of a function, respectively, $\bigcup x$ for the union of all sets in $x$, and $f(y)$ assuming $f$ is a function, for the unique $z$ s.t. $(y, z) \in f$. $\forall x (\emptyset \notin x \rightarrow \exists f (\text{Fun}(f) \wedge \text{Dom}(f) = x \wedge \text{Ran}(f) = \bigcup x \wedge \forall y \in x f(y) \in y))$.

Some formulations of ZFC introduce another axiom, that of the **Existence of the Empty Set**: $\exists e \forall w w \notin e$ or something equivalent. This is convenient but not needed because the existence of the

<footnote n="21">²¹For example $\phi \vee \psi$ is $\neg(\neg\phi \wedge \neg\psi)$, $\exists x \phi$ is $\neg\forall x\neg\phi$, and $\exists! x \phi$ is $\exists x (\phi \wedge \forall y (\phi \rightarrow y = x))$.</footnote>

<footnote n="22">²²For example, $x \subseteq y$ is defined as $\forall z z \in x \rightarrow z \in y$, $z = x \cap y$ is shorthand for $\forall w (w \in z \leftrightarrow w \in x \wedge w \in y)$, $\forall x \in y \phi$ stands for $\forall x x \in y \rightarrow \phi$ and $\exists x \in y \phi$ stands for $\exists x x \in y \wedge \phi$.</footnote>
empty set can be derived from Infinity and Comprehension. The proof sketch is included here as an example of how ZFC “works”.

**Existence of $\emptyset$—proof sketch.** Let us write Infinity in shorthand as $∃x \ Inf(x)$, and Comprehension as $∀y \ Comp(\phi, y)$ noting that this is a separate axiom for every formula $\phi$ that contains no free occurrences of variable $y$. Let $\phi(w) := w \neq w$. A ZFC proof is just a list of formulas. For this proof, let the first two formulas be $∃x \ Inf(x), ∀y \ Comp(w \neq w, y)$. A and $B$ implies $A \wedge B$ so let the third formula of the proof be $∃x \ Inf(x) \wedge ∀y \ Comp(w \neq w, y)$. Because $x$ does not appear to the right of $\wedge$, this implies $∃x (Inf(x) \wedge ∀y Comp(w \neq w, y))$. Instantiating the $∀y$ quantifier to $x$ yields $∃x (Inf(x) \wedge Comp(w \neq w, x))$. Let's unroll the “Comp” shorthand: $∃x ∃z (Inf(x) \wedge ∀w (w \in z \leftrightarrow (w \in x \wedge w \neq w)))$ (here, we also moved $∃z$ outside the parentheses as $z$ does not appear within $Inf(x)$). Because $A \wedge B$ implies $B$, we now get $∃x ∃z ∀w (w \in z \leftrightarrow (w \in x \wedge w \neq w))^{23}$. Now $x$ appears nowhere in the formula, so we can drop it: $∃z ∀w (w \in z \rightarrow w \neq w)$ which is easily shown to yield $∃z ∀w w \notin z$. $\square$

We can shorthand this to $∃z \ Empty(z)$ or $∃z z = \emptyset$. Whenever $\emptyset$ is used as a shorthand, it is understood that a proof such as the above precedes it. All sets are compositions of the empty set, as will become clear.

ZFC can be thought of as a rather low-level programming language. The syntax is kept to a minimum in order to reason about it precisely. Actually writing formal proofs in ZFC is extremely tedious but not needed in practice. Some remarks on the axioms:

**Extensionality** simply says that two sets are equal iff they have the same elements. That simplifies discourse. More generally, one could allow multiple distinct entities having the same elements, and then define a formula $EqualSets(x, y)$ to be true whenever $x, y$ have the same elements. The resulting theory would be usually more cumbersome, sometimes more convenient, and overall equivalent.

Notice that **Pairing** allows other elements beyond $x, y$ to be in $z$. That is fine because using Comprehension in conjunction with Pairing one can define precisely the pair $\{x, y\}$.

The **Power** axiom is powerful: it postulates the existence of the set of subsets of a set. This allows jumping from $N$ to continuum, and from there to much much larger infinities. It has been said that Power is way too powerful, and arguably it is the source of all trouble with infinities. The power set of a set $x$ will be denoted by $P(x)$ or $2^x$.

**Comprehension** and **Replacement** require some discussion. These are not individual axioms, but rather axiom schemas. For any formula $\phi$ of the language, a separate axiom is instantiated. They correspond to mathematician's statements such as "let $X$ be the set of all elements $x$ of $\mathbb{R}$ that satisfy property $P(x)$" (Comprehension) and "let $Y$ be the image of $X$ under function $f$" (Replacement). First-order logic does not allow variables ranging over properties, and this is why axiom schemas are needed. Ranging over properties is allowed in second-order logic and finite second-order axiomatizations of set theory are possible. Discussing the merits of first order logic and (mostly de-)merits of second-order logic is beyond the scope here. It suffices to understand that there is a separate Comprehension and a separate Replacement axiom for every formula $\phi$. Great care needs to be taken to avoid creating self-referential contradictions such as a "barber who shaves all those and those only who do not shave themselves". This is why Comprehension creates a set of all elements $x$ **within a set** $y$ that satisfy $\phi$. This simple condition prohibits circularity: assuming $y$ is a set and involves no circularity, $x$ involves no circularity. Similarly, Replacement creates a set out of the image of an **existing set**.

What about **Infinity**? Infinity postulates a set that contains $\emptyset$ and is closed under $x \mapsto \{x\}$. Given a set $J$ with this property as given by Infinity, we can then use Comprehension to take the intersection of all subsets of $J$ that also satisfy this property, and this intersection will be isomorphic to $\omega$. Without Infinity it would not be possible to prove that infinite sets exist.

**Foundation** is mostly cosmetic. It ensures that there are no downward chains of membership $\dots \in x_k \in x_{k-1} \in \dots \in x_2 \in x_1 \in x_0$. It grants no additional power to the theory, but makes certain proofs way easier.

<footnote n="23">²³Perhaps in more than one derivation step, depending on the precise set of deduction rules.</footnote>
Finally, the **Axiom of Choice** (AC) is a non-obvious axiom on which enormous literature exists. As it turns out, AC is itself independent of the other axioms of ZF, and a proof can be provided based on the forcing technique described in this manuscript. In fact there are axioms such as Determinacy that are contradictory with AC and could be appended to ZF as alternatives that lead to different mathematical results. Mathematicians often pay attention to the use of AC in proving a theorem.

## 3.2 Levels of Infinity: Ordinals and Cardinals

A set is *well ordered* if its elements are ordered and, importantly, if every nonempty subset contains a smallest element:

**Definition: well-ordered set.** A set $S$ is well ordered by a binary relation $< \text{ if:} (1) \text{ for any } x, y \in S, \text{ either } x < y \text{ or } y < x \text{ or } x = y; (2) \text{ if } x < y \text{ and } y < z \text{ then } x < z; (3) \text{ every subset of } S \text{ contains a smallest element.**

The natural numbers, $\mathbb{N}$ are well ordered. However, the real numbers $\mathbb{R}$ are *not* well ordered by the natural relation $<$ because there are subsets such as $(0,1)$ that do not contain a smallest element. Requiring that every subset contains a smallest element (an *infimum*) is a powerful condition. Every set can be well ordered as can be shown with the axiom of choice. Conversely, if every set can be well ordered then it is easy to prove the axiom of choice by defining a function that picks the infimum of each set in a collection of sets.

Given a set $S$ well ordered by $<$, the order type of $S$ is the graph induced by $<$. As an example, let $S = \mathbb{N} \cup \{\text{Julius, Augustus, Cleopatra}\}$ and let $n < \text{Julius} < \text{Augustus} < \text{Cleopatra}$ for all $n \in \mathbb{N}$. The resulting graph is $0 < 1 < 2 < \dots < \text{Julius} < \text{Augustus} < \text{Cleopatra}$. This is a different order type from the graph $0 < 1 < 2 < \dots$ even though both sets are countably infinite.

As another example, what is the order type of $\mathbb{N}^2$? This depends on the induced order. For example, we can order $\mathbb{N}^2$ lexicographically: $(a,b) < (c,d)$ iff $a < c \lor (a = c \land b \le d)$. Then, the order type is $(0,0) < (0,1) < \dots < (1,0) < (1,1) < \dots < \dots < (n,0) < (n,1) < \dots$. If instead we order $\mathbb{N}^2$ by $(a,b) < (c,d)$ iff $a+b < c+d \lor (a+b = c+d \land a \le b)$ then the order type is same as that of $\mathbb{N}$, as a moment's reflection will reveal.

Ordinals are a way to express the notion of order type. They can be thought of as a way of counting past infinity. The cleanest definition of ordinals is by von Neumann:

A set $S$ is **transitive** if every member $x \in S$ is a subset $x \subset S$. A set $\alpha$ is an **ordinal** if it is transitive and well-ordered by $\in$.

This definition leads to a way of representing numbers in $\mathbb{N}$ as ordinals. Each number is the set of smaller numbers. The ordinal $\mathbb{N}$ is usually denoted by $\omega$. The same scheme allows “counting” past $\mathbb{N}$.

* $0 := \emptyset; 1 := \{0\} = \{\emptyset\}; 2 := \{0,1\} = \{\emptyset, \{\emptyset\}\}; 3 := \{0,1,2\} = \{\emptyset, \{\emptyset\}, \{\emptyset, \{\emptyset\}\}\}, \dots$

* $\omega := \{0, 1, 2, \dots\}; \omega + 1 := \omega \cup \{\omega\}, \dots, \omega \cdot 2 = \{0, 1, \dots, \omega, \omega + 1, \omega + 2, \dots\}, \dots$

* $\omega^2 = \{0, 1, \dots, \omega, \dots, \omega \cdot 2, \dots, \omega \cdot 3, \dots\}$

* ...

As can be seen above, ordinals larger than $\emptyset$ come in two flavors: (1) **successor ordinals** $\alpha + 1 := \alpha \cup \{\alpha\}$; (2) **limit ordinals** such as $\omega = \bigcup_{\alpha<\omega} \alpha$, $\omega \cdot 2$, $\omega^2$ and so on.

**Ordinal addition: an example of transfinite recursion.** The addition $\alpha + \beta$ of two ordinals can be defined with **transfinite recursion**, a general technique for writing down a formula applicable to a well-ordered class of objects. To define a function $f$ for all ordinals, it suffices to define it for the base case $f(\emptyset)$, and then define $f(\alpha)$ assuming $f(\beta)$ is defined for any $\beta < \alpha$. Two cases need to be distinguished: the successor case $\alpha = \gamma + 1$ for some $\gamma$, and the limit case $\alpha = \bigcup_{\gamma<\alpha} \gamma$. For ordinal addition, the definition of $\alpha + \beta$ uses transfinite recursion on $\beta$:

* Base case, $\beta = 0$: then, $\alpha + 0 := \alpha$;

* Successor case, $\beta = \gamma + 1$: then, $\alpha + \beta := (\alpha + \gamma) + 1$;
• Limit case, $\beta$ is a limit ordinal: then, $\alpha + \beta := \bigcup_{\gamma<\beta} \alpha + \gamma$.

In the above definition, note that $\alpha, \beta$ can be infinite and even uncountable. When seeing transfinite recursion for the first time, a natural question is how does it “work” in ZFC. The way it is implemented is by a formula, in this case Plus($x, y, z$), which is true iff $x$ and $y$ are ordinals and $z$ is their sum. It is almost like coding. Let’s define Plus($x, y, z$) in full detail to exemplify how this is done.

Let Ord($x$) be shorthand for the formula that asserts $x$ is an ordinal, Succ($x, y$) for $y = x \cup \{x\}$, and LimOrd($x$) for $x$ being a limit ordinal. Plus($x, y, z$) has to ensure $x$ and $y$ are ordinals and $z$ is their ordinal sum. This is accomplished with a helper sequence $s$ of length $y+1$ (a function whose domain is $y+1^{24}$) such that at every “position” $w$, $0 \le w \le y$ the value $s[w]$ is $x+w$. Let Fun($x$) be shorthand for $x$ being a function$^{25}$ and Dom($x, y$) for “the domain of $x$ is $y$”. Also, let the shorthand $s[i] = y$ stand for a formula Eval($s, i, y$) that is true iff $s(i) = y$, i.e., if the pair $(i, y)$ is a member of $s$. The reader may want to write down their Plus version before reading the one below. For readability, $\alpha, \beta, ...$ are used as variables taking ordinal values:

$$ \text{Plus}(\alpha, \beta, \gamma) := \text{Ord}(\alpha) \wedge \text{Ord}(\beta) \wedge \exists \beta'(\text{Succ}(\beta, \beta') \wedge \exists s (\text{Fun}(s) \wedge \text{Dom}(s, \beta') \wedge \\ \forall \delta \in \beta' ((\delta = \emptyset \wedge s[\delta] = \alpha) \vee (\exists \zeta \text{ Succ}(\zeta, \delta) \wedge \text{Succ}(s[\zeta], s[\delta])) \vee (\text{LimOrd}(\delta) \wedge s[\delta] = \bigcup_{\zeta \in \delta} s[\zeta])) \wedge \gamma = s[\beta])) $$

Note the use of shorthand $\bigcup_{\zeta \in \delta} s[\zeta]$. The range of $s$ for $\zeta \in \delta$ exists by Replacement and its union exists by Union. Composing a formula for $\bigcup$ is an exercise left for the reader.

Readers familiar with Gödel’s incompleteness theorem and the expression of recursive functions with Peano Arithmetic formulas will notice a similarity here, where intermediate values are “saved” in $s$. The upshot is that every transfinite recursive definition can be expressed as a formula. One way to do so is the technique given above, where a helper sequence $s$ stores all intermediate values. From now on, we will liberally make transfinite recursive definitions without the need to provide formulas.

Notice that $1 + \omega = \omega$ while $\omega + 1 = \{0, 1, ..., \omega\} \neq \omega$. As another example, $\omega + \omega$ is a limit ordinal equal to $\bigcup_{\alpha<\omega} \omega + \alpha$ and it has the same order type as $0 < 1 < 2 < \dots < 0' < 1' < 2' < \dots$. Figure 1 displays ordinals up to $\omega^\omega$.

**Ordinal multiplication.** The ordinal $\alpha \cdot \beta$ can be defined as the Cartesian product of $\alpha$ and $\beta$ with elements sorted lexicographically. By convention, the least significant position is placed first. As an example, $\omega \cdot 2 = \{(0, 0), (0, 1), (0, 2), \dots, (1, 0), (1, 1), (1, 2), \dots\} = \omega + \omega$ whereas $2 \cdot \omega = \{(0, 0), (0, 1), (1, 0), (1, 1), (2, 0), (2, 1), \dots\} = \omega$. As another example, $\omega^2$ has the same order as $\mathbb{N}^2$ under lexicographic order $(a, b) < (c, d) \leftrightarrow a < c \vee (a = c \wedge b < d)$.

No finite ordinal can be mapped bijectively to a different ordinal. However, this is no longer true for infinite ordinals. For example, $\omega^2$ can be mapped bijectively to $\omega$ because both sets are countable.

There are certain ordinals that cannot be put in a bijection with a smaller ordinal. All $n \in \omega$ are examples. Also, $\omega$ is an example. A cardinal is an ordinal that cannot be put in a bijection with a smaller ordinal. Every member of $\omega$ as well as $\omega$ itself are cardinals and $\omega$ is the smallest infinite cardinal. Let Card($\kappa$) be shorthand for the formula asserting $\kappa$ is a cardinal. There is special notation for infinite cardinals: $\aleph_0 := \omega$ and every subsequent infinite cardinal is given an ordinal subscript: $\aleph_0 < \aleph_1 < \aleph_2 < \dots < \aleph_k < \dots < \aleph_\omega < \dots$. Each of these cardinals is a different order of infinity, “bigger” than the previous infinity in the sense that there cannot be a bijection between them. The notation $\aleph_\alpha$ can be thought of as shorthand for a formula Aleph($\kappa, \alpha$) asserting that $\alpha$ is an ordinal and $\kappa$ is precisely the $\alpha$th infinite cardinal. Given any set $S$, we denote by $|S|$ the unique cardinal that maps bijectively to $S$.

The cardinal successor of a cardinal $\kappa$ is the cardinal immediately larger than $\kappa$, denoted $\kappa^+$. This should not be confused with the ordinal successor of $\kappa$, which is $\kappa \cup \{\kappa\}$.

**Cardinal exponentiation.** Given infinite cardinals $\kappa$ and $\lambda$, $\kappa^\lambda$ is defined to be the cardinality of the set of functions from $\lambda$ to $\kappa$. The usual properties of exponentiation such as $\kappa^{\lambda+\xi} = \kappa^\lambda \kappa^\xi$ and

<footnote>$^{24}$Recall that $y+1$ is the set of ordinals $\le y$.</footnote>

<footnote>$^{25}$A set of pairs $(a, b)$ such that for any $a$ there is at most a single $(a, b)$.</footnote>
<figure><img src="image_3.png" /><figcaption>Figure 1: **Representation of ordinal numbers up to $\omega^\omega$.**

Picture found in Wikipedia (https://en.wikipedia.org/wiki/Ordinal_number) without attribution.</figcaption></figure>

$\kappa^{\lambda\xi} = \kappa^{\lambda\epsilon}$ follow easily from the definition. With the Axiom of Choice (AC), additional properties simplify cardinal exponentiation:

* For infinite $\kappa \le \lambda$, we have $\kappa^{\lambda} = 2^{\lambda}$.

* If there exists cardinal $\mu < \kappa$ with $\mu^{\lambda} \ge \kappa$, then $\kappa^{\lambda} = \mu^{\lambda}$.

**Confusing abuse of notation: ordinal vs. cardinal exponentiation.** There is an unfortunate notational discrepancy between ordinal and cardinal exponentiation. Exponentiating to a limit ordinal such as $\omega^\omega$ denotes taking the limit $\sup\{\omega^n | n \in \omega\}$, while if $\omega$ is viewed as the cardinal $\aleph_0$, $\aleph_0^{\aleph_0}$ denotes the cardinal of same size as the set of functions $\aleph_0 \to \aleph_0$. Therefore, $\omega^\omega = \bigcup_{n \in \omega} \omega^n$ is a countable union of countable sets and therefore countable, while $\aleph_0^{\aleph_0}$ is of cardinality continuum. To see why this is so, observe that $2^{\aleph_0} \le \aleph_0^{\aleph_0} \le (2^{\aleph_0})^{\aleph_0} = 2^{\aleph_0^2} = 2^{\aleph_0}$.

With this terminology, CH states that $2^{\aleph_0} = \aleph_1$. GCH states that $2^{\aleph_\alpha} = \aleph_{\alpha+1}$ for any ordinal $\alpha$.

**How big are countable ordinals?** Countable ordinals are way smaller than continuum. Since we are all familiar with the real line or interval (0, 1), which we don't consider all that “big”, we may conclude that countable ordinals can't be too big. In fact, countable ordinals keep advancing to stages that are absurdly high. As a first flavor, Cantor's ordinal $\varepsilon_0$ is defined as the first ordinal that is a fixed point of $\varepsilon = \omega^\varepsilon$, and consequently $\varepsilon_0 = \omega^{\omega^{\omega^{\cdot\cdot\cdot}}} = \sup\{\omega, \omega^\omega, \omega^{\omega^\omega}, \dots\}$. It is still countable. Next, $\varepsilon_1$ is the next fixed point, $\varepsilon_2$ the next, and so on: $\varepsilon_0, \varepsilon_1, \dots, \varepsilon_\omega, \dots, \varepsilon_{\varepsilon_0}, \dots, \varepsilon_{\varepsilon_{\varepsilon_\omega}}, \dots$ are all fixed points of $\varepsilon = \omega^\varepsilon$ and each such $\varepsilon_\zeta$ is countable as long as $\zeta$ is countable. This topic is complex and beyond the scope here, but worth keeping in mind in the subsequent sections when wondering how a countable model $M$ could cogently reflect properties of uncountable cardinals.
### 3.2.1 Expressing mathematics in ZFC

ZFC is powerful enough to express all ordinary mathematics. Some examples:

* **Definition of $\mathbb{N}$.** $\mathbb{N}$ is defined using Infinity and Comprehension: using abbreviations $\emptyset$ and $S(x) := x \cup \{x\}$, we can define $I$ as an infinite set satisfying the axiom of Infinity and $\mathbb{N}$ as $\{x \in I : \forall J \text{Inf}(J) \to x \in J\}$, which exists by the axiom of Comprehension. Now we can define $0 := \emptyset$, $1 := S(0)$ and addition inductively for any $m, n \in \mathbb{N}$ expressed as a formula $\phi_+(m, n, s)$ that is true iff $s = m + n$ by $0 + 0 := 0$; $m + S(n) = S(m) + n := S(m + n)$ and with some effort prove all the properties of addition such as associativity and commutativity. Similarly a formula $\phi_\times$ can be defined for multiplication with $m \times S(n) := m \times n + n$. These recursive definitions can be turned into formulas using precisely the same technique employed above to define ordinal addition. Then, all properties of these operations can be proven using ZFC axioms.

* **Definition of $\mathbb{Q}$.** $\mathbb{Q}$ can be defined in a multitude of ways; a clean one is representing $m/n$ as a pair $(m, n)$ with no common divisor$^{26}$ and defining addition $(a, b) + (c, d) := (r, s)$ whereby $r/s = (ad + bc)/cd$ but $r, s$ share no common divisor.

* **Definition of $\mathbb{R}$.** $\mathbb{R}$ can also be defined in many ways, such as using *Dedekind cuts*: a cut is a partition of $\mathbb{Q}$ into two subsets $A, B$ such that $A$ is nonempty and a proper subset of $\mathbb{Q}$, if $x < y \in A$ then $x \in A$, and additionally $\forall x \in A \exists y \in A \ y > x$. $\mathbb{R}$ can be defined as the the set of all cuts $(A, B)$ with '<' defined by $(A, B) < (C, D)$ iff $A$ is a proper subset of $C$. For example, $\sqrt{2}$ becomes the cut $\{(x \in \mathbb{Q} : x < 0 \lor x^2 < 2\}, \{y \in \mathbb{Q} : y > 0 \land y^2 > 2\})$. Addition of $(A, B)$, $(C, D)$ can be defined as $(A', B')$ with $A' = \bigcup\{x + y : x \in A \land y \in C\}$ and $B' = \mathbb{Q} - A'$. And so on. All familiar properties of $\mathbb{R}$ can be proven.

With some pain, all familiar concepts in mathematics can be defined, and all mathematical proofs can be expanded to formal proofs within ZFC. ZFC can be thought of as a low-level programming language for mathematics.

## 3.3 Sets, Classes and the Universe

The ZFC axioms postulate the existence of sets built out of other sets. However, not everything expressed syntactically in ZFC is a set. The famous Russell's paradox of a set of all sets that are not members of themselves is avoided here by simply not allowing $x \in x$. Specifically, $\{x | x \in x\} = \emptyset$ and $\{x | x \notin x\}$ is the collection of all sets, which is not a set in ZFC.

**Proper classes.** A formula $P(x)$ of a single free variable $x$ (a property $P$), sometimes defines a set $\{x | P(x)\}$ of all elements satisfying the property. For example, the collection of all $x$ that satisfy $x \neq x$ is $\emptyset$, which is a set. The collection of $x$ that satisfy $\text{Inf}(x) \land \forall z \text{Inf}(z) \to x \subseteq z$ is precisely $\{\omega\}$. However, $P(x)$ need not define a set. Sometimes the set status of $x : P(x)$ is unknown, and sometimes it is *known* not to be a set, in which case $x : P(x)$ is called a **proper class**. For example, $x : \text{Ord}(x)$ cannot be a set: if it were, it would be (1) transitive because given any $\alpha$ such that $\text{Ord}(\alpha)$, all $\alpha$'s members $\beta \in \alpha$ are also ordinals and therefore $\text{Ord}(\beta)$; and (2) well ordered by $\in$ because given any two ordinals $\alpha, \beta$ either $\alpha \in \beta$ or $\beta \in \alpha$ or $\alpha = \beta$, and given any subset there would be a smallest element because of Foundation$^{27}$. Therefore, if it were a set, $\text{Ord}(x)$ would be an ordinal! But then $\text{Ord}(x)$ and indeed $\text{Ord}(x) + 1$ would need to be “in” $\text{Ord}(x)$, an absurdity. Therefore, the ordinals are a proper class and not a set. We will denote them by $\text{ON}$: when we say $x \in \text{ON}$ this is just another way of writing $\text{Ord}(x)$.<fnref n="28" />

**The universe $V$ and the cumulative hierarchy.** The most important proper class of sets is the entire universe $V$ of all sets. $V$ can be defined with transfinite recursion similarly to how $\text{Plus}(x, y, z)$ was defined in the preceding section. The set $V_\alpha$ is defined for every ordinal $\alpha$. Note that $V_\alpha$ is indeed a set and is called the *universe at stage $\alpha$*:

<footnote n="26">²⁶A formula to achieve that would be $\neg\exists r, s, t \in \mathbb{N} (r > 1 \land s > 1 \land t > 1 \land \phi_\times(r, s, m) \land \phi_\times(r, t, n))$.</footnote>

<footnote n="27">²⁷Given a subset $s$ consisting of ordinals, let $\alpha_0 \in s$. If $\alpha$ is the smallest element, we are done. If not, pick $\alpha_1 < \alpha_0$, i.e., $\alpha_1 \in \alpha_0$. Continue on with $\alpha_{i+1} \in \alpha_i$ until the smallest element is hit. The sequence has to terminate because by Foundation there is no infinite descending chain $\cdots \in \alpha_{i+1} \in \alpha_i \cdots \alpha_0$.</footnote>

<footnote n="28">²⁸Incidentally, there are countably many formulas $P(x)$ and therefore there are countably many proper classes definable by a formula and countably many sets definable by a formula. For instance, when considering the continuum-many subsets of $\omega$, only countably many of them can ever be specified.</footnote>
• $V_0 := \emptyset$

• $V_{\alpha+1} := \mathcal{P}(V_\alpha)$, the power set of $V_\alpha$ for any successor ordinal $\alpha$.

• $V_\alpha := \bigcup_{\beta<\alpha} V_\beta$ for any limit ordinal $\alpha$.

• $V := \bigcup_{\alpha \in ON} V_\alpha$.

This definition stands for a ZFC formula, call it $V(\alpha, x)$ which says that “$x$ is a member of $V_\alpha$”, and a formula $V(x)$ which says that “$x$ is a member of some $V_\alpha$”. Before proceeding, the reader may want to write down versions of these formulas.

Let's write down these formulas. $Pow(x, y)$ is an abbreviation for the formula “$y$ is the power set of $x$”. The other abbreviations have been introduced. Notice the use of $V_{aux}$, which is a helper sequence that contains all stage-$\beta$ universes for $0 \le \beta \le \alpha$.<fnref n="29" /> Also note that it is easy to show that if $x \in V_\alpha$ then $x \in V_\gamma$ for all $\gamma > \alpha$. This is called a **cumulative** property, and $V$ is a **cumulative hierarchy**.

$$ 
\begin{aligned}
V(\alpha, x) &:= \operatorname{Ord}(\alpha) \wedge \exists V_{aux} \operatorname{Fun}(V_{aux}) \wedge \operatorname{Dom}(V_{aux}, \alpha + 1) \wedge \\
&\quad \forall \beta \in \alpha + 1 (\beta = \emptyset \wedge V_{aux}[\beta] = \emptyset) \vee (\exists \gamma \in \beta \beta = \gamma + 1 \wedge \operatorname{Pow}(V_{aux}[\gamma], V_{aux}[\beta])) \vee \\
&\quad (\operatorname{LimOrd}(\beta) \wedge V_{aux}[\beta] = \bigcup_{\gamma \in \beta} V_{aux}[\gamma]) \wedge x \in V_{aux}[\alpha]
\end{aligned}
$$

We can define the proper class $V$ with the formula $V(x) := \exists \alpha V(\alpha, x)$. It is not hard to prove that $\forall x V(x)$.

Having defined $V(\alpha, x)$, a useful property to define for any set $x$ is its **rank**. Let $\operatorname{rank}(x)$ be the first ordinal $\alpha$ such that $x \in V_\alpha$, i.e., the least ordinal $\alpha$ such that $V(\alpha, x)$. It is easy to see that $\operatorname{rank}(x)$ is the smallest ordinal that exceeds the rank of any member of $x$. If $\beta$ is the supremum of ranks of elements in $x$, then $\operatorname{rank}(x) = \beta + 1$ if there is $y \in x$ with $\operatorname{rank}(y) = \beta$, and otherwise $\operatorname{rank}(x) = \beta$.

**Class functions.** A class function is a unary operation defined on a class of sets. Consider a class of sets $A : P(A)$. A class function $\phi$ over the class is a unary operation that takes any $A$ such that $P(A)$ as argument and returns some set $B$. For example, the formula $\phi(x, y, A)$ in the Replacement Schema takes as input any $A$ in the universe $V$ and defines a set $B$ that consists of replacing every $x$ in $A$ with the unique $y$ such that $\phi(x, y, A)$. The Replacement Schema postulates that $B$ is a set.

**Summary: sets and classes.** A set is any entity proven to exist by ZFC. Syntactically, think of a set as a variable $x$ bound within a formula that states that $x$ exists and is the unique entity with so and so properties. A good example is $\omega$, which should be thought of as the bound variable $x$ within the formula $\exists x \operatorname{Inf}(x) \wedge \forall y \operatorname{Inf}(y) \rightarrow x \subseteq y$. A class is just a formula—a property—$P(x)$ of a single free variable. It defines any $x$ that makes the resulting sentence true. So, when we define a class such as $ON$ (the ordinals), we really mean anything that satisfies the formula $\operatorname{Ord}(x)$. And when we abuse notation and say $\alpha \in ON$, we really mean $\operatorname{Ord}(\alpha)$. A proper class is simply a class—a single-variable formula—which is satisfied by a collection of items that cannot possibly be a set. $ON$ and $V$ are examples of proper classes. When we use transfinite recursion to define a set, a class, a function or a relation, such as in the case of $V_\alpha$ or of ordinal addition $Plus(\alpha, \beta, \gamma)$, we simply are writing down a single ZFC formula in readable form, by exposing the base case, the successor ordinal case, and the limit ordinal case.

## 3.4 Models and Reflection

Given a collection $\Phi$ of formulas of a language $\mathcal{L}$, a model $M$ is basically a set of elements in which the formulas are assigned meaning and are true. More precisely, a model $M$ is a set together with assignments of constants of $\mathcal{L}$ to elements of $M$, functions of $k$ variables of $\mathcal{L}$ to functions $M^k \rightarrow M$, and relations of $\mathcal{L}$ to subsets of $M \times M$. $M$ is a **model** of $\Phi$ if each formula in $\Phi$ is true under this assignment.

<footnote n="29">²⁹$V_{aux}$ is a set that is a function with domain $\alpha + 1$, similarly to $s$ in the definition of Plus. $V_{aux}[\beta] = \gamma$ stands for $\operatorname{Eval}(V_{aux}, \beta, \gamma)$, or equivalently for $(\beta, \gamma) \in V_{aux}$.</footnote>
As an example, consider again the axioms of group theory: (1) associativity: $\forall x \forall y \forall z (x \cdot y) \cdot z = x \cdot (y \cdot z)$; (2) identity: $\forall x e \cdot x = x \cdot e = x$; (3) inverse: $\forall x \exists x^{-1} x \cdot x^{-1} = x^{-1} \cdot x = e$. One model of these axioms is $M = \{0, 1, 2, 3, 4\}$ with $e := 0$, $x \cdot y := x + y \bmod 5$. Another model is $\mathbb{Z} = \{\dots, -2, -1, 0, 1, 2, \dots\}$ with $e := 0$, $x \cdot y := x + y$ and $x^{-1} := -x$. Yet another model is $\mathbf{SO}(3)$, the group of rotations in 3 dimensions: identity is the rotation by zero degrees in any axis; associativity holds between any three rotations; and each rotation has the reverse rotation as its unique inverse.

The notion of a model is useful in determining whether a given statement is the logical consequence of a collection of axioms. As an example, does the commutative law $\forall x \forall y x \cdot y = y \cdot x$ follow from the laws of group theory? It doesn't, because it holds for some models of group theory, such as $G$ and $\mathbb{Z}$, but doesn't hold for others such as $\mathbf{SO}(3)$: performing a rotation by $90^\circ$ by the $z$-axis followed by one by the $y$-axis takes $(1, 0, 0)$ to $(0, 0, 1)$ while reversing the order results in $(0, 1, 0)$. An important theorem is behind this:

**Gödel's completeness theorem:** any consistent collection of formulas of first order logic has a model.

Consequently, if neither $\phi$ nor $\neg\phi$ is a logical consequence of $\Phi$, then there exists models both for $\Phi \cup \{\phi\}$ and $\Phi \cup \{\neg\phi\}$. The commutative law is an example of a formula independent of the axioms of group theory. Consequently, there are commutative models such as $\mathbb{Z}$ and non-commutative models such as $\mathbf{SO}(3)$.

Gödel's completeness theorem is outside the scope of this manuscript. The reader can take it as given, or preferably refer to an exposition of the Henkin version of the proof (Arjona and Alonso 2014). The proof is not hard, and is illuminating on how models arise from syntax.

**Models of ZFC.** In ZFC there are no constants (alternatively, sometimes $\emptyset$ is defined as a constant), there are countably many variables $x_0, x_1, x_2, \dots$, no functions, and two relations: $\in$, $=$. A model of ZFC is a set $M$ together with assignments of the relations $\in$ and $=$ to subsets of $M \times M$ so that each of the countably many axioms of ZFC is logically valid under these assignments.

**Standard transitive models.** The language of ZFC devoid of a model is just syntax and $\in$ is just a letter that by itself carries no meaning. The axioms do give it structure, but in principle a model could be devised where $\in$ is a relation other than set membership. A **standard model** $M$ is one where $\in$ is set membership. There is a bit of meta reasoning here. Who decides what is set membership? We do! Examining ZFC as syntax, and thinking of $M$ semantically, we decide that indeed $\in$ is set membership within $M$. Formally, if we assume the class $V$ to be the “true” set universe, a standard model $M$ is a set in $V$ (i.e., $\exists\alpha M \in V_\alpha$) and we check that $\in_M$, viewed as a subset of $M \times M$, is precisely $\in_V \cap M \times M$, where $\in_V$ is the subset of $V$ that stands for “true” $\in$. If in addition $M$ is a transitive set, then $M$ is a **standard transitive model** and has nice properties that will be covered below.

In the proof of independence of CH, the notion of a model of ZFC will be used extensively. The models will be standard countable transitive sets.

Each model will be a mini-universe within which a sentence $\phi$ may be true or false, and may have a truth value different from its truth value across $V$. To keep track of truth of formulas within models, two concepts are key: **relativization** and **reflection**. Informally, a formula $\phi$ is *relativized* to a set $M$ when $\phi$ talks about objects in $M$ only. For a trivial example, if $\phi := \forall x x = \emptyset$ then $\phi$ is false; however, relative to $M := \{\emptyset\}$ $\phi$ is true. As another example, $\psi := \forall x \exists y y = x + 1$ is true relativized to $\mathbb{N}$ but false relativized to $\{0, 1, \dots, 2022\}$. We denote $\phi$ relativized to $M$ by $\phi^M$. A formula $\phi$ is *reflected* in $M$ when $\phi$ is equivalent to its relativization: $\phi \leftrightarrow \phi^M$. Let's make these notions more precise:

**Relativization.** A formula $\phi$ is **relativized** to a set $M$ if all its variables range over $M$. This is achieved by a simple syntactic manipulation to make all existential and universal quantifiers range over $M$: all $\forall x \psi(x)$ and $\exists x \psi(x)$ are simply converted to $\forall x \in M \psi(x)$ and $\exists x \in M \psi(x)$. More precisely, any set $M$ can be thought of as a formula of a single variable $M(x)$ that defines a set of elements satisfying it. Then, $\forall x \in M \psi(x)$ and $\exists x \in M \psi(x)$ are simply shorthand for $\forall x (M(x) \to \psi(x))$ and $\exists x (M(x) \land \psi(x))$. We denote this syntactically modified formula by $\phi^M$. Some examples:

* $\phi := \forall x x = \emptyset$ is false. However, if we let $M := \{\emptyset\}$, $\phi^M$ becomes $\forall x \in M x = \emptyset$, which is true.

* $\phi := \forall x x = \emptyset \lor \exists y x = y \cup \{y\}$ is also false. However, relativized to $\omega$ it is true.
• $\phi := \forall x x = \emptyset \lor \exists y y \in x$ is true. However, if we let $M := \{1\}^{30}$ then $\forall x \in M x = \emptyset \lor \exists y \in M y \in x$ is false.

In general, formulas relativized to a set $M$ state something about $M$.

**Relativization to a class/property.** The notion of a set model can be generalized to a class model. Syntactically, a set in ZFC is just a formula $\phi(y)$ for which the sentence $\exists x \forall y (y \in x \leftrightarrow \phi(y))$ is derivable in ZFC. For example, $\emptyset$ is captured by $\exists x \forall y (y \in x \leftrightarrow y \neq y)$.31 More generally, a formula $P(y)$ defines the class of all $y$ that satisfy property $P$. This class becomes a set if it is provable in ZFC that $\exists x \forall y (y \in x \leftrightarrow P(y))$. Even when such a proof is not possible, however, we can relativize a formula $\phi$ to $P$: simply require that all variables of $\phi$ range over values for which $P$ is true. Syntactically, all subformulas of the form $\forall x \psi(x)$ and $\exists x \psi(x)$ are converted to $\forall x (P(x) \rightarrow \psi(x))$ and $\exists x (P(x) \land \psi(x))$, respectively. For example:

• $\forall x \forall y x \in y \lor x = y \lor y \in x$ is clearly false. However, we can relativize it to the proper class $ON$ of ordinals, which is not a set. $\forall x \in ON \forall y \in ON x \in y \lor x = y \lor y \in x$ is true. This latter formula should be understood as shorthand for $\forall x (\mathrm{Ord}(x) \rightarrow \forall y (\mathrm{Ord}(y) \rightarrow x \in y \lor x = y \lor y \in x))$.

**Reflection.** Reflection is the property of a set $M$ whereby a formula $\phi$ is equivalent to $\phi^M$: we say that $M$ reflects $\phi$ just in case $\phi \leftrightarrow \phi^M$ is true whenever all free variables of $\phi$ range over $M$. The latter point can be a source of confusion. Say that $\phi(x, y)$ has free variables $x$ and $y$. “$M$ reflects $\phi$” means that whenever $a, b \in M$, we have $\phi(a, b) \leftrightarrow \phi^M(a, b)$. For example, let $\phi(x, y) := x \in y \lor y \in x \lor x = y$. Then, $\omega$ reflects $\phi$ trivially because $\phi = \phi^\omega$ and therefore for any $m, n \in \omega$, $\phi(m, n) \leftrightarrow \phi^\omega(m, n)$. But now let $\psi(x) := \forall y \phi(x, y)$. In this case, $\psi^\omega := \forall y \in \omega x \in y \lor y \in x \lor x = y$, and $\omega$ does not reflect $\psi$ because we can find $n \in \omega$ (in fact, any $n \in \omega$) for which $\psi(n)$ is false and $\psi^\omega(n)$ is true.

Recall the definition of transitivity. A set $M$ is **transitive** if every member's member is a member: $M$ is transitive if $\forall x \in M y \in x \rightarrow y \in M$. A transitive set $M$ reflects a large class of formulas: those that involve only looking at elements of $M$ and their contents. Some examples before this concept is made more precise.

Consider $\mathrm{Empty}(x) := \forall w w \in x \rightarrow w \neq w$. Relativized to $M$, $\mathrm{Empty}^M(x) := \forall w \in M w \in x \rightarrow w \neq w$. Is $\mathrm{Empty}(x)$ reflected in $M$? Equivalently, does $\mathrm{Empty}(x) \leftrightarrow \mathrm{Empty}^M(x)$ hold whenever $x$ ranges over $M$? Well, it is easy to show this does not hold in general. Let $M := \{1, 2\}$ and let $x = 1$. By our definition of 1 := $\{0\}$, Empty(1) is false because $0 \in 1$ but Empty$^M(1)$ is true because $\forall w \in M w \notin 1$ holds. What if $M$ were transitive? Then, because $0 \in 1$ whenever $1 \in M$, it would necessarily be the case that $0 \in M$. It is easy to show that $\mathrm{Empty}(x)$ is reflected in any transitive set $M$.

As a more involved example, consider the definition of an ordinal as a transitive set totally ordered by $\in$: $\mathrm{Ord}(x) := \forall y \forall z y \in x \rightarrow (z \in y \rightarrow z \in x) \land (z \in x \rightarrow (z \in y \lor y \in z \lor y = z))$. Let's relativize $\mathrm{Ord}(x)$ to $M$: $\mathrm{Ord}^M(x) := \forall y \in M \forall z \in M y \in x \rightarrow (z \in y \rightarrow z \in x) \land (z \in x \rightarrow (z \in y \lor y \in z \lor y = z))$. Let $M$ be transitive and let some ordinal $\alpha \in M$. $\mathrm{Ord}(\alpha)$ holds by assumption. Does $\mathrm{Ord}^M(\alpha)$ hold? Well, if $\forall y \forall z y \in \alpha \rightarrow \dots$ holds, then certainly $\forall y \forall z \in M y \in \alpha \rightarrow \dots$ holds as well. Therefore, $\mathrm{Ord}(x)$ is reflected in any transitive set.

The property of $\mathrm{Empty}(x)$ and $\mathrm{Ord}(x)$ of being reflected in every transitive set, is a general property of a formula called absoluteness. Informally, $\mathrm{Empty}(x)$ and $\mathrm{Ord}(x)$ are formulas that only talk about sets within $x$, and therefore if the model is transitive and has $x$, it has all the relevant elements to decide the truth of the formula:

**Absoluteness.** A formula $\phi$ is called **absolute** across transitive models if $\phi \leftrightarrow \phi^M$ for any transitive set $M$. Absoluteness is a useful concept in reasoning about formulas. There is an important class of formulas of “low complexity” that are absolute in every transitive set.

<footnote>30Recall, $1 := \{\emptyset\}$.</footnote>

<footnote>31When a ZFC proof uses $\emptyset$, this should be understood as shorthand for the following: (1) append to the beginning of that proof the derivation of the sentence $\exists x \forall y (y \in x \leftrightarrow y \neq y)$; (2) understand whatever formula uses $\emptyset$ to be a $\land$ with $\exists x \forall w w \notin x$ (where the $x$ variable is treated properly in the rest of the formula). For example, $1 = \{\emptyset\}$ should be understood as shorthand for something like $\exists w \exists x (\forall y (y \in x \leftrightarrow y \neq y) \land \forall z z \in w \rightarrow z = x)$. Writing down proofs in full mechanically verifiable detail is incredibly painful but it works. The same is true for assembly code, which is simpler to reason about and implement in hardware, but cumbersome to program on. In our case, $\emptyset, 1, 2$, and so on are examples of shorthand that unrolls into longer formulas and proofs.</footnote>
**Logical complexity.** The quantifiers of a formula, $\forall x$ and $\exists x$, determine its logical complexity. Quantifiers are **bounded** when they are of the form $\forall x \in y \psi$ and $\exists x \in y \psi$ (formally, $\forall x x \in y \to \psi$ and $\exists x x \in y \land \psi$), and otherwise they are **free**. Bounded quantifiers let the variable range over a given set, while free quantifiers let the variable range over the universe. Bounded quantifiers do not make the formula any more complex. Free quantifiers increase the logical complexity of the formula. A formula is of the lowest complexity $\Delta_0$ if all its quantifiers are bounded. A formula is $\Sigma_1$ if it is $\exists x \psi$ where $\psi$ is $\Delta_0$. A formula is $\Pi_1$ if it is $\forall x \psi$ where $\phi$ is $\Delta_0$. Here, $x$ could represent a tuple so these are equivalent to allowing the formula to be $\exists x_1 \dots \exists x_k \phi$ or $\forall x_1 \dots \forall x_k \phi$, respectively. Higher complexity formulas involve alternating quantifiers, but we will not need to discuss this topic. The following important properties are easy to prove:

Whenever $M$ is a transitive set, $\phi$ is $\Delta_0$ and free variables range over $M$,

* **Absoluteness of bounded formulas.** $\phi$ is reflected in $M$: $\phi \leftrightarrow \phi^M$. **Proof sketch.** The idea is simple: $\phi^M$ is simply $\phi$ with the syntactic change of converting every quantifier $\exists x \psi(x)$ to $\exists x x \in M \land \psi^M(x)$. Because all quantifiers in $\phi$ are bounded, they are of the form $\exists x x \in y \land \psi(x)$, for some $y$. When interpreting $\phi^M$ by definition all variables range over $M$ and so does $y$. Therefore, $x \in y$ implies $x \in M$. Therefore, $\exists x x \in y \land x \in M \land \psi^M(x)$ is equivalent to $\exists x x \in y \land \psi^M(x)$, which in turn is equivalent to $\exists x x \in y \land \psi(x)$ by inductive assumption on the structure of $\phi$. $\square$

* Moreover, for any $\Sigma_1$ formula $\psi := \exists x \phi$, it is true that $\exists x \in M \phi \to \exists x \phi$, therefore $\psi^M \to \psi$. This is obvious: if there is $x$ within $M$ with a given property, then there is $x$ with the property.

* Conversely, for any $\Pi_1$ formula $\psi := \forall x \phi$, it is true that $\psi \to \psi^M$. This is also obvious: if for all $x$ a property holds, then the property holds for all $x$ in $M$.

Many useful formulas are $\Delta_0$ and therefore absolute across transitive sets, and can be transferred freely across transitive models. Here is a useful list:

* “$x$ is empty”; “$x$ is the union of $y$ and $z$”.$^{32}$

* “$x$ is transitive”.$^{33}$

* “$x$ is an ordinal”: $\text{Ord}(x)$; “$x$ is a successor ordinal”; “$x$ is a limit ordinal”.$^{34}$

* “$x$ is a natural number”.$^{35}$

* $\omega$: we only need to look at elements within a set $x$ to tell whether $x$ is indeed equal to $\omega$.$^{36}$ Therefore, for any transitive model $M$, $\omega^M = \omega$, or in the notation that we will use most frequently, $\aleph_0^M = \aleph_0$.

* “$f$ is a function from $x$ to $y$”; similarly for $f$ is a bijection, surjection, injection etc. Also $\text{Dom}(f)$, $\text{Ran}(f)$ are absolute: we only need to look inside $f$ to see which elements of the pairs $(x, y) \in f$ form the domain and range of $f$. Showing that these formulas are $\Delta_0$ is left as an easy exercise.

* “$x$ is finite”.$^{37}$

**Cardinals are not absolute.** $\text{Card}(\kappa) := $ “$\kappa$ is a cardinal” is not absolute. Unrolling this formula, it says that “$\text{Ord}(\kappa) \land$ there is no surjection $f$ between $\alpha \in \kappa$ and $\kappa$”. Now let $M$ be a transitive set and let $\kappa \in M$. The part $\text{Ord}(\kappa)$ is absolute, so $\kappa$ is an ordinal with respect to $M$ iff $\kappa$ is an ordinal. However, there could be a surjection $f: \alpha \to \kappa$ outside $M$ but none in $M$. Therefore, it is possible that $\text{Card}^M(\kappa)$ is true but $\text{Card}(\kappa)$ is false. In general, if we have models $M \subset N$, cardinals of $M$ can stop being cardinals in $N$, but any cardinals of $N$ are guaranteed to be cardinals of $M$.

Finally we are ready to express the Reflection Principle:

<footnote>$^{32}$The formula for “$x$ is empty” is $\neg \exists y \in x y = y$ (for instance) and the formula for “$x$ is the union of $y$ and $z$” is $(\forall w \in x w \in y \lor w \in z) \land \forall w \in y w \in x \land \forall w \in z w \in x$. Both formulas are $\Delta_0$.</footnote>

<footnote>$^{33}$$\forall y \in x \forall z \in y z \in x$ is $\Delta_0$.</footnote>

<footnote>$^{34}$For $x$ being a limit ordinal, $\text{Ord}(x) \land \forall y \in x \exists z \in x y \in z$ is $\Delta_0$. Successor ordinal is left as an exercise.</footnote>

<footnote>$^{35}$The following formula is $\Delta_0$: $\text{Ord}(x) \land (x$ is not a limit ordinal $\forall x = \emptyset) \land \forall y \in x (y = \emptyset \lor y$ is not a limit ordinal).</footnote>

<footnote>$^{36}$The formula “$x = \omega \leftrightarrow (\text{Ord}(x) \land x \neq \emptyset \land x$ is a limit ordinal $\land \forall y \in x y$ is a natural number)” is $\Delta_0$.</footnote>

<footnote>$^{37}$“$\exists n \in \omega \exists f \in \omega \times \omega f$ is a function from $n$ to $x$”. This definition uses the fact that $\omega \times \omega$ is absolute, which is left to the reader.</footnote>
**Reflection Principle.** Given any formula $\phi(x_1, \dots, x_k)$, it is a ZFC theorem that there exists a countable transitive set $M$ such that whenever the variables of $\phi$ take values $a_1, \dots, a_k \in M$,

$$ \phi(a_1, \dots, a_k) \leftrightarrow \phi^M(a_1, \dots, a_k) $$

We say that $\phi$ is reflected in $M$.

The Reflection Principle is an algorithm that takes any $\phi$ as input and returns a ZFC proof of $\exists M \operatorname{CntTrans}(M) \wedge \phi \leftrightarrow \phi^M$.

Importantly, $\phi$ can be the conjunction of any finite collection of theorems of ZFC:

**Reflection Principle and Finite Fragments of ZFC.** Given a finite collection of ZFC axioms $\phi_1, \dots, \phi_k$, it is a ZFC theorem that there exists a countable transitive set $M$ where the axioms are reflected: $\exists M \operatorname{CntTrans}(M) \wedge \phi_1^M \wedge \dots \wedge \phi_k^M$.

This is a stunningly powerful result: there exist countable transitive set models for arbitrarily large finite fragments of ZFC. Consequently, any theorem of ZFC—basically, any mathematical theorem—can be converted into a theorem holding within a countable transitive set model.

This also implies that there cannot be a finite first-order logical axiomatization of ZFC. If there was, ZFC could prove its own consistency through proving the existence of a model of all its axioms, which is impossible by Gödel's second incompleteness theorem.

The Reflection Principle is at the heart of the proof of independence of CH. The proof is not hard; we will skip it and come back to it in Section 6. For now, it is important to keep in mind the following point: ZFC does not have any way to “talk” about formulas as objects. Only after fixing formula $\phi$ can the Reflection Principle algorithm be run to output a ZFC proof that there is a countable transitive set $M$ such that $\phi \leftrightarrow \phi^M$. However, we can arithmetize ZFC because the collection of axioms is recursive, and prove the Reflection Principle in Peano Arithmetic.

# 4 Outline of the proof of independence of CH

## 4.1 Statement

To recap, the natural question we will be addressing is whether there is an infinity between $|\mathbb{N}| = |\omega| = \aleph_0$ and $|\mathbb{R}| = c = 2^{\aleph_0}$. The formula CH is the statement $2^{\aleph_0} = \aleph_1$. We will show that a proof of either CH or $\neg$CH leads to contradiction.

It is clear that a set $S$ such that $|\mathbb{N}| < |S| < |\mathbb{R}|$ can never be demonstrated the way $\mathbb{N}$ and $\mathbb{R}$ are: if it ever did, a contradiction would ensue. But neither can inexistence be proven. In fact, the inability to properly size $c$ in the pecking order of infinities is extreme: there can be 2, 3, 2022, countably many, or uncountably many infinities in-between $\aleph_0$ and $c$.<fnref n="38" />

Gödel showed that CH is consistent by the inner model method (1939), a topic beyond the scope here; a simple argument shows that this method cannot show that $\neg$CH is consistent.<fnref n="39" /> Instead, Cohen's

<footnote n="38">³⁸However, König's theorem restricts the precise position of $c$: it cannot be the union of a collection of fewer than $c$-many sets each of which is smaller than $c$. This topic is addressed in the section “What values can $2^{\aleph_0}$ take?” below.</footnote>

<footnote n="39">³⁹The topic is beyond the scope of this manuscript and for excellent further reading material I refer the reader to Smullyan and Fitting (2010), but a brief summary is in order. In the inner model method, a formula $L(x)$ is devised for the universe of constructible sets, analogous to $V(x)$ for the universe of all sets. The difference is that at every stage $\alpha$, $L_{\alpha+1}$ is defined to contain the sets that are definable by formulas with parameters from $L_\alpha$ instead of $V_{\alpha+1}$ being the power set of $V_\alpha$. The collection $x: L(x)$ is a proper class containing all the ordinals and such that every axiom of ZFC $\phi$ is proven in its relativized version $\phi^L$, i.e., replacing all $\forall x \dots$ with $\forall x L(x) \rightarrow \dots$ and all $\exists x \dots$ with $\exists x L(x) \wedge \dots$. Importantly, a formula is defined $\mathrm{Constr}(x)$ that states that $x$ is constructible, which is true iff $x$ is in $L$, i.e., if $L(x)$. And not only that, $\mathrm{Constr}(x)$ is true over $L$, meaning that the relativized version $\mathrm{Constr}(x)^L$ is provable. This implies that $\forall x L(x) \rightarrow \mathrm{Constr}(x)^L$ is proven. Therefore the class of constructible sets $x: L(x)$ obeys all ZFC and is a model of the **axiom of constructibility**, $\forall x \mathrm{Constr}(x)$ or as it is better known, $V = L$. Therefore $V = L$ is consistent with ZFC. Moreover, it is shown that within $L$ the continuum hypothesis holds, i.e., $CH^L$ is a theorem of ZFC. Finally, it is shown that $L$ is the smallest model of ZFC containing all the ordinals, and any model of ZFC containing all the ordinals has to include all of $L$.</footnote>

<footnote>Can the same technique be applied in the other direction to show that $\neg$CH is consistent? Let's assume that we could devise a formula $M(x)$ such that for every ZFC axiom $\phi$ the version $\phi^M$ holds and such that $(\neg \mathrm{CH})^M$ holds. The class construction $L$ can be relativized to $M$, as $L^M$. This is just a formula $L^M(x)$ that defines the class of constructible $x$ within</footnote>
method of forcing starts with a ground model *M* and extends to a larger, *outer model* *N* in which CH fails.

## 4.2 The Ground Model M

**Assume** CH is provable for contradiction. The proof is an algorithm that transforms a hypothetical proof of CH to an inconsistency proof of ZFC. At a high level, a model *M* is established for the finitely many axioms of ZFC that are used in the hypothetical proof of CH. The proof of CH is copied within *M*, and then *M* is expanded to a model *N* ⊃ *M* in which there exist more than ℵ₂ subsets of N and therefore ¬CH<sup>*N*</sup> is proven. At the same time the proof of CH is shown to still go through in *N* to derive CH<sup>*N*</sup>, leading to a contradiction. The same technique, building an *outer model* of a ground model *M* through the forcing method, is general and can be used to also prove consistency of CH. This exposition will focus on the proof of consistency of ¬CH, which is the harder part. Consistency of CH is covered in Section 6.2, after the main exposition.

**Relativize the proof to a set M.** Any proof of CH would be an ordered list of formulas, $\phi_1, \dots, \phi_n$ such that each $\phi_i$ is either an axiom or a logical consequence of preceding formulas in the list and $\phi_n = \text{CH}$. We might as well assume that $\phi_1, \dots, \phi_k$ ($k < n$) are the axioms used in the proof. By the Reflection Principle, a ZFC proof can be produced that there is a countable transitive set *M* where all $\phi_i$s hold, and therefore the proof goes through relativized to *M*: first prove within ZFC that $\exists M \text{ CntTrans}(M) \wedge \phi_1^M \wedge \dots \wedge \phi_k^M$ and then continue on with the rest of the proof: $\phi_{k+1}^M, \dots, \phi_n^M$. An additional subtlety is that the list $\phi_1, \dots, \phi_k$ needs to contain (1) all axioms needed for the proof of CH; (2) all axioms needed for the Reflection Principle to be applied to $\phi_1 \wedge \dots \wedge \phi_k$; (3) all axioms needed for subsequent constructions below. Still this is a finite list of axioms, so without loss of generality assume that $\phi_1, \dots, \phi_k$ includes all of them.

So far, the algorithm has produced a ZFC proof of CH<sup>*M*</sup>.

**The Skolem paradox.** This is a moment to pause and reflect. How is it possible that *M* is a *countable* set reflecting CH? The whole question of CH is whether an *uncountable* infinity exists between $\aleph_0$ and continuum. How can this question be relativized to a countable model *M*? The seeming conflict between uncountability and the existence of countable models is known as the Skolem paradox.

This is a part of the proof that initially looks like cheating. First, note that *M* contains an intact copy of $\aleph_0$. Then, *M* does *not* contain all of $2^{\aleph_0}$ but instead a countable subset of $2^{\aleph_0}$, call it $(2^{\aleph_0})^M$, which acts as the continuum within *M*. $(2^{\aleph_0})^M$ is a countable ordinal that is uncountable with respect to *M*—call it uncountable<sup>*M*</sup>—because within *M* there is no bijection between $\aleph_0$ and $(2^{\aleph_0})^M$. Moreover, any property of $2^{\aleph_0}$ expressed by a formula, such as containing all limits of Cauchy sequences (if viewed as $\mathbb{R}$), is obeyed: $(2^{\aleph_0})^M$ contains all limits of those Cauchy sequences that exist in *M*. This may all sound bizarre, but the Reflection Principle and the more general Lowenheim-Skolem reflection theorems were known well before 1963 when Cohen proved the consistency of $\neg\text{CH}$, and are way simpler to prove.

### 4.2.1 Extend ZFC to postulate a countable transitive model M

Since every proof of a formula $\phi$ can be transformed to $\exists M \text{ CntTrans}(M) \wedge \phi^M$, we may as well assume that there exists a countable transitive model *M*.

**It is safe to extend ZFC to ZFC+**. Following Weaver (2014), this observation suggests an extension of ZFC to ZFC+ that simplifies the proof: introduce a new symbol 'M', which acts as a term, together with the axiom CntTrans(*M*) and all axiom schemas of ZFC relativized to *M*. These additions cannot introduce a contradiction where none existed: suppose that a proof of contradiction follows from new axioms $\psi_1^M, \dots, \psi_l^M$, CntTrans(*M*). Now $\psi_1 \wedge \dots \wedge \psi_l$ is trivially a theorem, therefore $\exists M \text{ CntTrans}(M) \wedge \psi_1^M \wedge \dots \wedge \psi_l^M$ is a theorem by the Reflection Principle as explained above. A perfect

<footnote>the class $M(x)$, therefore $L^M \subseteq L$. However, *L* is the smallest proper class model of ZFC, and therefore $L^M = L$, which implies that $L \subset M$. Simply, for any $x$, $L(x) \to M(x)$. Now because CH holds in *L* and $\neg\text{CH}$ holds in *M*, it follows that $M \neq L$—*M* cannot be identical to *L* so it has to be properly larger. But then it follows that $\neg\forall x \text{ Constr}(x)$ or $V \neq L$ because *L* is precisely the class of sets *x* such that $\text{Constr}(x)$. This is a contradiction with consistency of $V = L$. In conclusion, there cannot be such a formula $M(x)$ where $\neg\text{CH}^M$ holds.</footnote>
syntactic copy of the proof of contradiction, with M replaced with *M*, brings a contradiction within ZFC.
Therefore, if ZFC is consistent, so is ZFC+.

In ZFC+, M is a symbol that represents *by fiat* a countable transitive model of ZFC. All ZFC theorems are theorems of ZFC+ relativized to M. The formula Ord(*x*) is Δ₀, therefore it is derivable in ZFC+ that being an ordinal in M means being an ordinal: ∀*x* ∈ M Ord(*x*)<sup>M</sup> ↔ Ord(*x*). Also, ℵ₀<sup>M</sup> = ℵ₀, i.e., “(*x* is the smallest infinite cardinal)<sup>M</sup>” ↔ “*x* is the smallest infinite cardinal”.

It is derivable in ZFC+ that there exists an ordinal α<sub>M</sub> = sup{α | Ord(α) ∧ α ∈ M} that is countable,
∉<sub>M</sub>, and is the supremum of ordinals in M. Also that the sets ℵ<sub>0</sub><sup>M</sup> < ℵ<sub>1</sub><sup>M</sup> < ℵ<sub>2</sub><sup>M</sup> < ... < ℵ<sub>α</sub><sup>M</sup> < ... are
ordinals ∈ M as long as α ≤ α<sub>M</sub>, are countable, are uncountable<sup>M</sup> and cardinals<sup>M</sup>. This means that it is
a theorem of ZFC+ that there is no surjection f ∈ M between any of these M-cardinals: the formula
¬∃f ∈ M Surj(f) ∧ Dom(f, ℵ<sub>α</sub><sup>M</sup>) ∧ Ran(f, ℵ<sub>α+1</sub><sup>M</sup>) is a theorem of ZFC+ for any ordinal α ∈ M.

The uncountable cardinals in M. All infinite sets ℵ<sub>1</sub><sup>M</sup> < ℵ<sub>2</sub><sup>M</sup> < ... are countable and uncountable<sup>M</sup>. This is a simple point that needs to be made clear, otherwise it can be enormously confusing. ℵ<sub>1</sub><sup>M</sup> is nothing other than a formula of ZFC+. It says “there exists x ∈ M ∧ x is a countable ordinal ∧ there is no surjection f : ω → x such that f ∈ M ∧ for any ordinal α ∈ M with α < x, there is a surjection f ∈ M, f : ω → α”. And M in turn is just a symbol of ZFC+. Beyond that, M does not “exist” other than syntactically—no proof that M exists is possible in ZFC by Gödel’s incompleteness theorem—and neither does ℵ<sub>1</sub><sup>M</sup> exist other than as a shorthand for the above formula that is provable in ZFC+.

Relativize the assumed proof of CH to M. Let $\phi_1, \dots, \phi_k$ be the axioms appearing in the proof of CH. The same proof, using $\phi_1^M, \dots, \phi_k^M$ instead yields $CH^M$, or equivalently $(2^{\aleph_0})^M = \aleph_1^M$.

4.3 Breaking CH by extending M to M[G]

A countable collection of $\aleph_2^M$-many subsets of $\aleph_0$. Now comes a devious trick of leveraging the countability of M to construct an extension of M that breaks CH. In particular, precisely because $\aleph_1^M$, $\aleph_2^M$, ... as well as $(2^{\aleph_0})^M$ are countable, it is easy to prove in ZFC+ the existence of a countable collection of $\aleph_2^M$-many distinct subsets of $\aleph_0$ (remember, $\aleph_0^M = \aleph_0$), none of which are in M. If these subsets can be added to M in a way so as to produce a new model, CH will fail in this new model. And this is precisely what the forcing construction does.

Representing $\aleph_2^M$-many subsets of $\aleph_0$. These subsets can be represented as a function $g : \aleph_2^M \times \aleph_0 \to \{0,1\}$: every "row" $\alpha \in \aleph_2^M$ of the "table" $g$ is a function $\aleph_0 \to \{0,1\}$, or equivalently a subset of $\omega$. As will become clear, it is convenient to represent $g$ with the collection of *finite* partial functions $p : \aleph_2^M \times \aleph_0 \to \{0,1\}$ such that $p \subset g$, i.e., all finite partial functions that agree with $g$ on all elements of their domain. All such $p$ are in M. (All hereditarily finite sets—sets with a finite number of members that are also hereditarily finite, recursively—are in M. Given a hereditarily finite set $f$, a finite number of Pairing applications establishes that $f \in M$.) We will denote this collection with $G := \{p \mid p$ is a finite partial function $\aleph_2^M \times \aleph \to \{0,1\}$ and $\forall (\alpha, n) \in \text{Dom}(p) p(\alpha, n) = g(\alpha, n)\}$. The "rows" of $g$, which by abuse of terminology will also be referred to as rows of $G$, will appear below in several examples and will be denoted by $s_\alpha$ for the $\alpha$th row.

The goal is now to add *G* to M in a manner that results in a larger model: extend M to a set M[G]
that contains every set in M as well as *G* and all sets that are implied by the presence of *G* through ZFC
axioms. M[G] should be a model: for every axiom *φ*<sup>M</sup> there should be a ZFC+ proof of *φ*<sup>M[G]</sup>. Then,
the proof of CH<sup>M</sup> can be copied to yield a ZFC+ proof of CH<sup>M[G]</sup>. If in addition ℵ<sub>2</sub><sup>M</sup> = ℵ<sub>2</sub><sup>M[G]</sup>, i.e., the
precise same (countable) ordinal that is the third smallest infinite cardinal in M is the third smallest
infinite cardinal in M[G], then a contradiction ensues.

**4.3.1 New sets that need to be in M[G]**

What kind of new sets are required to be in M[G] for all ZFC axioms $\phi$ to hold as $\phi^{M[G]}$? All kinds of sets will be required by Pairing, Power, Union, Comprehension, Replacement and AC. The Comprehension axiom presents the clearest challenge: for any formula $\phi$ of $k+1$ free variables, for any $y \in M[G]$ and any sets $w_1, \dots, w_k \in M[G]$, the set $z := \{x \in y \mid \phi^{M[G]}(x, w_1, \dots, w_k)\}$ should be in M[G].
Consider the set $\mathbb{P}$ of all finite partial functions $\aleph_2^M \times \aleph_0 \to \{0,1\}$. Each $p \in \mathbb{P}$ is in $M$ as discussed and therefore $\mathbb{P} \in M$. $\mathbb{P}$ will be an important structure: it is a partial order with sets $p \in \mathbb{P}$ ordered by $\subseteq$, and $G$ is a subset of $\mathbb{P}$ that is not in $M$. In the next section, we will define $\mathbb{P}$ as a *forcing notion* and $G$ as a *maximal ideal* over $\mathbb{P}$. For now, let's just focus on the question of what new sets in $M[G]$ are implied by $G$.

Take any set $x \in M$. Having access to the “key” $G \subsetneq \mathbb{P}$, can we generate any new subsets $y \subset x$ that may not already be in $M$?

One obvious way is to find any relation $r \subset x \times \mathbb{P}$ such that $r \in M$ and take the preimage of $x$ under $G$: $\{z \in x | (z, p) \in r$ and $p \in G\}$ is in general a set not in $M$, and if $M[G]$ is a model then it contains this set by Comprehension$^{M[G]}$. As an aside, every $x \in M$ is the preimage of $r := x \times \mathbb{P}$ under $G$. Also, $G$ is the preimage of $r := \{(p, p) | p \in \mathbb{P}\}$ under $G$. Therefore, the collection of preimages under $G$ of $x \times r$ for $x, r \in M$ and $r \subseteq x \times \mathbb{P}$ includes all of $M$ as well as $G$.

**Taking preimages transfinitely.** Is this a general form of all sets that are required to be in $M[G]$? Well, what about preimages under $G$ of $y \times r'$ where $y$ is the preimage of $x$ under $r$? These sets are also required to be in $M[G]$ if $M[G]$ is to be a model, and specifically if Comprehension$^{M[G]}$ holds. One stage of taking preimages under $G$ does not suffice; the construction needs to be applied transfinitely. The details of how to do this will be given in the next section but the idea is simple. Consider a relation $r \subset r' \times \mathbb{P}$ and $r'$ in turn being a relation $\subset r'' \times \mathbb{P}$, with $r'' \in M$ and $r''$ a relation of the same form, and so on. The preimage under $G$ of $r$, call it $r^G$, can be taken recursively as $r^G := \{r'^G | (r', p) \in r$ and $p \in G\}$. From now on, “preimage under $G$” will mean taking preimages recursively.

**Sets that could lead to contradiction.** Certain sets that contain information about $M$ lead to contradiction if included in $M[G]$. For example, consider the countable ordinal $\alpha_M$ that is the supremum of all ordinals in $M$. As it turns out, $\alpha_M \in M[G]$ would lead to contradiction:<fnref n="40" /> Because $\alpha_M$ is countable, it is just a shuffling of $\omega$ that can be expressed as a function $f: \omega \to \omega$, which can be expressed as a subset $s_f$ of $\omega \times \omega$, which can be expressed as a subset of $\omega$. Call that subset $s_{\alpha_M}$. The maps $a_M \to f \to s_f \to s_{\alpha_M}$ are definable by rather simple formulas of ZFC—they are absolute—and therefore the maps and their inverses are present in any model. So if $s_{\alpha_M} \in M[G]$ then $\alpha_M \in M[G]$ and we get a contradiction.

Therefore, not any $G$ works. If $G$ contains $s_{\alpha_M}$ for instance, it won't produce a model. To show how $M[G]$ can be made into a ZFC model, we will: (1) describe the new sets implied by $G$, and define $M[G]$ as a collection of these sets; (2) devise a strategy of how to prove $\phi^{M[G]}$ for every ZFC axiom $\phi$, which will illuminate the conditions needed so that the proofs go through, and (3) based on that reasoning, define the property that $G$ needs to have—*genericity*—so that we can produce a ZFC proof of $\phi^{M[G]}$ for every axiom $\phi$ and especially for the Comprehension axiom schema. Once these tasks are accomplished, we will finally prove that $M[G]$ is indeed a model as long as $G$ is *generic*.

Let's organize the above discussion with some definitions. First, let's explore the structure of $\mathbb{P}$, which is in $M$ and will be leveraged to convert axioms $\phi^M$ to their counterparts $\phi^{M[G]}$. $\mathbb{P}$ will be called a *forcing notion* for reasons that will become clear.

### 4.3.2 A forcing notion $\mathbb{P}$ and ideals over $\mathbb{P}$

**Definition.** A forcing notion is a partial order set (poset) $\mathbb{P} \in M$ consisting of elements $p \in \mathbb{P}$ that in the context of consistency of $\neg CH$ are *finite* partial functions $\aleph_2^M \times \aleph_0 \to \{0,1\}$.<fnref n="41" /> $\mathbb{P}$ is ordered by

<footnote n="40">⁴⁰*Proof sketch.* In ZFC+ the existence of CntTrans(M) implies the existence of a minimal model $M_{MIN}$ that is a subset of any transitive model. This result is covered by Cohen (1966) and is beyond the scope here. It is worth mentioning that every element $a$ of $M_{MIN}$ is associated with a formula $\phi_a(x)$ that is true iff $x = a$—every element is named. Of course, $M_{MIN}$ is countable. Let $\alpha_0$ be the supremum of all ordinals in $M_{MIN}$. It is consistent with ZFC+ that there is no model $N$ with supremum of ordinals $\alpha_1 > \alpha_0$. To see why, let $N$ be a model with supremum $\alpha_1$ such that $\alpha_1 > \alpha_0$ is minimal. If no such $N$ exists, we are done. Otherwise, $M_{MIN} \in N$ and “there is no model with supremum of ordinals $> \alpha_0$$^N$ is a ZFC+ theorem. Therefore, it is consistent that there is no model with supremum $\alpha_1 > \alpha_0$, because the statement holds relativized to $N$ and $N$ is a model. Now consider $\alpha_M \in M[G]$. Because the construction of $M[G]$ can be carried starting with any $M$, even with $M = M_{MIN}$, it is inconsistent for $M[G]$ to have a supremum of ordinals greater than that of $M$. Therefore, $\alpha_M \notin M[G]$. □</footnote>

<footnote n="41">⁴¹Forcing is a general technique for proving independence results beyond CH, and in some contexts elements $p$ are infinite; however, they have to be in $M$.</footnote>
inclusion: $p \le q$ whenever $p \subseteq q$ (notably, $p \le p$). Two elements $p, q$ are **compatible** if $\exists r \ p \le r \land q \le r$. In other words $p, q$ are compatible if they agree on the values they assign on the intersection of their domains and thus can be patched together to form a bigger partial function $r$. If they “clash” at a given entry $(\alpha, n)$, then they are incompatible, denoted by $p \perp q$.

The elements $p \in \mathbb{P}$ are called **forcing conditions** because each of them forces additional sentences to be true or false in $M[G]$. For example, take a simple $p = \{(\omega + 3, 7), 1\}, ((11, 3), 0)\}$. This $p$ maps the element $(\omega + 3, 7) \in \aleph_2^M \times \aleph_0$ to 1 and the element $(11, 3)$ to 0, and these choices in turn will force certain sentences in $M[G]$ to be true or false.

**Construction of $G$ from partial functions.** With the poset $\mathbb{P}$ thus defined, one way to think of $G$ is as a *subset* of $\mathbb{P}$ consisting of all $p$ that can be patched together to form some complete function $\cup G : \aleph_2^M \times \aleph_0 \to \{0, 1\}$. In order to make this work, we need to mathematically define what it means for $G$ to be a subset of $\mathbb{P}$ that is patchable together to form a complete function. The structure that works is for $G$ to be a *maximal ideal* of the poset $\mathbb{P}$, defined as follows:

**Definition.** $G$ is an **ideal** over $\mathbb{P}$ if:

1. Elements are pairwise compatible: for any $p, q \in G$ there is $r \in G$ such that $p \le r, q \le r$.

2. $G$ is downward closed: if $p \le q$ and $q \in G$ then $p \in G$.

$G$ is a **maximal ideal** if for any $p \in \mathbb{P}$ either $p \in G$ or $p$ is incompatible with some $q \in G$.

In other words, $G$ is an ideal over poset $\mathbb{P}$ if (1) every pair of elements of $G$ are compatible—patchable together to form a bigger function, and (2) it is downward closed—all partial functions that are subsets of $\cup G$ are included in $G$. $G$ is a maximal ideal if no other element of $\mathbb{P}$ can be added to it. Then, $\cup G$ is a complete function because if some element $(\alpha, n)$ was not mapped to $\{0, 1\}$, then $\{((\alpha, n), 0)\} \in \mathbb{P}$ would be an element $\notin G$ compatible with every element of $G$.

The notion of ideal over a poset is related to ideals over Boolean algebras, a topic that is beyond the scope here.<fnref n="42" />

Figure 2 displays a small portion of the poset $\mathbb{P}$ and complete function $\cup G$.

We want pairs of elements. to be compatible so that they are patchable together, we want
downward closure so that $G$ is as simple as possible, and we want maximality so that $\cup G$
forms a complete function.

4.3.3 The extended model $M[G]$

Now we can go back to defining what new sets need to be in $M[G]$ due to the presence of $G$. As discussed, the collection of preimages under $G$ of $x \times r$ for any $x, r \in M$ with $r \subseteq x \times \mathbb{P}$ needs to be in $M[G]$, and the process of taking preimages under $G$ needs to be extended transfinitely. Any model that is a superset of $M$ and contains $G$ has to have all these elements.

To conduct the transfinite construction, let's start by considering what elements are in $M$.

**What are the elements of M?** M is just a symbol of ZFC+, and the elements that provably belong to M are those elements that provably belong to any countable transitive set that reflects the ZFC axioms. Recall the definition of V as the universe of sets. V is just a ZFC formula: $V(x) := \exists\alpha V(\alpha, x)$. The formula $V(\alpha, x)$ given explicitly above can be used to make $V_\alpha$ into a set through Comprehension as long as $\alpha$ is given. In other words, $\forall\alpha \exists v \forall x V(\alpha, x) \leftrightarrow x \in v$ is a ZFC theorem that can be proven with transfinite induction.

So, how about M's elements? Well, because M is a ZFC model by ZFC+ fiat, all provable ZFC sentences are reflected in M. Every ZFC theorem $\phi$ is automatically a ZFC+ theorem $\phi^M$. In other words,

<footnote n="42">⁴²Ideals of a ring form the kernel of a ring homomorphism, which consists of all the elements that a homomorphism maps to 0. Each homomorphism of a Boolean algebra to the binary algebra {0, 1} defines a maximal ideal of all elements that map to 0. A poset is not a Boolean algebra but it can be embedded in a Boolean algebra. In most literature on CH, the dual concept of a *filter* is used and the poset is reversed for this to work: $p \le q$ whenever $p \supseteq q$. The complement of a maximal ideal is an *ultrafilter* that maps elements to 1. Here I follow the approach of Weaver (2014) that I find more natural because $p \subseteq q$ resembles $p \le q$.</footnote>
<figure><img src="image_4.png" /><figcaption>Figure 2: **The forcing notion $P$ and table $\bigcup G$.** $P$ consists of finite partial functions $\aleph_2^M \times \aleph_0 \to \{0,1\}$, and all of $P$ is in $M$. The members of $P$ are partially ordered by inclusion, and the ones that are compatible can be patched together to form bigger functions. For example, $p, q$, and $s$ are patchable to form $v$. $p$ is compatible with $r$ as well, but clashes on the top left entry with $t$ and $u$. Also $r, t$ and $u$ are patchable together to form $w$. $P$ continues upward to contain larger and larger functions, but always finite, whose limits are infinite (but not necessarily complete) functions $\aleph_2^M \times \aleph_0 \to \{0,1\}$. Every infinite partial function $\aleph_2^M \times \aleph_0 \to \{0,1\}$ is a limit $\notin P$. The function $\bigcup G$ that will be constructed in this proof is a *complete* function, a very special kind of limit.</figcaption></figure>

$\forall \alpha \in M \exists v \in M \forall x \in M V^M(\alpha, x) \leftrightarrow x \in v$ is a ZFC+ theorem. Therefore, the $V$ hierarchy can be defined within $M$ except that it will be shorter and thinner.

**M is short and thin.** It is provable in ZFC+ that $V_\alpha^M$ is a set in $M$ as long as $\alpha \in M$. Also that $M$ is “short” because it contains only the ordinals up to and not including a countable ordinal $\alpha_M$, and “thin” because it is missing a bunch of subsets at each stage of $V_\alpha^M$. It has to be so: $M$ is countable and $\omega \in M$—in fact, $\omega \in V_{\omega+1}^M$ (*why?*)—and therefore $V_{\omega+2}^M$ misses all but a countable collection of subsets of $\omega$. To understand what makes $M$ “thin”, the reader is encouraged to go back to the definition of formula $V(\alpha, x)$ and relativize it into $V^M(\alpha, x)$. In particular pay attention to $Pow(x, y) := \forall z \ z \subseteq x \leftrightarrow z \in y$. This is a key subformula that changes meaning when relativized to $M$: $\forall z \in M \ z \subseteq x \leftrightarrow z \in y$. With this “small” change, at each successor stage $\beta+1$ of the transfinite construction of $V_\alpha$, not all subsets of $V_\beta$ are added to $V_{\beta+1}$ *but only those subsets that are in* $M$. So, which subsets are these? At the very minimum, $M$ includes all of the minimal ZFC model $M_{MIN}$ that is implied by the existence of a model, as discussed by Cohen (1966).<sup>43</sup> Because the only axioms pertaining to $M$ in ZFC+ are the ZFC axioms<sup>M</sup> and *CntTrans(M)*, it is neither specified, nor excluded that $M$ is $M_{MIN}$ or some strictly larger countable model. So, which subsets of $V_\beta$ are included in $V_{\beta+1}$ is largely left unspecified, as long as they are denumerable.

**How to define new subsets in $M[G]$ using $G$.** In defining $M[G]$, each $V_\alpha^M$ needs to be modified to $V_\alpha^{M[G]}$. $G$ is available to $M[G]$ and the extra information in $G$ is available when $V_{\beta+1}^{M[G]}$ is constructed. The Cartesian product trick outlined above needs to be extended transfinitely. Analogously to sets of the form $x \times r$ above, sets $\tau \in M$ will be defined recursively to consist of ordered pairs $(\sigma, p)$ with $p \in P$ and $\sigma$ being similarly defined to $\tau$ but of lower rank. The sets thus defined are all in $M$ and will be called the *P-names* because each one of them *names* an element in $M[G]$, by taking its preimage under $G$.

The definition of P-names that follows may seem counterintuitive at first.

<footnote n="43"><sup>43</sup>However, the existence of a model cannot be proven within ZFC because then ZFC would be proving its own consistency, which contradicts Gödel's second incompleteness theorem.</footnote>
**Definition of P-name hierarchy.** Given $\mathbb{P} \in \mathbb{M}$, the set $M^{\mathbb{P}}$ of P-names is defined. A P-name is a set $\tau \in \mathbb{M}$ of the form $\tau \subseteq \{(\sigma, p) | \sigma \text{ is a P-name and } p \in \mathbb{P}\}$. The definition is by transfinite recursion, and is turned to a formula $N(\alpha, x)$ in a similar manner to the formulas $V(x)$ and $V(\alpha, x)$, left as an exercise for the reader:

* $N_0 := \emptyset$.

* $N_{\alpha+1} := \mathcal{P}(N_{\alpha} \times \mathbb{P}) \cap \mathbb{M}$, for any successor ordinal $\alpha$.

* $N_{\alpha} = \bigcup_{\beta < \alpha} N_{\alpha}$, for any limit ordinal $\alpha$.

* $M^{\mathbb{P}} := \bigcup_{\alpha \in \mathbb{O}N} N_{\alpha}$.

The collection of P-names is already in $\mathbb{M}: M^{\mathbb{P}} \subset \mathbb{M}$. Note that $M^{\mathbb{P}}$ is a ZFC+ set but a proper class and not a set in $\mathbb{M}$.<fnref n="44" /> Call it an M-class. The **name rank** of a P-name $\tau$ is defined the same way as the rank of an element of $V$ to be the least ordinal $\alpha$ such that $\tau \in N_{\alpha}$ and is denoted by $\text{nr}(\tau)$. Each P-name $\tau$ can be thought of as a set of “potential” elements. The choice of $G$ determines which of these elements materialize and which ones vanish. For example say $\tau = \{(\sigma, p), (\rho, q), (\pi, r), (\pi, q)\}$, where $\sigma = \{(\pi, r), (\rho, q)\}$, $\rho = \{(o, q)\}$, $\pi = \{(o, q), (o, p)\}$, $o = \{(\emptyset, p)\}$. A couple of examples of how things could turn out depending of $G$:

* Let's say that $G$ contains $p$ and $r$ but not $q$. Then, $\xi = \{\emptyset\}$, $\pi = \{\xi\} = \{\{\emptyset\}\}$, $\rho = \emptyset$, $\sigma = \{\pi\} = \{\{\{\emptyset\}\}\}$, and $\tau = \{\sigma, \pi\} = \{\{\emptyset\}\}$, $\{\{\{\emptyset\}\}\}$.

* Instead, say that $G$ contains $q$ but not $p, r$. Then $\xi = \emptyset$, $\pi = \{\emptyset\}$, $\rho = \{\emptyset\} = \pi$, $\sigma = \{\{\emptyset\}\}$, and $\tau = \{\rho, \pi\} = \{\pi\} = \{\{\emptyset\}\}$. Notice how $\rho, \pi$ collapse here but not in the previous case.

Given any $\tau \in M^{\mathbb{P}}$, the preimage of $\tau$ under $G$ has to be in $M[G]$. What is not clear at all is whether those are all the elements $M[G]$ needs to be a model. Indeed we will show that as long as $G$ is *generic* (a property that we will define soon), those are all the elements required.

The preimages of P-names under $G$ taken with transfinite recursion will be called $G$-evaluations:

**Definition: the evaluation of $\tau$ by $G$.** Given P-name $\tau$, its evaluation $\tau^G \in M[G]$ is defined recursively to be $\{\sigma^G | (\sigma, p) \in \tau \text{ for some } p \in G\}$.

**Cosmetic change to P-names.** Notice that if $p \le q$ and $(\sigma, p) \in \tau$, then whenever $q \in G$, by downward closure $p \in G$ and therefore $\sigma^G \in \tau^G$ whether or not $(\sigma, q) \in \tau$; the presence or absence of $(\sigma, q) \in \tau$ makes no difference. For that reason, if $(\sigma, p) \in \tau$ we may as well assume that $(\sigma, q) \in \tau$ for all $q \ge p$. This is a cosmetic change to the definition of P-names that simplifies their structure, as described by Weaver (2014). From now on we adopt this convention, and we modify $N_{\alpha}$ to be the subset of elements in the above definition that additionally obey this condition. This will simplify some subsequent proofs.

Now we are ready to define the extended set $M[G]$:

$$M[G] := \{\tau^G | \tau \in M^{\mathbb{P}}\}$$

That's it! Elegantly, $M[G]$ is just the set of preimages under $G$ of P-names.

$M$ is a subset of $M[G]$; to show that, define a **canonical P-name** $\tilde{x} \in \mathbb{M}$ for each $x \in \mathbb{M}$ recursively on the rank of $x$ by $\tilde{x} = \{(\tilde{y}, p) | y \in x \text{ and } p \in \mathbb{P}\}$. The idea is that all the elements of $x$ are tagged by every element of $\mathbb{P}$. No matter which elements $G$ contains, $\tilde{x}^G$ always equals $\{\tilde{y}^G | y \in x\}$ which equals $\{y | y \in x\} = x$ by transfinite induction on $\text{rank}(x)$, assuming $\tilde{y}^G = y$ holds for all sets of smaller rank than $x$. Therefore, for all $x \in \mathbb{M}$ we have $\tilde{x}^G = x$ therefore $x \in M[G]$.

**Proposition.** $M \subset M[G]$. □

<footnote n="44">⁴⁴ A proper class is always of the same height—has the same ordinals—as the universe. If not, then let $\alpha_{MAX}$ be the maximal ordinal of the proper class $P(x)$. Then $\forall x (P(x) \rightarrow x \in V_{\alpha_{MAX}+1})$ therefore use Comprehension to form the set $\{x \in V_{\alpha_{MAX}+1} | P(x)\}$. A proper class with respect to the universe of sets $V$—i.e., a proper class—can be put in a bijection with all ordinals in $\mathbb{O}N$. A proper class with respect to a set model such as $\mathbb{M}$ is always a set because $\mathbb{M}$ is a set and moreover it is “short”. Specifically $M^{\mathbb{P}}$ has height $\alpha_{\mathbb{M}}$, which is a countable ordinal. This makes $M^{\mathbb{P}}$ a set with respect to $V$, but of the same height as $\mathbb{M}$ and therefore a proper class with respect to $\mathbb{M}$.</footnote>
<figure><img src="image_5.png" /><figcaption>Figure 3: **Definition of extended model** M[G]. The ground model M contains M<sup>P</sup>, the P-names. M<sup>P</sup> is a ZFC+ set and within M it is a proper class and not a set. P-names are transfinitely defined within M. The preimage of each P-name τ under G is defined through transfinite recursion: τ<sup>G</sup> := {σ<sup>G</sup> | (σ, p) ∈ τ and p ∈ G}. Then, M[G] := {τ<sup>G</sup> | τ ∈ M<sup>P</sup>} . Every set x ∈ M is a member of M[G] by defining the canonical ȳ = {(ȳ, p) | y ∈ x and p ∈ P} such that ȳ<sup>G</sup> = x. G is the preimage of Γ := {(p, p) | p ∈ P} ∈ M.</figcaption></figure>

Does G ∈ M[G]? To show that, we need to demonstrate a P-name evaluating to G. The following
simple one works:

$$
\Gamma := \{(\check{p}, p) \mid p \in \mathbb{P}\}
$$

Then verify that $\Gamma^G = \{\check{p}^G \mid p \in G\} = \{p \mid p \in G\} = G$. Elegantly, $G \in M[G]$.

Therefore M[G] is indeed bigger than M: it contains G, which is not in M.

How about any new ordinals—might M[G] be “taller” than M? No, as can be shown by a simple induction on rank(τ<sup>G</sup>), which is always ≤ nr(τ) < α<sub>M</sub>. Therefore M[G] contains exactly the same ordinals as M. However, M[G] contains additional sets at infinite stages V<sub>α</sub><sup>M[G]</sup> so it is a bit “thicker” than M.

To recap, the P-names are already in M and are hierarchical nested relations between elements of M and P. Given that G is in M[G], the preimage of each of these relations has to be in M[G] if M[G] has any hope of being a model: Comprehension<sup>M[G]</sup> requires that. As it turns out, M[G] is the minimal model that is an extension of M and contains G: if N is such a model, then M[G] ⊆ N because Comprehension requires that every G-evaluation of a P-name is a member of N. Figure 3 illustrates the construction of M[G] from M. Of course, we are yet to show how to define G so that that M[G] is a model of ZFC. Indeed M[G] will not be a model in general if G is not generic.

**How** ∈ **works within** M[G]. In the next sections we will describe the property of genericity of G that ensures M[G] is a model of ZFC. Before proceeding, some intuition is useful on how M[G] “works” and in particular how “∈” is affected by the choice of G. Think of two members σ<sup>G</sup>, τ<sup>G</sup> of M[G]. What are the conditions on σ, τ ∈ M<sup>P</sup> and G that make σ<sup>G</sup> ∈ τ<sup>G</sup> true? One may be tempted to say (σ, p) ∈ τ for some p ∈ G. This seems perfectly reasonable, but unfortunately it has a bug. To detect the bug, let’s recall what τ<sup>G</sup> is defined to be: τ<sup>G</sup> := {σ<sup>G</sup> | (σ, p) ∈ τ for some p ∈ G}. Before reading further, can you detect the bug? ... If you did, congratulations! If not, it does seem fine to require (σ, p) ∈ τ for some p ∈ G verbatim from the definition. Well, what if (ρ, p) ∈ τ for some p ∈ G and moreover ρ<sup>G</sup> = σ<sup>G</sup>? This much weaker condition also has the effect of making σ<sup>G</sup> ∈ τ<sup>G</sup> true. As we saw in an example above, it is the rule rather than the exception for σ ≠ ρ while σ<sup>G</sup> = ρ<sup>G</sup>. Therefore, to define membership in M[G] we first have to define equality. Moreover, equality better be extensional: we want τ<sup>G</sup> = υ<sup>G</sup> iff σ<sup>G</sup> ∈ τ<sup>G</sup> ↔ σ<sup>G</sup> ∈ υ<sup>G</sup>. Therefore, equality needs to be defined in terms of membership, which needs to be
defined in terms of equality, leading to a potential pitfall of circular reasoning. Fortunately, there is a way out: equality and membership are defined simultaneously in a transfinite recursive manner.

Keeping this in mind, let's proceed to ask what conditions $G$ and $M[G]$ need to have so that $M[G]$ is a model.

## 4.4 Genericity and Forcing

### 4.4.1 How to transfer Comprehension to $M[G]$

$M[G]$ is the set of all preimages under $G$ of $\mathbb{P}$-names in $M^\mathbb{P}$— the $G$-interpretations. For $M[G]$ to be a model, all these preimages are necessary because of Comprehension, but it is not clear that they are sufficient. To show that $M[G]$ is a model, we need a metatheorem/algorithm that produces a ZFC+ proof of $\phi^{M[G]}$ for every input axiom $\phi$.<fnref n="45" />

Let's start with the most versatile ZFC axiom for creating new sets: Comprehension. For every set $y$ and formula $\phi(x)^{46}$, all $x \in y$ that satisfy $\phi(x)$ form a new set $z := \{x \in y | \phi(x)\}$. How do we ensure that there is a ZFC+ proof schema for Comprehension$^{M[G]}$? For any $\tau^G \in M[G]$, we need a ZFC+ proof that $z := \{\sigma^G \in \tau^G | \phi^{M[G]}(\sigma^G)\}$ is a set in $M[G]$. Equivalently, we need to show that $z = v^G$ for some $\mathbb{P}$-name $v \in M^\mathbb{P}$.

What axioms can ZFC+ leverage to prove this? An obvious guess is Comprehension$^M$. We want to use Comprehension$^M$ to prove Comprehension$^{M[G]}$. So let's write down how Comprehension$^M$ could yield $v$: it would look like $v := \{x \in y | \psi_\phi^{M}(x)\}$ for some formula $\psi_\phi$ relativized to $M$ that depends on $\phi$, and for some $y \in M$ that depends on $\tau^G$.

Every element of $M[G]$ has a counterpart in $M$: its $\mathbb{P}$-name. Every $\sigma^G \in \tau^G$ corresponds to $(\sigma, p) \in \tau$ for some $p \in G$.<fnref n="47" /> So we are starting to see the form that Comprehension$^M$ ought to take:

$$v := \{(\sigma, p) \in \tau | \psi_{\phi}^{M}(\sigma, p)\}.$$

Notice that any such $v \in M$ would automatically be in $M^\mathbb{P}$ by Comprehension$^M$. The question now is how to device a $\psi_\phi^M$ that will achieve the feat of $v^G$ being equal to $\{\sigma^G \in \tau^G | \phi^{M[G]}(\sigma^G)\}$.

In $M[G]$, we want to collect all $\sigma^G \in \tau^G$ that satisfy $\phi$. If we could collect within $M$ all $(\sigma, p) \in \tau$ such that $p \in G$ implies $\phi^{M[G]}(\sigma^G)$, we would be done. So let's employ some wishful thinking and imagine we can formulate some $\psi_\phi^M(\sigma, p)$ that is true in $M$ iff the presence of $p$ in $G$ implies that $\phi^{M[G]}(\sigma^G)$ is true.<fnref n="48" />

In other words, we need to form $\psi_\phi^M$ that says “$p \in G$ forces $\phi^{M[G]}(\sigma^G)$ to be true”.

And that is the idea at the heart of forcing! For every formula $\phi$ of ZFC, we will define a formula $\psi_\phi^M$ that given $\sigma \in M^\mathbb{P}$ specifies the set of **forcing conditions** $p \in \mathbb{P}$ whose presence in $G$ forces $\phi^{M[G]}(\sigma^G)$ to be true in $M[G]$. The whole point is to be able to deploy Comprehension$^M$ to prove Comprehension$^{M[G]}$.

*The main purpose of forcing is to use Comprehension in the ground model to prove Comprehension in the outer model.*

It is not at all obvious that this is possible. As it turns out, it can be done as long as $G$ is of a special kind—a *generic* $G$. And generic ideals $G$ exist as long as $M$ is countable, hence the need for $M$ to be countable.

<footnote n="45">⁴⁵As usual, this is a metatheorem. It is impossible to prove within ZFC that a set is a model of ZFC. Instead, we will provide an algorithm that given any axiom $\phi$ as input, produces a ZFC proof of $\phi^{M[G]}$. The entire algorithm can be shown as a single arithmetic theorem in PA.</footnote>

<footnote n="46">⁴⁶Suppressing extra parameters $w_i$.</footnote>

<footnote n="47">⁴⁷The discussion in the previous section of how “$\in$” works in $M[G]$ emphasized that given $\sigma, \tau \in M^\mathbb{P}$, we can have $\sigma^G \in \tau^G$ without having $(\sigma, p) \in \tau$: we just require some $(\rho, p) \in \tau$ with $\rho^G = \sigma^G$. Are we contradicting ourselves here by saying that $\sigma^G \in \tau^G$ always corresponds to $(\sigma, p) \in \tau$? A moment's reflection will reveal that there is no contradiction. Any $\sigma^G \in \tau^G$ corresponds to some $(\sigma, p) \in \tau$. In addition to that, there could be other $\sigma', \sigma''$ etc such that $\sigma'^G = \sigma''^G = \sigma^G$, and these additional $\mathbb{P}$-names may or may not appear inside $\tau$.</footnote>

<footnote n="48">⁴⁸To be perfectly clear, we want $\psi_\phi^M(\sigma, p) \iff (p \in G \rightarrow \phi^{M[G]}(\sigma^G))$.</footnote>
### 4.4.2 Properties fixed by a single condition $p$ have to be generic

Before exploring how to define formulas $\psi_{\phi}^{M}(\sigma, p)$ that say “$p$ forces $\phi^{M[G]}(\sigma^G)$ to be true”, it is illuminating to discuss the implications of the ability to do so on the properties of $G$. So, suspending disbelief for a moment, assume that for any $\phi(x_1, \dots, x_k)$, the collection of $p \in \mathbb{P}$ whose presence in $G$ guarantees the truth of sentence $\phi^{M[G]}(\sigma_1^G, \dots, \sigma_k^G)$ is a set in $\mathcal{M}$ definable with a formula $\psi_{\phi}^{M}(p, \sigma_1, \dots, \sigma_k)$. Let us for now call forcing the ability to define such a formula $\psi_{\phi}$ for every formula $\phi$.

*Let's explore this assumption down the rabbit hole of what it implies for $G$.*

**Only generic new sets can be forced into the extended model.** The subset $s_{\alpha_M}$ discussed above that encodes the supremum $\alpha_M$ of ordinals of $\mathcal{M}$, is specific. Can $s_{\alpha_M}$ possibly be in $\mathcal{M}[G]$? Well, then the formula $\phi := \text{"there is a row } \alpha \text{ in } G \text{ that equals } s_{\alpha_M}\text{"}$ or something similar would need to be forced by some $p \in G$. However, $p$ is just a finite partial function. It can always be extended in each of the finite number of rows of its domain to make sure the row differs from $s_{\alpha_M}$. Therefore $p$ cannot ensure that any row is equal to $s_{\alpha_M}$.<fnref n="49" /> No $p$ can ever force any subset in $G$ to be specific.

This motivates the notion of a **generic** subset of $\omega$. It is a subset $s$ such that any of its properties $\phi(s)$ can be ensured by fixing a finite part of $s$.<fnref n="50" />

If forcing is possible, then all subsets in $G$ are generic. This immediately does away with any worries that special subsets that create contradictions are introduced. Let's see some additional properties implied for generic subsets.

#### Examples of generic properties.

* Consider two different rows $\alpha, \beta \in \aleph_2^{M[G]}$ of $G$, corresponding to subsets $s_\alpha, s_\beta$ of $\omega$. Is it ever the case that $s_\alpha = s_\beta$? Could some $p \in G$ force them to be equal? Any $p$ only fixes a finite portion of the rows $\alpha$ and $\beta$, so it is always possible to extend $p$ so as to make $s_\alpha \neq s_\beta$. Notice the asymmetry here: whereas it is impossible for any $p$ to fix $s_\alpha = s_\beta$, many different $p$ make $s_\alpha \neq s_\beta$. No matter which $p$ we start with, we can always extend it to ensure $s_\alpha \neq s_\beta$. Therefore, because we insist that all properties of $s_\alpha, s_\beta$ are fixed by some $p$, all rows of a generic $G$ are distinct!

* Could $s_\alpha$ be missing some positions? Could we “neglect” to introduce some position $k$ to $s_\alpha$ and leave $s_\alpha[k]$ is undefined? Well, some $p$ would have to force $s_\alpha$ to be missing position $k$. However, it is always possible to extend $p$ by setting $(\alpha, k)$ to 0 or 1. Therefore, a generic $G$ is a maximal ideal and $\bigcup G$ is a complete function!

* Could $s_\alpha$ equal some subset $t \in \mathcal{M}$? Again, no finite $p \in \mathbb{P}$ can force that because $p$ can always be extended with a position ensuring $s_\alpha$ differs from $t$. Therefore, a generic $G$ contains all new subsets not in $\mathcal{M}$!

We are getting lots of freebies. All these properties are immediately implied by the yet to be demonstrated fact that every formula is forced by some element $p \in \mathbb{P}$. And all of these generic properties are highly desirable for $G$. Here is another freebie that we get:

* Consider the complete works of Shakespeare encoded in binary digits Shake[0] \dots Shake[N]. Could a subset $s_\alpha$ fail to have some position $i$ such that $s_\alpha[i : i + N] = \text{Shake}[0 : N]$? Well, some $p$ would have to force $s_\alpha$ to neglect Shakespeare's complete works. However, it is always possible to extend $p$ by finding some $i$ greater than any position of $s_\alpha$ set by $p$ and setting the next $N + 1$ positions to Shake[0 : N]. Therefore every row of a generic $G$ contains the complete works of Shakespeare (as well as every other finite piece of information in the universe) infinitely many times.<fnref n="51" />

<footnote n="49">⁴⁹Because $s_{\alpha_M} \notin \mathcal{M}[G]$, $s_{\alpha_M}$ does not have a $\mathbb{P}$-name in $\mathcal{M}$. Therefore, $\phi := \text{"there is a row } \alpha \text{ in } G \text{ that equals } s_{\alpha_M}\text{"}$ is not possible to relativize to $\mathcal{M}[G]$ and "there is a $p$ such that $\psi_\phi(p, \dots, s_{\alpha_M})$" saying that some $p$ forces $s_{\alpha_M}$ to be in $\mathcal{M}[G]$ is not possible to relativize to $\mathcal{M}$. These formulas are false in ZFC+ and meaningless for $\mathcal{M}[G]$ and $\mathcal{M}$, because they refer to terms not belonging to these models.</footnote>

<footnote n="50">⁵⁰More generally, in other applications of forcing it doesn't have to be a finite part of $s$, as long as it is a part of $s$ already present in the ground model $\mathcal{M}$. In our case, because $\mathbb{P}$ is defined to only have finite partial functions as elements, only finite conditions on $s$ are possible.</footnote>

<footnote n="51">⁵¹For any binary string $b$ and for any $i$ and any $\alpha \le \aleph_2$ there is a ZFC+ proof that $b$ appears in $|b|$ consecutive positions of $s_\alpha$ starting at a position $\ge i$, and this statement is forced by $p = \{\}$.</footnote>
This is all fantastic news. Now it remains to show that forcing is possible.

### 4.4.3 Necessity and possibility

Recapping, the desire to leverage Comprehension$^M$ to prove Comprehension$^{M[G]}$ leads naturally to wishing that every sentence $\phi^{M[G]}(\sigma^G)$ becomes true or false depending on a sentence $\psi_\phi^M(\sigma, p)$ that says “p forces $\phi^{M[G]}(\sigma^G)$ to be true”. Assuming this can be done, because any $p \in M$ has very limited information, $G$ needs to be generic. Next, we will define genericity more precisely.

Let’s fix some $\phi$ and $p$. We take the perspective of partial construction $p$ that will eventually be extended to a full $G$. Each possible extension $q \ge p$ introduces incremental information about $G$ and $M[G]$. Sometimes $p$ already has enough information to decide (to force) $\phi$ to be true or false, and other times $\phi$’s truth value may need to wait until some $q \ge p$ introduces more information.

What conditions should we impose on $p$ that force $\phi$ to be true? Some $q \ge p$ may make $\phi$ true, some $q \ge p$ may make $\phi$ false, and others may have uncertain status. Take for example $\phi := \text{"}s_\alpha[n] = 0\text{"}$. Assuming $(\alpha, n) \notin \text{Dom}(p)$, some $q \ge p$ make $\phi$ true and some make $\phi$ false, while others leave it undecided. It seems intuitively clear that $p$ lacks sufficient information to decide $\phi$. As another example, $\psi := s_\alpha \ne s_\beta$. Given a $p$ that does not already have any entries $(\alpha, n)$, $(\beta, n)$ set to different values for any $n$, some $q \ge p$ make $\psi$ true but none make $\psi$ false. Here, perhaps $p$ already has all the needed information to decide that $\psi$ is true in $M[G]$.

Our first requirement is that every sentence $\phi$ of $M[G]$ is decided by some $p \in G$. Additionally, we want stability: if $p$ decides $\phi$ to be true, then every $q \ge p$ should also decide $\phi$ to be true otherwise a contradiction could ensue.

With these two requirements in mind, let’s ask what are sufficient conditions for $p$ to decide that a sentence $\phi$ of $M[G]$ is true. What if for every $q$ extending $p$, there is some $r$ extending $q$ such that $r$ makes $\phi$ true? In this scenario, could any $q \ge p$ decide $\neg\phi$? No, because then some $r \ge q$ would decide $\phi$ and introduce a contradiction.

So this is it: $p$ should force $\phi$ if for every $q \ge p$ there is $r \ge q$ such that $r$ makes $\phi$ true. If this condition is met, there is no way to find a $q \ge p$ that forces $\neg\phi$. Because $\phi$ has to be true or false in $M[G]$, $p$ is forced (pun intended) to force $\phi$ to be true.

This is the basic mechanism of forcing. The truth value of every sentence $\phi^{M[G]}$ has to be decided by some $p \in \mathbb{P}$. For certain sentences this is easy: if $\phi$ asserts that $s_\alpha[n] = 1$, it is obvious how $\phi$ is decided when a $p$ is reached with $(\alpha, n)$ in its domain. However, certain other sentences may need to “wait” for potentially infinitely many choices to be made: for example, when $\phi$ asserts $s_\alpha = s_\beta$.52 If we want every sentence to be decided by a single $p$ so that Comprehension is transferred to $M[G]$, we need to find a mechanism to decide such sentences. Forcing is precisely made for this purpose.53

We define a forcing relation from ground formulas $x = y$, $x \in y$ all the way up to composite formulas, whereby $p \in \mathbb{P}$ forces a formula $\phi$ to be true through structural induction on $\phi$ whenever for every $q \ge p$ there is $r \ge q$ that forces $\phi$ to be true. The latter condition unrolls the structure of $\phi$ as will become clear.

**Necessity and possibility.** In modal logic there is the concept of **necessity** and its dual, **possibility**. An exposition of the independence of CH based on modal logic is covered in the excellent book by Smullyan and Fitting (2010). We will not need to cover modal logic here except for a basic concept at the heart of forcing. In our context specifically, necessity and possibility are taken from the point of view of a partial construction $p$. If every $q$ extending $p$ has a given property $\phi$, then $\phi$ is **necessarily true** at $p$. For example, if $p$ already fixed $(\alpha, 0) \to 1$, then for any $q \ge p$ this value is still fixed, so $\phi := s_\alpha[0] = 1$ is necessarily true. If some $q$ extending $p$ has a given property $\phi$, then $\phi$ is **possibly true** at $p$. For example, if $p$ has not fixed yet positions 1, ..., 2022 of row $\omega + 2022$, it is possibly true that $\phi := \bigwedge_{i=1}^{2022} s_{\omega+2022}[i] = 1$. The notion we actually care about is that of **necessarily possibly true**: no matter how we extend $p$ to some $q$, we can always extend $q$ to some $r$ that makes

<footnote>52Or even when $\phi$ asserts that $(\alpha, n)$ is in the domain of $\mathbb{P}$ as there are limits $p_1 \le p_2 \le \dots \le p_n \le \dots$ that do not include given entries in the domain of $\bigcup_i p_i$.</footnote>

<footnote>53The reader may ask: what if there is a sentence $\phi$ and a $p$ such that for every $q \ge p$ there is an $r \ge q$ making $\phi$ true, and at the same time there is an $r' \ge q$ making $\phi$ false? A quick reflection will reveal that this is impossible: if $r \ge q$ makes $\phi$ true, then there is no $r' \ge r$ making $\phi$ false. That’s why forcing works.</footnote>
$\phi$ true. For example, at any $p$, it is necessarily possibly true that $s_\alpha \neq s_\beta$ for $0 \le \alpha \neq \beta < \aleph_2^M$. The importance of this notion was already given above: if $\phi$ is necessarily possibly true at $p$, then there is no way to find $q \ge p$ that forces $\neg\phi$ and therefore $p$ is forced (pun intended) to force $\phi$.

In other words: if some sentence $\phi^{M[G]}$ is necessarily possibly true at $p$, then $p$ should force $\phi^{M[G]}$. Applying this concept iteratively, if $\phi^{M[G]}$ is necessarily possibly forced at $p$, then $p$ should force $\phi^{M[G]}$. Given our wishful thinking that every sentence $\phi^{M[G]}$ is decided by some $p \in \mathbb{P}$, we are forced to consider every $\phi^{M[G]}$ that is necessarily possibly forced at $p$ to be forced by $p$.

Figure 4 summarizes this main idea. The way this is implemented in the proof below is with the concept of *genericity* of $G$.

<figure><img src="image_6.png" /><figcaption>Figure 4: Deciding the truth value of a sentence $\phi^{M[G]}$ with a condition $p \in \mathbb{P}$. $\mathbb{P}$ is displayed from {} (bottom) to larger partial functions at higher levels. ($\mathbb{P}$ has infinitely many elements at each level and infinitely many edges per element.) Given a sentence $\phi$, $\mathbb{P}$ is color coded: green for true, light green for necessarily possibly true, ruby red for false, pink for necessarily possibly false, and gray for undecided. Take for example $\phi := "(s_0[0] = 1 \land \text{the value of } s_0[1] \text{ is set}) \lor \text{the value of } s_0[1] \text{ is not set}", $ referring to row $s_0$ of $G$. Let $p$ contain $(0,0) \to 0$. Then "$s_0[0] = 1$" is true for any $G \ni p$. Moreover, any $q \ge p$ that contains $(0,1) \to 0$ satisfies $\phi$. Such a $q$ is green and $p$ is light green: no matter how $p$ is extended, it is possible to extend further to some $q$ with $(0,1)$ in its domain to satisfy $\phi$; $p$ forces $\phi$ to be true. Consider now $p'$ that contains $(0,0) \to 1$. Now, the only way for $\phi$ to be true would be that "the value of $s_0[1]$ is not set". However, no matter how $p'$ is extended, it is always possible to extend it further and include $(0,1)$ in its domain, falsifying $\phi$. Therefore, $p'$ falls in the pink region. For a general $\phi$, any $p \in \mathbb{P}$ is in one of these five categories. A $p$ that makes $\phi$ true or false can only be extended to $q$ with the same property. A $p$ that makes $\phi$ necessarily possibly true (false) can only be extended to either a $q$ with the same property or to one that makes $\phi$ true (false). $\mathbb{P}$ is colored by structural recursion on $\phi$. For theorems of ZFC, all $\mathbb{P}$ is green. Ground sentences like "$s_0[0] = 1$" admit only green, red and gray. Necessarily possibly true sentence like "the value of $s_0[1]$ is set" admit only green and light green. If $G$ is generic, every sentence $\phi^{M[G]}$ has some $p \in G$ that lies in the non-gray region, as we will see.</figcaption></figure>

### 4.4.4 Genericity and forcing

The condition of "necessarily possible", stating that for every $q \ge p$ there is some $r \ge q$ with a given property, can be defined elegantly as a graph property of $\mathbb{P}$: density of a subset $D \subseteq \mathbb{P}$, $D \in \mathbb{M}$.

**Definition of dense sets over $\mathbb{P}$**. A set $D \subseteq \mathbb{P}$ is **dense** if for all $q \in \mathbb{P}$ there is $r \ge q$ such that $r \in D$. $D$ is **dense above** $p \in \mathbb{P}$ if for all $q \ge p$ there is $r \ge q$ such that $r \in D$.

To understand how the concept of density will be employed, let $D \subseteq \mathbb{P}$ be any subset, and imagine that $\phi^{M[G]}(\sigma^G)$ is true for every single $G$ that contains some element of $D$. This is a strong condition:
if $p \in G$ for some $p \in D$, then $\phi^{M[G]}(\sigma^G)$ is true. What is the implication if $D$ is dense? Then $\phi$ is necessarily possibly true at any $p$. If in addition $D \in M$ is a set in $M$ definable given parameter $\sigma \in M^P$, then we can construct formula $\psi^M(x, \sigma)$ that forces $\phi^{M[G]}(\sigma^G)$ to be true whenever $x$ is some $p \in D$.

Any $\phi^{M[G]}$ that is necessarily possibly true at some $p$ (in the sense that for any $q \ge p$ there is an $r \ge q$ such that $\phi^{M[G]}$ is true if $r \in G$) corresponds to a dense set $D_{p,\phi} := \{r \ge p \mid \phi \text{ is true at } r\}$. We will only care about dense sets $D \in M$, because we need to be able to apply Comprehension$^M$. Properties $\phi$ that correspond to dense sets $D \notin M$ will simply not relativize to $M$ so we don't need to worry about them: such sentences are true or false in ZFC+ but do not have a truth value$^{M[G]}$.

Some examples of dense sets $D \subseteq P, D \in M$: (1) the set of functions $p$ that fix element $(\alpha, n)$ is a dense subset of $P$ and is in $M$ by Comprehension$^M$;$^{54}$ (2) the set of $p$ that make rows $\alpha$ and $\beta$ different;$^{55}$ (3) the set of $p$ that make row $\alpha$ different from a specific subset $s \subseteq \omega$ in $M$; (4) the set of $p$ that make row $\alpha$ contain the binary encoding of Shakespeare's complete works in some consecutive positions; (5) the set of $p$ that are intersections of finitely many of the above sets: finitely many dense properties can be combined to form a dense property that is the $\wedge$ of all of them. Importantly, this allows combination of dense properties within composite formulas and definition of forcing with structural induction on formulas.

At last, we are ready to mathematically define what a generic $G$ is. A generic $G$ should never fail to intersect a set $D \in M$ that is dense over $P$. The formula $\Gamma \cap \check{D} \ne \emptyset$ evaluates to $G \cap D \ne \emptyset$ in $M[G]$, and is necessarily possibly true at any $p$. Therefore every $p$ should force it and consequently there should be some $q \in G \cap D$. In other words, given $D \in M$ dense over $P$, the $M[G]$-sentence $G \cap D \ne 0$ is either true or false. By our premise (wishful thinking) that every sentence of $M[G]$ is forced by some $p \in P$, either some $p$ forces $\Gamma \cap \check{D} \ne \emptyset$, or some $p$ forces $\Gamma \cap \check{D} = \emptyset$. But no $p$ can do the latter, therefore every $p$ has to do the former. To ensure that, we define genericity thus:

**Definition of genericity.** An ideal $G$ over $P$ is **generic** over $M$ if it intersects every dense set $D \in M$. That is, $G \cap D \ne \emptyset$ for every dense $D \subset P, D \in M$.

As we will see, this simple condition elegantly enables defining a forcing formula $\psi_{\phi}^{M}(p, \dots)$ for every sentence $\phi^{M[G]}$. There is a big question though, does such a $G$ exist? Generally no, but if the ground model is countable then an easy proof guarantees the existence of a generic $G$. This is precisely why a countable transitive model $M$ is postulated.

**Proposition: existence of a generic ideal.** Let $P$ be a poset over countable model $M$ and let $p \in P$. A generic ideal $G$ with $p \in G$ exists.

**Proof.** Let $D_1, D_2, D_3, \dots$ be an enumeration of all dense subsets of $P$ that are members of countable model $M$. We will create a sequence $p_0, p_1, p_2, \dots$ hitting each one of them. Let $p_0 = p$. Since $D_1$ is dense, there is $p_1 \in D_1$ with $p_1 \ge p_0$. Similarly, $p_{i+1} \in D_{i+1}$ with $p_{i+1} \ge p_i$ can always be found.

Now, we will create an ideal $G$ that contains all elements in that sequence. $G$ is simply $\{p \in P \mid p \le p_i \text{ for some } p_i \text{ in the sequence}\}$. Clearly $p_i \in G \cap D_i \ne 0$, so it remains to show that $G$ is an ideal. Indeed it is downward closed by definition, and for any two $p, q \in G$, $p \le p_i, q \le p_j$ for some $i, j$ and then pick $k \ge i, j$ and we have $p, q \le p_k$. Therefore every pair of elements of $G$ are compatible. $\square$

*The existence of generic ideals is precisely the reason M needs to be countable. G needs to hit dense subsets that are members of M, of which there are only countably many. What about dense subsets not in M? We don't care about them because they correspond to $\phi$ with constants outside $M[G]$ and therefore whose truth is settled outside $M[G]$.*

There is one additional property that $P$ needs to have to ensure that $G \notin M$: no condition $p$ should be such that it “finalizes” $G$. Formally, $p$ is an **atom** if every pair $q, r \ge p$ are compatible. Once an atom is hit, $G$ is finalized: no more “choices” need to be made. $P$ is **atomless**, if it has no atoms. In addition, if $p \le q \le p$ implies $p = q$, then $P$ is called **separative**. For forcing to go through and generate $M[G] \supseteq M$, $P$ has to be separative. The $P$ we have been discussing so far is clearly separative.

**Proposition: G is not in M.** If $P$ is a separative poset and $G$ is generic over $P$, then $G \notin M$.

<footnote>$^{54}$For instance $\{p \in P \mid \exists x \exists x \wedge p \wedge x[0] = (\alpha, n)\}$ is an instance of Comprehension$^M$ with obvious abbreviations.</footnote>

<footnote>$^{55}$For instance $\{p \in P \mid \exists n \exists x \exists y \exists x \wedge p \wedge y \wedge p \wedge x[0] = (\alpha, n) \wedge y[0] = (\beta, n) \wedge x[1] \neq y[1]\}$ with obvious abbreviations.</footnote>
**Proof.** Let $H \subseteq \mathbb{P}$, $H \in \mathcal{M}$. Consider the set $D_H := \{p \in \mathbb{P} \mid \exists q \in H \ p \perp q\}$. $D_H \in \mathcal{M}$ by Comprehension$^M$, and it is easy to see that $D_H$ is dense. Therefore $G \cap D_H \neq \emptyset$. □

With the definition of genericity in place, we are finally ready to define forcing.

**Definition: forcing.** An element $p \in \mathbb{P}$ forces the sentence $\phi(\tau_1, \dots, \tau_k)$ if $\phi^{M[G]}(\tau_1^G, \dots, \tau_k^G)$ is true for every generic ideal $G$ with $p \in G$. Forcing establishes a separate relation $\subset \mathbb{P} \times (M^\mathbb{P})^k$ for every $k$-ary formula $\phi$ in the language, denoted by $p \Vdash \phi(\tau_1, \dots, \tau_k)$.

Forcing is a generalization of truth in $\mathcal{M}$, or the notion of satisfaction: if $p \Vdash \phi$ and $\phi \to \psi$, then $p \Vdash \psi$. Notice that forcing is only defined on the sentences. Forcing establishes a separate relation among elements of the ground model $\mathcal{M}$ for every sentence $\phi$ of ZFC. Given a formula of $k$ variables and a $k$-tuple of names, the relation defines the set of $p$ that make the resulting sentence true in $\mathcal{M}[G]$.

**Notation.** The standard notation $p \Vdash \phi(\tau_1, \dots, \tau_k)$ when $\phi^{M[G]}(\tau_1^G, \dots, \tau_k^G)$ is true for every generic $G \ni p$ can be somewhat confusing. Nobody actually cares about the truth value of $\phi(\tau_1, \dots, \tau_k)$, only of $\phi^{M[G]}(\tau_1^G, \dots, \tau_k^G)$. For example, $\phi := \emptyset \in \mathbb{I}$ is forced by every $p$ because $\phi^{M[G]} := \emptyset^G \in \mathbb{I}^G := \emptyset \in \{1\}$ is true for any generic $G$. However, $\emptyset \in \mathbb{I}$ is obviously false and its truth value is irrelevant. The reason for the notation is that the forcing relation for $\phi$ is between $p, \tau_1, \dots, \tau_k$, and $G$ is *not* part of the relation. In fact, the relation is definable within $\mathcal{M}$.

The next task will be to prove that given any $\phi$ the forcing relation is definable in $\mathcal{M}$, so that the collection of $p$ that force $\phi$ is a set in $\mathcal{M}$. Once this is established, Comprehension$^M$ can be leveraged to assign truth within $\mathcal{M}[G]$. The key to showing definability of forcing is that $G$ is generic.

## 4.5 Proof that $M[G]$ is a model

The goal now is to show that $M[G]$ is a model of ZFC. This is a metatheorem: for every axiom $\phi$ of ZFC, an algorithm produces a derivation of $\phi^{M[G]}$ from $\phi^M$. Going from $\phi^M$ to $\phi^{M[G]}$ is not a simple task. It requires careful control of what statements are true in $M[G]$, and the key to that is the fundamental theorem of forcing, which is a metatheorem about ZFC rather than a theorem of ZFC.

### 4.5.1 Statement of the “fundamental theorem of forcing” metatheorem

Given a formula $\phi(x_1, \dots, x_k)$, the fundamental theorem of forcing (FTF) says that the collection of $p \in \mathbb{P}$ and $\mathbb{P}$-names $\tau_1, \dots, \tau_k$ that force $\phi$ is a set in $\mathcal{M}$, and moreover that $\phi^{M[G]}(\tau_1^G, \dots, \tau_k^G)$ is true iff some $p$ forces $\phi(\tau_1, \dots, \tau_k)$.

**The fundamental theorem of forcing (FTF).** Let $\phi(x_1, \dots, x_k)$ be a formula of $k$ free variables, $\mathbb{P}$ a separative poset in countable transitive set model $\mathcal{M}$, and $G$ a generic ideal of $\mathbb{P}$. Let $\tau_i, 1 \le i \le k$ be $\mathbb{P}$-names of maximum name rank $\alpha$.

1. **Definability.** There is a set $\mathcal{F}_\alpha^\phi \in \mathcal{M}$ such that $p \Vdash \phi(\tau_1, \dots, \tau_k)$ iff $(p, \tau_1, \dots, \tau_k) \in \mathcal{F}_\alpha^\phi$. That is to say, **the forcing relation is definable** in $\mathcal{M}$.

2. **Truth.** For any generic ideal $G$ over $\mathbb{P}$, $\phi^{M[G]}(\tau_1^G, \dots, \tau_k^G)$ iff there is a $p \in G$ such that $p \Vdash \phi(\tau_1, \dots, \tau_k)$. In other words, in $M[G]$ **any true sentence is forced by some** $p \in G$.

3. **Coherence.** If $p \Vdash \phi$ and $q \ge p$ then $q \Vdash \phi$.

The FTF is an *algorithm on ZFC syntax*: it takes a formula $\phi$ as input and produces a ZFC proof of the three assertions for $\phi$.

**How FTF is used in the proof of $CH^{M[G]}$.** In the algorithm that transforms a proof of CH into a proof of $CH^{M[G]}$, as a first step all the needed axioms $\phi_1, \dots, \phi_k$ are collected. The Reflection Principle algorithm provides a ZFC proof of existence of a countable transitive set $M$ in which every $\phi_i^M$ holds. Then the FTF algorithm generates a separate ZFC proof of FTF for each $\phi_i^M$, including recursively for its subformulas, to obtain $\phi_i^{M[G]}$. Then, the proof of CH is copied to a proof of $CH^{M[G]}$.
Before proving FTF, a few words about how it will be applied to prove Comprehension$^{M[G]}$ using Comprehension$^M$. Given a formula $\phi$, whenever $\phi^{M[G]}(\sigma^G)$ is true there is a $p$ that forces $\phi(\sigma)$ (FTF.Truth). Looking at the elements $(\sigma, p)$ of $\tau$, the maximum name rank $\text{nr}(\sigma)$ is some $\alpha$, and now $\mathcal{F}_{\alpha}^{\phi}$ contains all possible $(\sigma, p)$ in $\tau$ such that $p$ forces $\phi(\sigma)$ (FTF.Definability). Then, by Comprehension$^M$ the elements $(\sigma, p) \in \tau$ such that $(p, \sigma) \in \mathcal{F}_{\alpha}^{\phi}$ form a set in M, call it $v := \{(\sigma, p) \in \tau | (p, \sigma) \in \mathcal{F}_{\alpha}^{\phi}\}$. This is a $\mathbb{P}$-name, and it is easy to show that in fact $v^G$ is the desired set in $M[G]$ of all $\{\sigma^G \in \tau^G | \phi^{M[G]}(\sigma^G)\}$. Therefore Comprehension works in $M[G]$ by virtue of the FTF.

The above argument, which omits some technical details of why $v^G$ works and is presented in more detail below, is at the heart of the proof that $M[G]$ is a model. The FTF's main job is to transfer Comprehension as well as Power and Replacement from M to $M[G]$.<fnref n="56" />

The next task is to prove FTF. For starters, FTF.Coherence is trivial and follows from the downward closure of an ideal $G$. The other two clauses of FTF are quite technical to prove.

### 4.5.2 Architecture of the proof of FTF

The FTF for a formula $\phi$ has a ZFC+ proof by structural induction on $\phi$. The ground case “=” is the hardest. Each case follows the same proof layout.

**FTF proof layout.**

1. A general lemma establishes that for any $Z \subset \mathbb{P}, Z \in M$, if $G \subset Z$ then there is some $p \in G$ all of whose extensions are in $Z$. Think of $Z$ as a net definable in M; $Z$ will in fact be defined separately for every $\phi$ and contain all $q \in \mathbb{P}$ for which $\phi$ is possibly true. If $G$ is caught inside $Z$, the $p$ in the lemma makes $\phi$ necessarily possibly true and thereby forces $\phi$. The existence of a $p$ all of whose extensions are in $Z$ is implied because $G$ is generic—this is precisely how genericity of $G$ is used in the proof of FTF.

2. The set $\mathcal{F}_{\alpha}^{\phi}$ contains all $(p, \tau_1, \dots, \tau_k)$ such that $\tau_i$'s ranks are $\le \alpha$ and $\phi^{M[G]}(\tau_1^G, \dots, \tau_k^G)$ if $p \in \mathbb{P}$. These sets are defined with a single formula $\text{Force}^{\phi}(\alpha, p, \tau_1, \dots, \tau_k)$. If $\phi$ is a composite sentence, then $\text{Force}^{\phi}$ is composed using existing formulas for the components of $\phi$ by structural induction.

3. A net $Z^{\phi} \subset \mathbb{P}$ is defined that contains all $q$ for which $\phi$ is possibly true. Importantly, $Z^{\phi}$ is proven to be in M: by induction on name rank in the ground cases $\phi := \text{"$\tau_1 = \tau_2$"}$ and "$\sigma \in \tau$", and by structural induction in the composite cases.

4. Given $\phi$ true in $M[G]$, it is shown that $G \subset Z^{\phi}$, therefore some $p \in G$ has all its extensions in $Z^{\phi}$, which implies that $\phi$ is necessarily possibly true at $p$, which means $p$ forces $\phi$. The converse is also shown.

5. The FTF for $\phi$ easily follows.

The proof is long but not difficult. Its main difficulty lies in keeping the proof structure in mind when working on the details, and paying attention to what is definable in M and what is not. Let's prove the important lemma at the top.

**Lemma: the net Z.** If generic $G \subset Z \in M$, then there is $p \in G$ all of whose extensions are in $Z$.

*This lemma is the place where genericity of G is utilized. Z ∈ M will contain all q for which a condition that ensures φ is possibly satisfied. The lemma asserts a p ∈ G for which the condition is necessarily possible, and consequently a p that forces the condition. Figure 5 displays the lemma.*

**Proof.** Since $Z \in M, \bar{Z} := \mathbb{P} \setminus Z \in M$. Let $D$ be the set of all elements $p \in \mathbb{P}$ that are either $\ge$ some $q \in \bar{Z}$, or are incompatible with every $q \in \bar{Z}$. That is, $D := \{p \in \mathbb{P} | (\exists q \in \bar{Z} p \ge q) \lor (\forall q \in \bar{Z} p \perp q)\}$. $D \in M$ by Comprehension$^M$ and is dense: let $p \in \mathbb{P}$; if $p$ is compatible with some $q \in \bar{Z}$ then a common extension exists in $D$, whereas if $p$ is incompatible with every $q \in \bar{Z}$ then it is in $D$ already. Therefore by genericity $G$ intersects $D$, say $r \in G \cap D$. Either $r$ extends some $q \in \bar{Z}$, which is impossible because downward closure would imply $q \in G$ whereas $G \subset Z$, or $r$ is incompatible with every $q \in \bar{Z}$, therefore all of $r$'s extensions are in $Z$. □

<footnote n="56">⁵⁶Another important job comes later, in showing preservation of cardinals in $M[G]$.</footnote>
<figure><img src="image_7.png" /><figcaption>Figure 5: **The net $Z \in M$ that envelopes $G$.** If $G$ (green elements is a subset of $Z \in M$, then there is $p \in G$ (pictured in red here) all of whose extensions are in $Z$. The FTF will be proven by structural induction on $\phi$; each case will involve defining a net $Z$ that includes all $q$ for which $\phi$ is possibly true or possibly forced. This lemma establishes that if all of $G$ is a subset of $Z$, then there is a $p$ for which $\phi$ is necessarily possibly true / forced, and therefore that $p$ will force $\phi$ in each case.</figcaption></figure>

### 4.5.3 Proof of FTF for equality

Following the structure of the FTF proof laid above, let's define $F_{\alpha}^{x=y}$. This is the hardest case. Equality of $\tau_1$ and $\tau_2$ in $M[G]$ depends on whether each of the elements of one are in the other, and those elements in turn may become equal or unequal or even disappear depending on $G$. We saw a simple example above of how this happens. As it turns out, equality has to be settled in a transfinite induction on name rank. Same for membership, $\in$, but FTF for equality can be used in this case. The rest of the cases are settled with structural induction on $\phi$ and are much easier.

We want all triplets $(p, \tau_1, \tau_2)$ in $M$ where $\mathrm{nr}(\tau_1), \mathrm{nr}(\tau_2) \le \alpha$, such that $p$ forces $\tau_1^G = \tau_2^G$. Therefore, $p$ must be such that it is necessarily possible that every element $\sigma^G \in \tau_1^G$ is also $\in \tau_2^G$, and vice versa. Let's start with the forward direction: whenever $q \ge p$ and $(\sigma, q) \in \tau_1$, there must be $r \ge q$ making $\sigma$ a member of $\tau_2$ (recall that $(\sigma, q) \in \tau_1$ implies that $(\sigma, r) \in \tau_1$ for any $r \ge q$). Here we have a difficulty. We may be tempted to say that $(\sigma, r)$ has to be in $\tau_2$, but as explained above on "how $\in$ works within $M[G]$", this is too strong a condition. Perhaps $(\sigma, r)$ is not in $\tau_2$ for any $r \ge q$, but instead $(\sigma', r) \in \tau_2$ and simultaneously $r$ forces $\sigma = \sigma'$.

So now we seem to arrive at circular reasoning. We need to define equality, and the only way to do that is through equality. Fortunately, $(\sigma, p) \in \tau$ always implies that the name rank of $\sigma$ is lower than the name rank of $\tau$. Therefore we can use transfinite induction on name ranks. Without further ado, the correct condition for equality triplet $(p, \tau_1, \tau_2)$ of name ranks $\le \alpha$ is:

* For every $(\sigma, q) \in \tau_1$ with $q \ge p$ there exists $(\sigma', r) \in \tau_2$ with $r \ge q$ and $(r, \sigma, \sigma') \in \mathcal{F}_{\max\{\mathrm{nr}(\sigma), \mathrm{nr}(\sigma')\}}^{x=y}$.

* Conversely, for every $(\sigma, q) \in \tau_2$ with $q \ge p$ there exists $(\sigma', r) \in \tau_1$ with $r \ge q$ and $(r, \sigma, \sigma') \in \mathcal{F}_{\max\{\mathrm{nr}(\sigma), \mathrm{nr}(\sigma')\}}^{x=y}$.

**A ZFC formula for forcing equality.** Similar to the definitions of formula $V(a, x)$ above, a single formula $\mathrm{Force}^{=}(\alpha, p, \tau_1, \tau_2)$ is defined that is true whenever $p \in \mathbb{P}$, $\tau_1, \tau_2 \in N_{\alpha}$, and $p \Vdash \tau_1 = \tau_2$. Importantly, *this formula is already relativized to* $M$. Treating $M$ for a moment as a model and not as mere syntax, $M$ "knows" whether a given $p$ forces $\tau_1^G = \tau_2^G$ in $M[G]$: it is whenever in every extension $q$ of $p$, every member $\sigma$ of $\tau_1$ (i.e., $(\sigma, q) \in \tau_1$) is possibly equal to a member $\sigma'$ of $\tau_2$ (i.e., $\exists r \ge q (\sigma', r) \in \tau_2 \wedge (r, \sigma, \sigma') \in \mathcal{F}_{\beta}^{x=y}$ for some $\beta < \alpha$), and vise versa. To bring this important point
forward, I include an “implementation” of Force$^{=}$($\alpha, p, \tau_1, \tau_2$) here:$^{57}$

Force$^{=}$($\alpha, p, \tau_1, \tau_2$) := Ord($\alpha$) ∧ p ∈ P ∧ N($\alpha, \tau_1$) ∧ N($\alpha, \tau_2$) ∧ ∃F$_{aux}$ ∈ M Fun(F$_{aux}$) ∧ Dom(F$_{aux}$, α + 1) ∧

$$ \forall \beta \in \alpha + 1 (\forall p' \forall \tau'_1 \forall \tau'_2 (p' \in P \land N(\beta, \tau'_1) \land N(\beta, \tau'_2)) \rightarrow ((q, \tau'_1, \tau'_2) \in F_{aux}[\beta] \leftrightarrow) $$

$$ (\forall(\sigma, q) \in \tau'_1 (q \geq p' \rightarrow \exists \sigma' \exists r (\sigma', r) \in \tau'_2 \land r \geq q \land \exists \delta \in \beta (r, \sigma, \sigma') \in F_{aux}[\delta]) \land) $$

$$ (\forall(\sigma, q) \in \tau'_2 (q \geq p' \rightarrow \exists \sigma' \exists r (\sigma', r) \in \tau'_1 \land r \geq q \land \exists \delta \in \beta (r, \sigma, \sigma') \in F_{aux}[\delta])) \land) $$

$$ (p, \tau_1, \tau_2) \in F_{aux}[\alpha] $$

In this formula, P is assumed to be the poset in M with respect to which N() is the name space within M. Assuming $\alpha \leq \alpha_M$ and $p, \tau_1, \tau_2 \in M$, as mentioned above the entire formula is relativized to M.$^{58}$

**How Force**$^{=}$ **works.** This formula resembles computer code. For any $\alpha$, it defines the set $F_{\alpha}^{x=y} \in M$ of triplets $(p, \tau_1, \tau_2)$ of name ranks $\leq \alpha$ whereby $\tau_1, \tau_2$ are equal if $p \in G$. It uses an auxiliary transfinite array $F_{aux}$ whose job is to store all intermediate sets $F_{aux}[\beta] := F_{\beta}^{x=y}$. Each of these sets uses the information in previous sets (i.e., $F_{\delta}^{x=y}$ for $\delta < \beta$) to define equality for name ranks up to $\beta$. At each level $\beta$, for any $\tau'_1, \tau'_2 \in N_{\beta}, p'$ forces them equal if among the extensions of $p'$ each member of $\tau'_1$ is necessarily possibly a member of $\tau'_2$ and conversely. Here, “member of $\tau'_1$” means $\sigma$ such that $(\sigma, q) \in \tau_1$ for $q \geq p$, and “$\sigma$ is possibly a member of $\tau_2$” means that there exists $r \geq q$ such that $r$ forces $\sigma = \sigma'$ and $(\sigma', r) \in \tau_2$. Having filled the entire array $F_{aux}$, the last level $\alpha$ defines the elements $p$ that force equality of input names $\tau_1, \tau_2$.

Because there are no descending chains of membership $\cdots \in \sigma_3^G \in \sigma_2^G \in \sigma_1^G \in \tau$ in ZFC, all the chains of forcing equality of $\tau_1, \tau_2$ at $p$ by requiring all members $\sigma_1$ of one to be necessarily possibly equal to some $\sigma'_1$ of the other are resolved in a finite chain of “necessarily possibly”: $\sigma_1 = \sigma'_1$ will be resolved by requiring in turn for all members $\sigma_2$ of one to be necessarily possibly equal to some $\sigma'_2$ of the other and so on. Such a chain creates a chain of membership $\sigma_i^G \in \sigma_{i-1}^G \in \cdots \in \sigma_1^G \in \tau_1$ and $i$ cannot go to infinity because of Foundation. Each of the successive levels $i$ down also requires successively increasing $p \leq q_1 \leq r_1 \leq q_2 \leq r_2 \leq \cdots \leq q_i \leq r_i$. Because the chain is finite, the final forcing condition (say, $r_i$) is a member of P rather than some kind of infinite limit.

Now, using Comprehension$^M$ each $F_{\alpha}^{x=y}$ can be defined as set of the triplets $(p, \tau_1, \tau_2) \in P \times N_{\alpha} \times N_{\alpha} \in M$ that satisfy Force$^{=}$($\alpha, p, \tau_1, \tau_2$).

$$ F_{\alpha}^{x=y} := \{x \in P \times N_{\alpha} \times N_{\alpha} \mid \exists p \exists \tau_1 \exists \tau_2 x = (p, \tau_1, \tau_2) \land Force^{=}(\alpha, p, \tau_1, \tau_2)\} \in M $$

Therefore, each $F_{\alpha}^{x=y}$ is a set in M.

Once $F_{\alpha}^{x=y}$ is defined, the proof below establishes FTF for $\phi := x = y$. Specifically, two elements $\tau_1^G$ and $\tau_2^G$ in M[G] are equal iff some $p \Vdash \tau_1 = \tau_2$ iff $(p, \tau_1, \tau_2) \in F_{\alpha}^{x=y}$. This is shown by transfinite induction on name rank $\alpha$, assuming both parts of the theorem are true for all $\beta < \alpha$, specifically for all $(\sigma, p)$ in $\tau_1$ and $\tau_2$. Because this is the hardest part of the proof of FTF, it is included here. Much of this proof is mere bookkeeping.

**Proof of FTF for equality.** Following the structure of the FTF proof the next step is to define the net Z. For equality, let $Z^-= \{q \in P \mid$ for all $(\sigma_1, q) \in \tau_1$ there is $(\sigma_2, r) \in \tau_2$ with $r \geq q$ such that $r \Vdash \sigma_1 = \sigma_2\}$. Notice that $Z^-$ is the set of q for which $\tau_1$ is possibly a subset of or equal to $\tau_2$.

By inductive assumption on name rank, FTF holds for $\sigma_1, \sigma_2$, and it follows that $Z^+ \in M$. Now let's go ahead and perform step 4 of the FTF proof layout above:

**Claim.** $\tau_1^G \subseteq \tau_2^G$ implies $G \subset Z^-$ implies $\exists p \in G \forall q \geq p q \in Z^-$ implies $\tau_1^G \subseteq \tau_2^G$. Therefore all three conditions are equivalent.

<footnote>$^{57}$A few obvious abbreviations are used: $\forall(\sigma, q) \in \tau_2...$ is not proper syntax, and it stands for $\forall x(x \in \tau_2 \rightarrow \exists \sigma \exists q x = (\sigma, q) \land ...)$.</footnote>

<footnote>$^{58}$Syntactically it is not, but replacing syntax such as $\forall \beta \in \alpha + 1...$ with $\forall \beta \in M \beta \in \alpha + 1 \rightarrow ...$ makes no difference as $\beta \in \alpha + 1$ implies $\beta \in M$ and similarly for all the other quantifiers.</footnote>
We will prove that $\tau_1^G \subseteq \tau_2^G$ implies $G \subset Z^=$, which by the net lemma implies there is $p \in G$ all of whose extensions are in $Z^=$. Then we will prove that if there is such a $p$, then $\tau_1^G \subseteq \tau_2^G$, establishing that all these three conditions are equivalent. Conversely the same argument holds for $\tau_2^G \subseteq \tau_1^G$. Then, FTF will follow easily.

**Proof of claim.** Let $\tau_1^G \subseteq \tau_2^G$. Let $p \in G$, to show that $p \in Z^=$. If there is no $(\sigma_1, p) \in \tau_1$, then $p$ vacuously satisfies the condition to be in $Z^=$. So let $(\sigma_1, p) \in \tau_1$, therefore $\sigma_1^G \in \tau_1^G$. Then there is $(\sigma_2, q) \in \tau_2$ with $q \in G$ and $\sigma_1^G = \sigma_2^G$. The name ranks of $\sigma_1, \sigma_2$ are smaller than those of $\tau_1, \tau_2$ so by induction we can assume FTF for them, so there is $r \in G$ such that $r \Vdash \sigma_1 = \sigma_2$. Now a common extension $s \supseteq p, q, r$ satisfies $(\sigma_1, s) \in \tau_1$, $(\sigma_2, s) \in \tau_2$, and $s \Vdash \sigma_1 = \sigma_2$. Therefore $p \in Z^=$.

Since $p$ was arbitrary, $G \subset Z^=$, so by the lemma there is $p \in G$ such that every $q \ge p$ is in $Z^=$. Now to show that this in turn implies $\tau_1^G \subseteq \tau_2^G$.

Let $p$ be such. Let $\sigma_1^G \in \tau_1^G$, to show $\sigma_1^G \in \tau_2^G$. There is some $q \in G$ with $(\sigma_1, q) \in \tau_1$ and we can assume $q \ge p$. Therefore every extension $q' \ge q$ is in $Z^=$ and has $(\sigma_1, q') \in \tau_1$, therefore there is $r \ge q'$ with $(\sigma_2, r) \in \tau_2$ and $r \Vdash \sigma_1 = \sigma_2$. Therefore the set $D_q$ of $r$ with $(\sigma_2, r) \in \tau_2$ and $r \Vdash \sigma_1 = \sigma_2$ is dense above $q$. By assuming FTF.Definability inductively on name rank, $D_q \in M$ (because $F_{max\{nr(\sigma_1), nr(\sigma_2)\}}^{x=y} \in M$ by inductive assumption). Since $D_q$ is dense above $q \in G$ there is some $r \in G \cap D_q$ for which $(\sigma_1, r) \in \tau_1$, $(\sigma_2, r) \in \tau_2$, and $r \Vdash \sigma_1 = \sigma_2$ therefore $\sigma_1^G = \sigma_2^G \in \tau_2^G$. Since $\sigma_1^G \in \tau_1^G$ was arbitrary, the conclusion is that $\tau_1^G \subseteq \tau_2^G$ and moreover that $p \Vdash \tau_1 \subseteq \tau_2$. This concludes the proof of the claim. $\square$

Now it remains to prove two parts of FTF: (1) $p \Vdash \tau_1 = \tau_2$ iff $(p, \tau_1, \dots, \tau_k) \in F_\alpha^{x=y}$; (2) $\tau_1^G = \tau_2^G$ iff there is $p \in G$ such that $p \Vdash \tau_1 = \tau_2$.

For (1), let $p \Vdash \tau_1 = \tau_2$. We need to show that $(p, \tau_1, \tau_2) \in F_\alpha^\neg$. The conditions of membership $F_\alpha^\neg$ say that every extension $q \ge p$ must belong to $Z^=$ and conversely with $\tau_1$ and $\tau_2$ flipped. For any $q \ge p$ we can find $G$ containing $q$, and we have just shown that $G \subset Z^=$ therefore $q \in Z^=$. The direction with $\tau_1$ and $\tau_2$ flipped is exactly the same, so $(p, \tau_1, \tau_2) \in F_\alpha^\neg$. Conversely, let $(p, \tau_1, \tau_2) \in F_\alpha^\neg$ and let $G$ be a generic ideal that contains $p$. By definition of $F_\alpha^\neg$ every extension $q \ge p$ is in $Z^=$, therefore as we just showed $\tau_1^G \subseteq \tau_2^G$. The same argument with $\tau_1$ and $\tau_2$ flipped, establishes $\tau_1^G = \tau_2^G$.

For (2), the reverse direction is trivial. So let $\tau_1^G = \tau_2^G$, therefore $G \subset Z^= \in M$ therefore by the above lemma we can find $p \in G$ such that all $q \ge p$ are in $Z^=$, therefore as we showed $p \Vdash \tau_1 \subseteq \tau_2$ and by flipping $\tau_1$ and $\tau_2$ and repeating the argument including the definition of the corresponding $Z^=$, $p \Vdash \tau_1 = \tau_2$. $\square$

### 4.5.4 Proof of the fundamental theorem of forcing for the remaining cases

Equality was the hardest case of FTF to prove. The rest of the cases are easier and follow the same proof layout. Let's first define the sets $F_\alpha^\phi$ for each structural case of $\phi$. We do not need to be elaborate—they are all similar to $Force^=$ so we will just sketch them. The reader can write down some of these formulas for fun.

$F_\alpha^{x \in y}$ contains the triplets $(p, \tau_1, \tau_2)$ such that for every $q \ge p$ there is an $r \ge q$ and $(\sigma, r) \in \tau_2$ with $r \Vdash \tau_1 = \sigma$. In other words, such that $\tau_1$ is necessarily possibly a member of $\tau_2$. (Notice that $nr(\tau_1) < \alpha$ otherwise $(p, \tau_1, \tau_2)$ is never in $F_\alpha^{x \in y}$.) The formula $Force^\epsilon$ uses a transfinite induction with $Force^\epsilon$ as a subroutine, and details are omitted. Alternatively, a combined formula $Force^\epsilon$ or $\in (\alpha, p, \tau_1, \tau_2, T)$ can be written down, where $T = 0/1$ is the type $(0 :=; 1 : \in)$, and two auxiliary arrays are defined, $F_{aux}^\neg, F_{aux}^\epsilon$ holding the respective sets of $(p, \tau_1, \tau_2)$. The resulting formula is quite long but not hard to write down and details are omitted.

$F_\alpha^{-\psi}$ contains the tuples $(p, \tau_1, \dots, \tau_k)$ such that no $q \ge p$ forces $\psi(\tau_1, \dots, \tau_k)$: no $q \ge p$ exists with $(q, \tau_1, \dots, \tau_k)$ a member of $F_\alpha^\psi$, a set assumed to be already defined by structural induction on $\phi$.

$F_\alpha^{\psi \to \chi}$ contains the tuples $(p, \tau_1, \dots, \tau_k)$ such that it is necessarily possible that $\psi(\tau_1, \dots, \tau_k)$ implies $\chi(\tau_1, \dots, \tau_k)$, i.e., such that for every $q \ge p$ that forces $\psi$ there is $r \ge q$ that forces $\chi$: for every $(q, \tau_1, \dots, \tau_k) \in F_\alpha^\psi$ with $q \ge p$ there is $(r, \tau_1, \dots, \tau_k) \in F_\alpha^\chi$ with $r \ge q$, where those latter sets are assumed defined by structural induction on $\phi$.
Finally, $\mathcal{F}_{\alpha}^{\forall x\psi}$ contains the tuples $(p, \tau_1, \dots, \tau_k)$ such that $\forall \tau \in \mathbb{M}^{\mathbb{P}}$, it is necessarily possible that $\psi(\tau, \tau_1, \dots, \tau_k)$ is forced: $\forall \tau \forall \beta$ such that $N(\beta, \tau)$ and $\forall q \ge p$ there exists $r \ge q$ that forces $\psi(\tau, \tau_1, \dots, \tau_k)$, i.e., $(r, \tau, \tau_1, \dots, \tau_k) \in \mathcal{F}_{\max(\alpha, \beta)}^{\psi}$. Here notice that $N(\beta, \tau)$ states that $\tau \in N_{\beta}$ is a $\mathbb{P}$-name of rank $\le \beta$. The reader may ask: "wait, is there no constraint on $\beta$, and can it be $> \alpha$?" Yes: by structural inductive assumption, $\mathcal{F}_{\max(\alpha, \beta)}^{\psi}$ is defined and is a set in $\mathbb{M}$. Then, by Comprehension$^M$ we can form the set of all $(p, \tau_1, \dots, \tau_k) \in \mathbb{P} \times N_{\alpha}^k \in \mathbb{M}$ such that $\forall \tau \forall \beta (N(\beta, \tau) \to \forall q \ge p \exists r \ge q (r, \tau, \tau_1, \dots, \tau_k) \in \mathcal{F}_{\max(\alpha, \beta)}^{\psi}$).

The forcing chain that decides a sentence in $\mathbb{M}[G]$. Once the sets $\mathcal{F}_{\alpha}^{\phi}$ are defined, proof of the FTF can proceed. At this point, it is instructive to ask how a sentence $\phi^{\mathbb{M}[G]}$ is decided as true or false. There is a forcing chain that goes down the structural components of $\phi$ with "necessarily possibly forces" conditions, and then down the name ranks in atomic formulas $=, \in$ again with "necessarily possibly $=$, $\in$" conditions, respectively. The chain is constructed straight from the definitions of the $\mathcal{F}$ sets.

Let's look at a simple example: $\phi(y) := y = 0 \to \forall x \neg(x \in y)$. At the bottom we have $\text{Force}^{x \in y}(\alpha, p, x, y)$ and $\text{Force}^{y=0}(\alpha, p, y, \tilde{0})$ defined for all $\alpha$ and $p$ as above. Then, $\text{Force}^{\neg(x \in y)}(\alpha, p, x, y) := \forall q \ge p \neg \text{Force}^{x \in y}(\alpha, q, x, y)$. Continuing up, $\text{Force}^{\forall x \neg(x \in y)}(\alpha, p, y) := \forall x \forall \beta (N(\beta, x) \to \forall q \ge p \exists r \ge q \text{ Force}^{\neg(x \in y)}(\max(\alpha, \beta), r, x, y)).^{59}$ Finally, $\text{Force}^{\phi}(\alpha, p, y) := \forall q \ge p (\text{Force}^{y=0}(\alpha, q, y, \tilde{0}) \to \exists r \ge q \text{ Force}^{\forall x \neg(x \in y)}(\max(\alpha, \beta), r, y))$. Unrolling this, we get:

$$ \begin{gathered} \text{Force}^{\phi}(\alpha, p, y) := \forall q \ge p (\text{Force}^{y=0}(\alpha, q, y, \tilde{0}) \to \\ \exists r \ge q \forall x \forall \beta (N(\beta, x) \to \forall s \ge r \exists t \ge s \forall u \ge t \neg \text{Force}^{x \in y}(\max(\alpha, \beta), u, x, y)) \end{gathered} $$

**Proof of FTF for $\in$.** It is instructive to go over the proof for $\in$ and note the similarity with the proof for equality. Following the FTF proof layout, first we define the net $Z^\epsilon$. Let $Z^\epsilon := \{q \in \mathbb{P} \mid$ there exists $(\sigma, r) \in \tau_2$ with $r \ge q$ and $r \vdash \tau_1 = \sigma\}$. By assuming FTF.Definability for equality it follows that $Z^\epsilon \in \mathbb{M}$.

$Z^\epsilon$ is the set of all $q$ from whose "perspective" it is possible that $\tau_1 \in \tau_2$. On the other hand, $\mathcal{F}_{\alpha}^{x \in y}$ contains all the triplets $(p, \tau_1, \tau_2)$ where from $p$'s "perspective" it is necessarily possible that $\tau_1 \in \tau_2$. Therefore, for every $(p, \tau_1, \tau_2) \in \mathcal{F}_{\alpha}^{x \in y}$ all extensions $q \ge p$ are caught in the net $Z^\epsilon$.

Next task is to show that given $\tau_1^G \in \tau_2^G$ we have $G \subset Z^\epsilon$ therefore there is a $p$ all of whose extensions are in $Z^\epsilon$ therefore $p$ forces $\tau_1 \in \tau_2$, and conversely.

Let $\tau_1^G \in \tau_2^G$. Let $p \in G$. By definition $\tau_2^G = \{\sigma^G \mid (\sigma, q) \in \tau_2$ and $q \in G\}$, therefore there is a $q \in G$ such that $(\sigma, q) \in \tau_2$ for some $\sigma^G = \tau_1^G$. By FTF.Truth for equality, there is some $r \in G$ with $r \vdash \sigma = \tau$ and we can find $s \ge p, q, r, s \in G$. Then, $(\sigma, s) \in \tau_2$, and $s \vdash \sigma = \tau$ follows from FTF.Coherence. Therefore $p \in Z^\epsilon$. Since $p$ was arbitrary, $G \subset Z^\epsilon$. Therefore, there is some $p \in G$ such that every extension $q \ge p$ is in $Z^\epsilon$.

Let $p \in G$ such that every extension $q \ge p$ is in $Z^\epsilon$. To show that $\tau_1^G \in \tau_2^G$. First, note that $\tau_2^G$ is not empty: if it were, let $q$ force $\tau_2 = \emptyset$, by assuming FTF.Truth for $=$. Then take $q' \ge q, p$. Because $q' \in Z^\epsilon$, there is an extension $r \ge q'$ with $r \vdash \tau_1 = \sigma$ for $(\sigma, r) \in \tau_2$ so the set of $r$ with this property is dense above $q$ and therefore is a set in $\mathbb{M}$ by FTF.Definability for $=$. Therefore some $r' \in G$ is in that set, contradicting $\tau_2^G = \emptyset$. Similarly, letting $\tau_2^G$ be nonempty, every element of $\tau_2^G$ by definition has the form $\sigma^G$ for some $(\sigma, q) \in \tau_2$ with $q \in G$ so let $q$ be such. Then take $q' \ge q, p$, and again there is $r \ge q'$ with $r \vdash \tau_1 = \sigma'$ for some $(\sigma', r) \in \tau_2$. Therefore the set of $r$ with that property is dense above $q$, it is in $\mathbb{M}$ by FTF.Definability for $=, \text{and therefore some } r' \in G \text{ is in that set. Therefore } \tau_1^G \in \tau_2^G$.

We just proved FTF.Truth for $\in$, namely $\tau_1^G \in \tau_2^G$ iff there is $p \in G$ such that $p \vdash \tau_1 \in \tau_2$.

For FTF.Definability, we need to show that $(p, \tau_1, \tau_2) \in \mathcal{F}_{\alpha}^{\epsilon}$ iff $p \vdash \tau_1 \in \tau_2$. If $(p, \tau_1, \tau_2) \in \mathcal{F}_{\alpha}^{\epsilon}$, then every extension $q \ge p$ belongs to $Z^\epsilon$ and we just showed that this implies $p \vdash \tau_1 \in \tau_2$. Conversely, if $p \vdash \tau_1 \in \tau_2$, let $q \ge p$. We must show that $q$ satisfies the condition "there is $r \ge q$ and $(\sigma, r) \in \tau_2$ such that $(r, \tau_1, \sigma) \in \mathcal{F}_{\max(\text{nr}(\tau_1), \text{nr}(\sigma))}^{x=y}$". Let $G$ be a generic ideal containing $q$, therefore $p \in G$ so $\tau_1^G \in \tau_2^G$.

<footnote n="59">⁵⁹Note that $\max(\alpha, \beta)$ is shorthand for asserting the existence of some ordinal $\gamma$ with the requisite property, and that $N(\beta, x)$ "type checks" $\beta$ and $x$ so there is no further need to assert for instance $\text{Ord}(\beta)$.</footnote>
Therefore $q \in Z^\epsilon$ as we just showed, so there is such an $r \ge q$ with $(r, \tau_1, \sigma) \in \mathcal{F}_{\max(\mathrm{nr}(\tau_1), \mathrm{nr}(\sigma))}^{x=y}$. By FTF.Truth on =, that implies $r \Vdash \tau_1 = \sigma$. Therefore $q$ satisfies the condition for $p \in \mathcal{F}_\alpha^\epsilon$. $\square$

The rest of the cases are easier. The nets $Z$ for each are given below:

* $Z^\neg := \{q \in \mathbb{P} | q \Vdash \psi(\tau_1, \dots, \tau_k)\}$ where $\phi := \neg \psi$.

* $Z^\rightarrow := \{q \in \mathbb{P} | \text{ either } q \Vdash \psi(\tau_1, \dots, \tau_k) \text{ or } \exists r \ge q \text{ such that } r \Vdash \chi(\tau_1, \dots, \tau_k)\}$, where $\phi := \psi \rightarrow \chi$.

* $Z^\vee := \{q \in \mathbb{P} | \text{ for every } \mathbb{P}\text{-name } \tau \text{ there is } r \ge q \text{ such that } r \Vdash \psi(\tau, \tau_1, \dots, \tau_k)\}$, where $\phi := \forall x \psi$.

The proofs use the same layout and are left as exercises. $\square$

### 4.5.5 Proof that $M[G]$ is a model of ZFC

Next comes a case analysis where every axiom of ZFC is proven for $M[G]$. The axioms that leverage FTF are Power, Comprehension and Replacement. The other axioms are simpler to prove. Most cases involves concocting the right $\mathbb{P}$-name that proves existence of the set postulated by the axiom.

**Extensionality.** Every transitive set is extensional and therefore $M[G]$ is. $\square$

**Pairing.** Let $\sigma^G, \tau^G \in M[G]$. To prove $\{\sigma^G, \tau^G\} \in M[G]$ we need to devise a $\mathbb{P}$-name that evaluates to that pair. Well, let $v := \{(\sigma, p) | p \in \mathbb{P}\} \cup \{(\tau, p) | p \in \mathbb{P}\}$. The reader can verify that $v^G = \{\sigma^G, \tau^G\}$ regardless of the choice of $G$. $\square$

**Union.** Let $\tau^G \in M[G]$, to prove $\cup \tau^G \in M[G]$. We want a $\mathbb{P}$-name for members of members of $\tau$. Let $v := \{(\rho, p) | (\rho, p) \in \sigma$ for some $(\sigma, p) \in \tau\}$. The reader can verify with some routine bookkeeping that $v^G$ is precisely the set of elements of elements of $\tau^G$. $\square$

**Power.** Any $\tau^G \in M[G]$ has subsets $s \subset \tau^G$ some of which may be in $M[G]$ and some not—after all, $M[G]$ is countable and therefore “most” subsets of any infinite $\tau^G$ are missing. The Power axiom relativized to $M[G]$ says that the collection of subsets of $\tau^G$ that are in $M[G]$ form a set in $M[G]: \mathcal{P}(\tau^G) \cap M[G] \in M[G]$. We need to find a $\mathbb{P}$-name evaluating to precisely these subsets.

Starting with $\tau$, let $\pi = \{(\sigma, p) | \sigma \subseteq \tau$ is a $\mathbb{P}$-name and $p \in \mathbb{P}\}$.<fnref n="60" /> Intuitively, $\pi$ contains as many subsets of $\tau$ as possible so it better work.

Clearly $\pi^G \subseteq \mathcal{P}(\tau^G) \cap M[G]$. To show the reverse, the FTF will be useful. Let $\sigma^G \subseteq \tau^G$ be any subset of $\tau^G$ in $M[G]$. To show that $\sigma^G \in \pi^G$ it suffices to find a $\mathbb{P}$-name $\sigma' \subseteq \tau$ such that $\sigma'^G = \sigma^G$. The following $\sigma'$ is a set in $M$ thanks to FTF:Definability: $\sigma' := \{(\rho, p) \text{ such that } p \Vdash \rho \in \sigma\}$.

To show $\sigma'^G = \sigma^G$. Let $\rho^G \in \sigma'^G$, then there is $p \in G$ such that $(\rho, p) \in \sigma'$ and $p \Vdash \rho \in \sigma$ so $\rho^G \in \sigma^G$. So $\sigma' \subseteq \sigma$. Conversely, let $\rho^G \in \sigma^G$. Using FTF:Truth, there is $p \in G$ that forces this to be true, i.e., $p \Vdash \rho \in \sigma$, therefore by definition of $\sigma'$ $(\rho, p) \in \sigma'$ which implies $\rho^G \in \sigma'^G$. $\square$

**Infinity.** It follows from $\omega \in M \subset M[G]$. $\square$

**Foundation.** It holds in every set. $\square$

**Comprehension Schema.** This axiom is the best example of using FTF. For any formula $\phi(x)$ relativized to $M[G]$ and any set $\tau^G \in M[G]$, the set $z := \{\sigma^G \in \tau^G | \phi(\sigma^G)\}$ must be shown to belong to $M[G]$.<fnref n="61" /> It suffices to devise a $\mathbb{P}$-name $v$ evaluating to $z$. With forcing in place, the obvious $\mathbb{P}$-name works:

$$v := \{(\sigma, p) \in \tau | p \Vdash \phi(\sigma)\}$$

Importantly, $v$ is a $\mathbb{P}$-name due to FTF:Definability, specifically $\{(p, \sigma) \in \mathcal{F}_{\mathrm{nr}(\tau)}^\phi | (\sigma, p) \in \tau\}$ is a set in $M$ due to Comprehension$^M$ since we already know that $\mathcal{F}_{\mathrm{nr}(\tau)}^\phi$ is a set by Definability and that $\mathrm{nr}(\sigma) < \mathrm{nr}(\tau)$.<fnref n="62" />

<footnote n="60">⁶⁰More precisely, $\pi := \{\sigma \in \mathcal{P}(\tau)^M\} \times \mathbb{P} \in M$. It easily follows that $\pi$ is a $\mathbb{P}$-name.</footnote>

<footnote n="61">⁶¹The formula $\phi$ can have additional variables, $\phi(x, x_1, \dots, x_k)$ and for any $\tau_1^G, \dots, \tau_k^G$, the set $\{\sigma^G \in \tau^G | \phi(\sigma^G, \sigma_1^G, \dots, \sigma_k^G)\}$ should be in $M[G]$. To avoid the clutter, the extra variables are suppressed.</footnote>

<footnote n="62">⁶²More explicitly, $\{x \in \mathbb{P} \times \mathbb{P}^\mathbb{M} | \exists \alpha \exists p \exists \sigma \alpha = \mathrm{nr}(\tau) \wedge x = (p, \sigma) \wedge (\sigma, p) \in \tau \wedge \mathrm{Force}^\phi(\alpha, p, \sigma)\}$.</footnote>