$\sigma=\\{\\{\emptyset\\}\\}$, and
$\tau=\\{\rho,\pi\\}=\\{\pi\\}=\\{\\{\emptyset\\}\\}$. Notice how $\rho,\pi$
collapse here but not in the previous case.

Given any $\tau\in\mathrm{M}^{\mathbb{P}}$, the preimage of $\tau$ under $G$
has to be in $\mathrm{M}[G]$. What is not clear at all is whether those are
all the elements $\mathrm{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 $\mathbb{P}$-names under $G$ taken with transfinite recursion
will be called $G$-evaluations:

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

> Cosmetic change to $\mathbb{P}$-names. Notice that if $p\leq 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\geq p$. This is a cosmetic change to the
> definition of $\mathrm{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 $\mathrm{M}[G]$:

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

That’s it! Elegantly, $\mathrm{M}[G]$ is just the set of preimages under $G$
of $\mathbb{P}$-names.

$\mathrm{M}$ is a subset of $\mathrm{M}[G]$: to show that, define a canonical
$\mathbb{P}$-name $\check{x}\in\mathrm{M}$ for each $x\in\mathrm{M}$
recursively on the rank of $x$ by $\check{x}=\\{(\check{y},p)\>|\>y\in x$ 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,
$\check{x}^{G}$ always equals $\\{\check{y}^{G}\>|\>y\in x\\}$ which equals
$\\{y\>|\>y\in x\\}=x$ by transfinite induction on $\mathrm{rank}(x)$,
assuming $\check{y}^{G}=y$ holds for all sets of smaller rank than $x$.
Therefore, for all $x\in\mathrm{M}$ we have $\check{x}^{G}=x$ therefore
$x\in\mathrm{M}[G]$.

Proposition. $\mathrm{M}\subset\mathrm{M}[G]$. $\square$

Does $G\in\mathrm{M}[G]$? To show that, we need to demonstrate a
$\mathbb{P}$-name evaluating to $G$. The following simple one works:

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

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

Therefore $\mathrm{M}[G]$ is indeed bigger than $\mathrm{M}$: it contains $G$,
which is not in $\mathrm{M}$.

How about any new ordinals—might $\mathrm{M}[G]$ be “taller” than
$\mathrm{M}$? No, as can be shown by a simple induction on
$\mathrm{rank}(\tau^{G})$, which is always
$\leq\mathrm{nr}(\tau)<\alpha_{\mathrm{M}}$. Therefore $\mathrm{M}[G]$
contains exactly the same ordinals as $\mathrm{M}$. However, $\mathrm{M}[G]$
contains additional sets at infinite stages $V_{\alpha}^{\mathrm{M}[G]}$ so it
is a bit “thicker” than $\mathrm{M}$.

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

Figure 3: Definition of extended model $\mathrm{M}[G]$. The ground model
$\mathrm{M}$ contains $\mathrm{M}^{\mathbb{P}}$, the $\mathbb{P}$-names.
$\mathrm{M}^{\mathbb{P}}$ is a ZFC+ set and within $\mathrm{M}$ it is a proper
class and not a set. $\mathbb{P}$-names are transfinitely defined within
$\mathrm{M}$. The preimage of each $\mathbb{P}$-name $\tau$ under $G$ is
defined through transfinite recursion:
$\tau^{G}:=\\{\sigma^{G}\>|\>(\sigma,p)\in\tau$ and $p\in G\\}$. Then,
$\mathrm{M}[G]:=\\{\tau^{G}\>|\>\tau\in\mathrm{M}^{\mathbb{P}}\\}$. Every set
$x\in\mathrm{M}$ is a member of $\mathrm{M}[G]$ by defining the canonical
$\check{x}=\\{(\check{y},p)\>|\>y\in x$ and $p\in\mathbb{P}\\}$ such that
$\check{x}^{G}=x$. $G$ is the preimage of
$\Gamma:=\\{(p,p)\>|\>p\in\mathbb{P}\\}\in\mathrm{M}$.

How $\in$ works within $\mathrm{M}[G]$. In the next sections we will describe
the property of genericity of $G$ that ensures $\mathrm{M}[G]$ is a model of
ZFC. Before proceeding, some intuition is useful on how $\mathrm{M}[G]$
“works” and in particular how “$\in$” is affected by the choice of $G$. Think
of two members $\sigma^{G},\tau^{G}$ of $\mathrm{M}[G]$. What are the
conditions on $\sigma,\tau\in\mathrm{M}^{\mathbb{P}}$ and $G$ that make
$\sigma^{G}\in\tau^{G}$ true? One may be tempted to say $(\sigma,p)\in\tau$
for some $p\in G$. This seems perfectly reasonable, but unfortunately it has a
bug. To detect the bug, let’s recall what $\tau^{G}$ is defined to be:
$\tau^{G}:=\\{\sigma^{G}\>|\>(\sigma,p)\in\tau$ for some $p\in G\\}$. Before
reading further, can you detect the bug? … If you did, congratulations! If
not, it does seem fine to require $(\sigma,p)\in\tau$ for some $p\in G$
verbatim from the definition. Well, what if $(\rho,p)\in\tau$ for some $p\in
G$ and moreover $\rho^{G}=\sigma^{G}$? This much weaker condition also has the
effect of making $\sigma^{G}\in\tau^{G}$ true. As we saw in an example above,
it is the rule rather than the exception for $\sigma\not=\rho$ while
$\sigma^{G}=\rho^{G}$. Therefore, to define membership in $\mathrm{M}[G]$ we
first have to define equality. Moreover, equality better be extensional: we
want $\tau^{G}=\upsilon^{G}$ iff
$\sigma^{G}\in\tau^{G}\leftrightarrow\sigma^{G}\in\upsilon^{G}$. 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
$\mathrm{M}[G]$ need to have so that $\mathrm{M}[G]$ is a model.

###  4.4 Genericity and Forcing

####  4.4.1 How to transfer Comprehension to $\mathrm{M}[G]$

$\mathrm{M}[G]$ is the set of all preimages under $G$ of $\mathbb{P}$-names in
$\mathrm{M}^{\mathbb{P}}$— the $G$-interpretations. For $\mathrm{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 $\mathrm{M}[G]$ is a model,
we need a metatheorem/algorithm that produces a ZFC+ proof of
$\phi^{\mathrm{M}[G]}$ for every input axiom $\phi$.454545As 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^{\mathrm{M}[G]}$. The entire algorithm
can be shown as a single arithmetic theorem in PA.

Let’s start with the most versatile ZFC axiom for creating new sets:
Comprehension. For every set $y$ and formula $\phi(x)$464646Suppressing extra
parameters $w_{i}$., 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 ComprehensionM[G]? For any $\tau^{G}\in\mathrm{M}[G]$, we need a
ZFC+ proof that
$z:=\\{\sigma^{G}\in\tau^{G}\>|\>\phi^{\mathrm{M}[G]}(\sigma^{G})\\}$ is a set
in $\mathrm{M}[G]$. Equivalently, we need to show that $z=\upsilon^{G}$ for
some $\mathbb{P}$-name $\upsilon\in\mathrm{M}^{\mathbb{P}}$.

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

Every element of $\mathrm{M}[G]$ has a counterpart in $\mathrm{M}$: its
$\mathbb{P}$-name. Every $\sigma^{G}\in\tau^{G}$ corresponds to
$(\sigma,p)\in\tau$ for some $p\in G$.474747The discussion in the previous
section of how “$\in$” works in $\mathrm{M}[G]$ emphasized that given
$\sigma,\tau\in\mathrm{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^{\prime},\sigma^{\prime\prime}$ etc such
that $\sigma^{\prime G}=\sigma^{\prime\prime G}=\sigma^{G}$, and these
additional $\mathbb{P}$-names may or may not appear inside $\tau$. So we are
starting to see the form that ComprehensionM ought to take:

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

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

In $\mathrm{M}[G]$, we want to collect all $\sigma^{G}\in\tau^{G}$ that
satisfy $\phi$. If we could collect within $\mathrm{M}$ all
$(\sigma,p)\in\tau$ such that $p\in G$ implies
$\phi^{\mathrm{M}[G]}(\sigma^{G})$, we would be done. So let’s employ some
wishful thinking and imagine we can formulate some
$\psi_{\phi}^{\mathrm{M}}(\sigma,p)$ that is true in $\mathrm{M}$ iff the
presence of $p$ in $G$ implies that $\phi^{\mathrm{M}[G]}(\sigma^{G})$ is
true.484848To be perfectly clear, we want
$\psi_{\phi}^{\mathrm{M}}(\sigma,p)\leftrightarrow(p\in
G\rightarrow\phi^{\mathrm{M}[G]}(\sigma^{G}))$.

In other words, we need to form $\psi_{\phi}^{\mathrm{M}}$ that says “$p\in G$
forces $\phi^{\mathrm{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}^{\mathrm{M}}$ that given
$\sigma\in\mathrm{M}^{\mathbb{P}}$ specifies the set of forcing conditions
$p\in\mathbb{P}$ whose presence in $G$ forces
$\phi^{\mathrm{M}[G]}(\sigma^{G})$ to be true in $\mathrm{M}[G]$. The whole
point is to be able to deploy ComprehensionM to prove ComprehensionM[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 $\mathrm{M}$ is countable, hence the need for $\mathrm{M}$ to
be countable.

####  4.4.2 Properties fixed by a single condition $p$ have to be generic

Before exploring how to define formulas $\psi_{\phi}^{\mathrm{M}}(\sigma,p)$
that say “$p$ forces $\phi^{\mathrm{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},\ldots,x_{k})$, the collection of $p\in\mathbb{P}$ whose presence
in $G$ guarantees the truth of sentence
$\phi^{\mathrm{M}[G]}(\sigma_{1}^{G},\ldots,\sigma_{k}^{G})$ is a set in
$\mathrm{M}$ definable with a formula
$\psi_{\phi}^{\mathrm{M}}(p,\sigma_{1},\ldots,\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_{\mathrm{M}}}$ discussed above that encodes the supremum
$\alpha_{\mathrm{M}}$ of ordinals of $\mathrm{M}$, is specific. Can
$s_{\alpha_{\mathrm{M}}}$ possibly be in $\mathrm{M}[G]$? Well, then the
formula $\phi:=$ “there is a row $\alpha$ in $G$ that equals
$s_{\alpha_{\mathrm{M}}}$” 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_{\mathrm{M}}}$. Therefore $p$ cannot ensure
that any row is equal to $s_{\alpha_{\mathrm{M}}}$.494949Because
$s_{\alpha_{\mathrm{M}}}\not\in\mathrm{M}[G]$, $s_{\alpha_{\mathrm{M}}}$ does
not have a $\mathbb{P}$-name in $\mathrm{M}$. Therefore, $\phi:=$ “there is a
row $\alpha$ in $G$ that equals $s_{\alpha_{\mathrm{M}}}$” is not possible to
relativize to $\mathrm{M}[G]$ and “there is a $p$ such that
$\psi_{\phi}(p,\ldots,s_{\alpha_{\mathrm{M}}})$” saying that some $p$ forces
$s_{\alpha_{\mathrm{M}}}$ to be in $\mathrm{M}[G]$ is not possible to
relativize to $\mathrm{M}$. These formulas are false in ZFC+ and meaningless
for $\mathrm{M}[G]$ and $\mathrm{M}$, because they refer to terms not
belonging to these models. 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$.505050More 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 $\mathrm{M}$. In our case, because $\mathbb{P}$ is
defined to only have finite partial functions as elements, only finite
conditions on $s$ are possible.

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}^{\mathrm{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}\not=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}\not=s_{\beta}$. No matter which $p$ we start with, we can always
extend it to ensure $s_{\alpha}\not=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\mathrm{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 $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
$\mathrm{Shake}[0]\cdots\mathrm{Shake}[N]$. Could a subset $s_{\alpha}$ fail
to have some position $i$ such that
$s_{\alpha}[i\>:\>i+N]=\mathrm{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
$\mathrm{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.515151For any binary string
$b$ and for any $i$ and any $\alpha\leq\aleph_{2}^{\mathrm{M}}$ there is a
ZFC+ proof that $b$ appears in $|b|$ consecutive positions of $s_{\alpha}$
starting at a position $\geq i$, and this statement is forced by $p=\\{\\}$.
Infinity is big and generic infinity contains everything infinitely many
times.

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 ComprehensionM to prove ComprehensionM[G]
leads naturally to wishing that every sentence
$\phi^{\mathrm{M}[G]}(\sigma^{G})$ becomes true or false depending on a
sentence $\psi_{\phi}^{\mathrm{M}}(\sigma,p)$ that says “$p$ forces
$\phi^{\mathrm{M}[G]}(\sigma^{G})$ to be true”. Assuming this can be done,
because any $p\in\mathrm{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\geq p$ introduces incremental information about $G$ and $\mathrm{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\geq p$ introduces more information.

What conditions should we impose on $p$ that force $\phi$ to be true? Some
$q\geq p$ may make $\phi$ true, some $q\geq p$ may make $\phi$ false, and
others may have uncertain status. Take for example $\phi:=$
“$s_{\alpha}[n]=0$”. Assuming $(\alpha,n)\not\in\mathrm{Dom}(p)$, some $q\geq
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}\not=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\geq 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 $\mathrm{M}[G]$.

Our first requirement is that every sentence $\phi$ of $\mathrm{M}[G]$ is
decided by some $p\in G$. Additionally, we want stability: if $p$ decides
$\phi$ to be true, then every $q\geq 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 ${\mathrm{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\geq p$ decide $\lnot\phi$?
No, because then some $r\geq q$ would decide $\phi$ and introduce a
contradiction.

So this is it: $p$ should force $\phi$ if for every $q\geq p$ there is $r\geq
q$ such that $r$ makes $\phi$ true. If this condition is met, there is no way
to find a $q\geq p$ that forces $\lnot\phi$. Because $\phi$ has to be true or
false in $\mathrm{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^{\mathrm{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}$.525252Or even when $\phi$ asserts that $(\alpha,n)$ is
in the domain of $\mathbb{P}$ as there are limits $p_{1}\leq
p_{2}\leq\cdots\leq p_{n}\leq\cdots$ that do not include given entries in the
domain of $\bigcup_{i}p_{i}$. If we want every sentence to be decided by a
single $p$ so that Comprehension is transferred to $\mathrm{M}[G]$, we need to
find a mechanism to decide such sentences. Forcing is precisely made for this
purpose.535353The reader may ask: what if there is a sentence $\phi$ and a $p$
such that for every $q\geq p$ there is an $r\geq q$ making $\phi$ true, and at
the same time there is an $r^{\prime}\geq q$ making $\phi$ false? A quick
reflection will reveal that this is impossible: if $r\geq q$ makes $\phi$
true, then there is no $r^{\prime}\geq r$ making $\phi$ false. That’s why
forcing works.

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\geq p$
there is $r\geq 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 $\mathrm{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\geq 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,\ldots,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 $\phi$ true. For
example, at any $p$, it is necessarily possibly true that
$s_{\alpha}\not=s_{\beta}$ for
$0\leq\alpha\not=\beta<\aleph_{2}^{\mathrm{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\geq p$ that forces $\lnot\phi$ and therefore $p$ is
forced (pun intended) to force $\phi$.

In other words: if some sentence $\phi^{\mathrm{M}[G]}$ is necessarily
possibly true at $p$, then $p$ should force $\phi^{\mathrm{M}[G]}$. Applying
this concept iteratively, if $\phi^{\mathrm{M}[G]}$ is necessarily possibly
forced at $p$, then $p$ should force $\phi^{\mathrm{M}[G]}$. Given our wishful
thinking that every sentence $\phi^{\mathrm{M}[G]}$ is decided by some
$p\in\mathbb{P}$, we are forced to consider every $\phi^{\mathrm{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 4: Deciding the truth value of a sentence $\phi^{\mathrm{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$
the value of $s_{0}[1]$ is set$)\lor$ the value of $s_{0}[1]$ 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\geq 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^{\prime}$ 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^{\prime}$ is extended, it is always possible to extend it
further and include $(0,1)$ in its domain, falsifying $\phi$. Therefore,
$p^{\prime}$ 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^{\mathrm{M}[G]}$ has some $p\in G$ that lies in the non-
gray region, as we will see.

####  4.4.4 Genericity and forcing

The condition of “necessarily possible”, stating that for every $q\geq p$
there is some $r\geq 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\mathrm{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\geq q$ such that $r\in D$. $D$
> is dense above $p\in\mathbb{P}$ if for all $q\geq p$ there is $r\geq 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^{\mathrm{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^{\mathrm{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\mathrm{M}$ is a set in $\mathrm{M}$ definable given parameter
$\sigma\in\mathrm{M}^{\mathbb{P}}$, then we can construct formula
$\psi^{\mathrm{M}}(x,\sigma)$ that forces $\phi^{\mathrm{M}[G]}(\sigma^{G})$
to be true whenever $x$ is some $p\in D$.

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

Some examples of dense sets $D\subseteq\mathbb{P},D\in M$: (1) the set of
functions $p$ that fix element $(\alpha,n)$ is a dense subset of $\mathbb{P}$
and is in $\mathrm{M}$ by ComprehensionM;545454For instance
$\\{p\in\mathbb{P}\>|\>\exists x\>x\in p\land x[0]=(\alpha,n)\\}$ is an
instance of ComprehensionM with obvious abbreviations. (2) the set of $p$ that
make rows $\alpha$ and $\beta$ different;555555For instance
$\\{p\in\mathbb{P}\>|\>\exists n\>\exists x\>\exists y\>x\in p\land y\in
p\land x[0]=(\alpha,n)\land y[0]=(\beta,n)\land x[1]\not=y[1]\\}$ with obvious
abbreviations. (3) the set of $p$ that make row $\alpha$ different from a
specific subset $s\subseteq\omega$ in $\mathrm{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 $\land$ 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
$\mathbb{P}$. The formula $\Gamma\cap\check{D}\not=\check{\emptyset}$
evaluates to $G\cap D\not=\emptyset$ in $\mathrm{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\mathrm{M}$
dense over $\mathbb{P}$, the $\mathrm{M}[G]$-sentence $G\cap D\neq 0$ is
either true or false. By our premise (wishful thinking) that every sentence of
$\mathrm{M}[G]$ is forced by some $p\in\mathbb{P}$, either some $p$ forces
$\Gamma\cap\check{D}\not=\check{\emptyset}$, or some $p$ forces
$\Gamma\cap\check{D}=\check{\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 $\mathbb{P}$ is generic over $M$
> if it intersects every dense set $D\in M$. That is, $G\cap D\neq\emptyset$
> for every dense $D\subset\mathbb{P},D\in\mathrm{M}$.

As we will see, this simple condition elegantly enables defining a forcing
formula $\psi_{\phi}^{\mathrm{M}}(p,\ldots)$ for every sentence
$\phi^{\mathrm{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 $\mathrm{M}$ is postulated.

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

Proof. Let $D_{1},D_{2},D_{3},\ldots$ be an enumeration of all dense subsets
of $\mathbb{P}$ that are members of countable model $\mathrm{M}$. We will
create a sequence $p_{0},p_{1},p_{2},\ldots$ hitting each one of them. Let
$p_{0}=p$. Since $D_{1}$ is dense, there is $p_{1}\in D_{1}$ with $p_{1}\geq
p_{0}$. Similarly, $p_{i+1}\in D_{i+1}$ with $p_{i+1}\geq 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\mathbb{P}\>|\>p\leq p_{i}$ for some $p_{i}$ in the
sequence$\\}$. Clearly $p_{i}\in G\cap D_{i}\not=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\leq p_{i},q\leq p_{j}$ for some $i,j$ and then pick $k\geq
i,j$ and we have $p,q\leq p_{k}$. Therefore every pair of elements of $G$ are
compatible. $\square$

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

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

Proposition: $G$ is not in $\mathrm{M}$. If $\mathbb{P}$ is a separative poset
and $G$ is generic over $\mathbb{P}$, then $G\not\in\mathrm{M}$.

Proof. Let $H\subseteq\mathbb{P}$, $H\in\mathrm{M}$. Consider the set
$D_{H}:=\\{p\in\mathbb{P}\>|\>\exists q\in H\>p\perp q\\}$.
$D_{H}\in\mathrm{M}$ by ComprehensionM, and it is easy to see that $D_{H}$ is
dense. Therefore $G\cap D_{H}\not=\emptyset$. $\square$

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},\ldots,\tau_{k})$ if
> $\phi^{\mathrm{M}[G]}(\tau_{1}^{G},\ldots,\tau_{k}^{G})$ is true for every
> generic ideal $G$ with $p\in G$. Forcing establishes a separate relation
> $\subset\mathbb{P}\times(\mathrm{M}^{\mathbb{P}})^{k}$ for every $k$-ary
> formula $\phi$ in the language, denoted by
> $p\Vdash\phi(\tau_{1},\ldots,\tau_{k})$.

Forcing is a generalization of truth in $\mathrm{M}$, or the notion of
satisfaction: if $p\Vdash\phi$ and $\phi\rightarrow\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 $\mathrm{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 ${\mathrm{M}[G]}$.

> Notation. The standard notation $p\Vdash\phi(\tau_{1},\ldots,\tau_{k})$ when
> $\phi^{\mathrm{M}[G]}(\tau_{1}^{G},\ldots,\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},\ldots,\tau_{k})$, only of
> $\phi^{\mathrm{M}[G]}(\tau_{1}^{G},\ldots,\tau_{k}^{G})$. For example,
> $\phi:=\check{0}\in\check{1}$ is forced by every $p$ because
> $\phi^{\mathrm{M}[G]}:=\check{0}^{G}\in\check{1}^{G}:=0\in 1$ is true for
> any generic $G$. However, $\check{0}\in\check{1}$ 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},\ldots,\tau_{k}$, and $G$ is
> not part of the relation. In fact, the relation is definable within
> $\mathrm{M}$.

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

###  4.5 Proof that $\mathrm{M}[G]$ is a model

The goal now is to show that $\mathrm{M}[G]$ is a model of ZFC. This is a
metatheorem: for every axiom $\phi$ of ZFC, an algorithm produces a derivation
of $\phi^{\mathrm{M}[G]}$ from $\phi^{\mathrm{M}}$. Going from
$\phi^{\mathrm{M}}$ to $\phi^{\mathrm{M}[G]}$ is not a simple task. It
requires careful control of what statements are true in $\mathrm{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},\ldots,x_{k})$, the fundamental theorem of forcing
(FTF) says that the collection of $p\in\mathbb{P}$ and $\mathbb{P}$-names
$\tau_{1},\ldots,\tau_{k}$ that force $\phi$ is a set in $\mathrm{M}$, and
moreover that $\phi^{\mathrm{M}[G]}(\tau_{1}^{G},\ldots,\tau_{k}^{G})$ is true
iff some $p$ forces $\phi(\tau_{1},\ldots,\tau_{k})$.

> The fundamental theorem of forcing (FTF). Let $\phi(x_{1},\ldots,x_{k})$ be
> a formula of $k$ free variables, $\mathbb{P}$ a separative poset in
> countable transitive set model $\mathrm{M}$, and $G$ a generic ideal of
> $\mathbb{P}$. Let $\tau_{i},1\leq i\leq k$ be $\mathbb{P}$-names of maximum
> name rank $\alpha$.
>
>   1. 1.
>
> Definability. There is a set $\mathcal{F}^{\phi}_{\alpha}\in\mathrm{M}$ such
> that $p\Vdash\phi(\tau_{1},\ldots,\tau_{k})$ iff
> $(p,\tau_{1},\ldots,\tau_{k})\in\mathcal{F}^{\phi}_{\alpha}$. That is to
> say, the forcing relation is definable in $\mathrm{M}$.
>
>   2. 2.
>
> Truth. For any generic ideal $G$ over $\mathbb{P}$,
> $\phi^{\mathrm{M}[G]}(\tau_{1}^{G},\ldots,\tau_{k}^{G})$ iff there is a
> $p\in G$ such that $p\Vdash\phi(\tau_{1},\ldots,\tau_{k})$. In other words,
> in $\mathrm{M}[G]$ any true sentence is forced by some $p\in G$.
>
>   3. 3.
>
> Coherence. If $p\Vdash\phi$ and $q\geq 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 $\mathrm{CH}^{\mathrm{M}[G]}$. In the
algorithm that transforms a proof of $\mathrm{CH}$ into a proof of
$\mathrm{CH}^{\mathrm{M}[G]}$, as a first step all the needed axioms
$\phi_{1},\ldots,\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 $\mathrm{CH}$ is
copied to a proof of $\mathrm{CH}^{M[G]}$.

Before proving FTF, a few words about how it will be applied to prove
ComprehensionM[G] using ComprehensionM. Given a formula $\phi$, whenever
$\phi^{\mathrm{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 $\mathrm{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
ComprehensionM the elements $(\sigma,p)\in\tau$ such that
$(p,\sigma)\in\mathcal{F}_{\alpha}^{\phi}$ form a set in $\mathrm{M}$, call it
$\upsilon:=\\{(\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
$\upsilon^{G}$ is the desired set in $\mathrm{M}[G]$ of all
$\\{\sigma^{G}\in\tau^{G}\>|\>\phi^{\mathrm{M}[G]}(\sigma^{G})\\}$. Therefore
Comprehension works in $\mathrm{M}[G]$ by virtue of the FTF.

The above argument, which omits some technical details of why $\upsilon^{G}$
works and is presented in more detail below, is at the heart of the proof that
$\mathrm{M}[G]$ is a model. The FTF’s main job is to transfer Comprehension as
well as Power and Replacement from $\mathrm{M}$ to
$\mathrm{M}[G]$.565656Another important job comes later, in showing
preservation of cardinals in $\mathrm{M}[G]$.

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. 1.

A general lemma establishes that for any $Z\subset\mathbb{P},Z\in\mathrm{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 $\mathrm{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. 2.

The set $\mathcal{F}_{\alpha}^{\phi}$ contains all
$(p,\tau_{1},\ldots,\tau_{k})$ such that $\tau_{i}$’s ranks are $\leq\alpha$
and $\phi^{\mathrm{M}[G]}(\tau_{1}^{G},\ldots,\tau_{k}^{G})$ if
$p\in\mathbb{P}$. These sets are defined with a single formula
$Force^{\phi}(\alpha,p,\tau_{1},\ldots,\tau_{k})$. If $\phi$ is a composite
sentence, then $Force^{\phi}$ is composed using existing formulas for the
components of $\phi$ by structural induction.

  3. 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
$\mathrm{M}$: by induction on name rank in the ground cases $\phi:=$
“$\tau_{1}=\tau_{2}$” and “$\sigma\in\tau$", and by structural induction in
the composite cases.

  4. 4.

Given $\phi$ true in $\mathrm{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. 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 $\mathrm{M}$ and what is not. Let’s prove the important
lemma at the top.

Lemma: the net $Z$. If generic $G\subset Z\in\mathrm{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\in\mathrm{M}$ will contain all $q$ for which a condition that ensures
> $\phi$ is possibly satisfied. The lemma asserts a $p\in G$ for which the
> condition is necessarily possible, and consequently a $p$ that forces the
> condition. Figure 5 displays the lemma.

Figure 5: The net $Z\in\mathrm{M}$ that envelopes $G$. If $G$ (green elements
is a subset of $Z\in\mathrm{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.

Proof. Since $Z\in M$, $\bar{Z}:=\mathbb{P}\setminus Z\in\mathrm{M}$. Let $D$
be the set of all elements $p\in\mathbb{P}$ that are either $\geq$ 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\geq q)\lor(\forall
q\in\bar{Z}\>p\perp q)\\}$. $D\in\mathrm{M}$ by ComprehensionM 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$. $\square$

####  4.5.3 Proof of FTF for equality

Following the structure of the FTF proof laid above, let’s define
$\mathcal{F}_{\alpha}^{x=y}$. This is the hardest case. Equality of $\tau_{1}$
and $\tau_{2}$ in $\mathrm{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 $\mathrm{M}$ where
$\mathrm{nr}(\tau_{1}),\mathrm{nr}(\tau_{2})\leq\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\geq p$ and $(\sigma,q)\in\tau_{1}$, there must be $r\geq 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\geq 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 $\mathrm{M}[G]$”, this is too
strong a condition. Perhaps $(\sigma,r)$ is not in $\tau_{2}$ for any $r\geq
q$, but instead $(\sigma^{\prime},r)\in\tau_{2}$ and simultaneously $r$ forces
$\sigma=\sigma^{\prime}$.

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 $\leq\alpha$ is:

  * •

For every $(\sigma,q)\in\tau_{1}$ with $q\geq p$ there exists
$(\sigma^{\prime},r)\in\tau_{2}$ with $r\geq q$ and
$(r,\sigma,\sigma^{\prime})\in\mathcal{F}_{\max\\{\mathrm{nr}(\sigma),\mathrm{nr}(\sigma^{\prime})\\}}^{x=y}$.

  * •

Conversely, for every $(\sigma,q)\in\tau_{2}$ with $q\geq p$ there exists
$(\sigma^{\prime},r)\in\tau_{1}$ with $r\geq q$ and
$(r,\sigma,\sigma^{\prime})\in\mathcal{F}_{\max\\{\mathrm{nr}(\sigma),\mathrm{nr}(\sigma^{\prime})\\}}^{x=y}$.

A ZFC formula for forcing equality. Similar to the definitions of formula
$V(a,x)$ above, a single formula $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 $\mathrm{M}$. Treating $\mathrm{M}$ for a moment as a
model and not as mere syntax, $\mathrm{M}$ “knows” whether a given $p$ forces
$\tau_{1}^{G}=\tau_{2}^{G}$ in $\mathrm{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^{\prime}$ of
$\tau_{2}$ (i.e., $\exists r\geq
q\>(\sigma^{\prime},r)\in\tau_{2}\land(r,\sigma,\sigma^{\prime})\in\mathcal{F}_{\beta}^{x=y}$
for some $\beta<\alpha$), and vise versa. To bring this important point
forward, I include an “implementation” of
$\mathrm{Force}^{=}(\alpha,p,\tau_{1},\tau_{2})$ here:575757A few obvious
abbreviations are used: $\forall(\sigma,q)\in\tau_{2}\ldots$ is not proper
syntax, and it stands for $\forall
x(x\in\tau_{2}\rightarrow\exists\sigma\>\exists q\>x=(\sigma,q)\land...)$.

$\mathrm{Force}^{=}(\alpha,p,\tau_{1},\tau_{2}):=\mathrm{Ord}(\alpha)\land
p\in\mathbb{P}\land N(\alpha,\tau_{1})\land
N(\alpha,\tau_{2})\land\exists\mathcal{F}_{aux}\in\mathrm{M}\>\mathrm{Fun}(\mathcal{F}_{aux})\land\mathrm{Dom}(\mathcal{F}_{aux},\alpha+1)\land$
$\forall\beta\in\alpha+1\>(\forall
p^{\prime}\>\forall\tau_{1}^{\prime}\>\forall\tau_{2}^{\prime}\>(p^{\prime}\in\mathbb{P}\land
N(\beta,\tau_{1}^{\prime})\land
N(\beta,\tau_{2}^{\prime}))\rightarrow((q,\tau_{1}^{\prime},\tau_{2}^{\prime})\in\mathcal{F}_{aux}[\beta]\leftrightarrow$
$(\forall(\sigma,q)\in\tau_{1}^{\prime}\>(q\geq
p^{\prime}\rightarrow\exists\sigma^{\prime}\>\exists
r\>(\sigma^{\prime},r)\in\tau_{2}^{\prime}\land r\geq
q\land\exists\delta\in\beta\>(r,\sigma,\sigma^{\prime})\in\mathcal{F}_{aux}[\delta])\land$
$(\forall(\sigma,q)\in\tau_{2}^{\prime}\>(q\geq
p^{\prime}\rightarrow\exists\sigma^{\prime}\>\exists
r\>(\sigma^{\prime},r)\in\tau_{1}^{\prime}\land r\geq
q\land\exists\delta\in\beta\>(r,\sigma,\sigma^{\prime})\in\mathcal{F}_{aux}[\delta]))\land$
$(p,\tau_{1},\tau_{2})\in\mathcal{F}_{aux}[\alpha]$

In this formula, $\mathbb{P}$ is assumed to be the poset in $\mathrm{M}$ with
respect to which $N()$ is the name space within $\mathrm{M}$. Assuming
$\alpha\leq\alpha_{\mathrm{M}}$ and $p,\tau_{1},\tau_{2}\in\mathrm{M}$, as
mentioned above the entire formula is relativized to
$\mathrm{M}$.585858Syntactically it is not, but replacing syntax such as
$\forall\beta\in\alpha+1...$ with
$\forall\beta\in\mathrm{M}\>\beta\in\alpha+1\rightarrow...$ makes no
difference as $\beta\in\alpha+1$ implies $\beta\in\mathrm{M}$ and similarly
for all the other quantifiers.

> How Force= works. This formula resembles computer code. For any $\alpha$, it
> defines the set $\mathcal{F}_{\alpha}^{x=y}\in\mathrm{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 $\mathcal{F}_{aux}$ whose job is to store all intermediate sets
> $\mathcal{F}_{aux}[\beta]:=\mathcal{F}_{\beta}^{x=y}$. Each of these sets
> uses the information in previous sets (i.e., $\mathcal{F}_{\delta}^{x=y}$
> for $\delta<\beta$) to define equality for name ranks up to $\beta$. At each
> level $\beta$, for any $\tau_{1}^{\prime},\tau_{2}^{\prime}\in N_{\beta}$,
> $p^{\prime}$ forces them equal if among the extensions of $p^{\prime}$ each
> member of $\tau_{1}^{\prime}$ is necessarily possibly a member of
> $\tau_{2}^{\prime}$ and conversely. Here, “member of $\tau_{1}^{\prime}$”
> 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^{\prime}$ and
> $(\sigma^{\prime},r)\in\tau_{2}$. Having filled the entire array
> $\mathcal{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}^{\prime}$ of the other are resolved in a finite chain of
> “necessarily possibly": $\sigma_{1}=\sigma_{1}^{\prime}$ will be resolved by
> requiring in turn for all members $\sigma_{2}$ of one to be necessarily
> possibly equal to some $\sigma_{2}^{\prime}$ 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
> $\mathbb{P}$ rather than some kind of infinite limit.

Now, using ComprehensionM each $\mathcal{F}_{\alpha}^{x=y}$ can be defined as
set of the triplets $(p,\tau_{1},\tau_{2})\in\mathbb{P}\times N_{\alpha}\times
N_{\alpha}\in\mathrm{M}$ that satisfy $Force^{=}(\alpha,p,\tau_{1},\tau_{2})$.

$\mathcal{F}_{\alpha}^{x=y}:=\\{x\in\mathbb{P}\times N_{\alpha}\times
N_{\alpha}\>|\>\exists
p\exists\tau_{1}\exists\tau_{2}\>x=(p,\tau_{1},\tau_{2})\land
Force^{=}(\alpha,p,\tau_{1},\tau_{2})\\}\in\mathrm{M}$

Therefore, each $\mathcal{F}_{\alpha}^{x=y}$ is a set in $\mathrm{M}$.

Once $\mathcal{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 $\mathrm{M}[G]$ are equal iff some $p\Vdash\tau_{1}=\tau_{2}$ iff
$(p,\tau_{1},\tau_{2})\in\mathcal{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\mathbb{P}\>|\>$ 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\mathrm{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.

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\geq 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\geq 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\geq p$. Therefore every
extension $q^{\prime}\geq q$ is in $Z^{=}$ and has
$(\sigma_{1},q^{\prime})\in\tau_{1}$, therefore there is $r\geq q^{\prime}$
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\mathrm{M}$ (because
$\mathcal{F}_{max\\{\mathrm{nr}(\sigma_{1}),\mathrm{nr}(\sigma_{2})\\}}^{x=y}\in\mathrm{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},\ldots,\tau_{k})\in\mathcal{F}^{x=y}_{\alpha}$; (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\mathcal{F}_{\alpha}^{=}$. The conditions of
membership $\mathcal{F}_{\alpha}^{=}$ say that every extension $q\geq p$ must
belong to $Z^{=}$ and conversely with $\tau_{1}$ and $\tau_{2}$ flipped. For
any $q\geq 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\mathcal{F}_{\alpha}^{=}$. Conversely, let
$(p,\tau_{1},\tau_{2})\in\mathcal{F}_{\alpha}^{=}$ and let $G$ be a generic
ideal that contains $p$. By definition of $\mathcal{F}_{\alpha}^{=}$ every
extension $q\geq 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\mathrm{M}$ therefore by the above lemma we can
find $p\in G$ such that all $q\geq 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
$\mathcal{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.

$\mathcal{F}^{x\in y}_{\alpha}$ contains the triplets $(p,\tau_{1},\tau_{2})$
such that for every $q\geq p$ there is an $r\geq 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
$\mathrm{nr}(\tau_{1})<\alpha$ otherwise $(p,\tau_{1},\tau_{2})$ is never in
$\mathcal{F}_{\alpha}^{x\in y}$.) The formula $Force^{\in}$ uses a transfinite
induction with $Force^{=}$ as a subroutine, and details are omitted.
Alternatively, a combined formula
$Force^{=\>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, $\mathcal{F}_{aux}^{=},\mathcal{F}_{aux}^{\in}$ 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.

$\mathcal{F}^{\lnot\psi}_{\alpha}$ contains the tuples
$(p,\tau_{1},\ldots,\tau_{k})$ such that no $q\geq p$ forces
$\psi(\tau_{1},\ldots,\tau_{k})$: no $q\geq p$ exists with
$(q,\tau_{1},\ldots,\tau_{k})$ a member of $\mathcal{F}_{\alpha}^{\psi}$, a
set assumed to be already defined by structural induction on $\phi$.

$\mathcal{F}^{\psi\rightarrow\chi}_{\alpha}$ contains the tuples
$(p,\tau_{1},\ldots,\tau_{k})$ such that it is necessarily possible that
$\psi(\tau_{1},\ldots,\tau_{k})$ implies $\chi(\tau_{1},\ldots,\tau_{k})$,
i.e., such that for every $q\geq p$ that forces $\psi$ there is $r\geq q$ that
forces $\chi$: for every
$(q,\tau_{1},\ldots,\tau_{k})\in\mathcal{F}^{\psi}_{\alpha}$ with $q\geq p$
there is $(r,\tau_{1},\ldots,\tau_{k})\in\mathcal{F}^{\chi}_{\alpha}$ with
$r\geq 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},\ldots,\tau_{k})$ such that
$\forall\tau\in\mathrm{M}^{\mathbb{P}}$, it is necessarily possible that
$\psi(\tau,\tau_{1},\ldots,\tau_{k})$ is forced: $\forall\tau\>\forall\beta$
such that $N(\beta,\tau)$ and $\forall q\geq p$ there exists $r\geq q$ that
forces $\psi(\tau,\tau_{1},\ldots,\tau_{k})$, i.e.,
$(r,\tau,\tau_{1},\ldots,\tau_{k})\in\mathcal{F}^{\psi}_{\max(\alpha,\beta)}$.
Here notice that $N(\beta,\tau)$ states that $\tau\in N_{\beta}$ is a
$\mathbb{P}$-name of rank $\leq\beta$. The reader may ask: “wait, is there no
constraint on $\beta$, and can it be $>\alpha$?” Yes: by structural inductive
assumption, $\mathcal{F}^{\psi}_{\max(\alpha,\beta)}$ is defined and is a set
in $\mathrm{M}$. Then, by ComprehensionM we can form the set of all
$(p,\tau_{1},\ldots,\tau_{k})\in\mathbb{P}\times N_{\alpha}^{k}\in\mathrm{M}$
such that $\forall\tau\>\forall\beta\>(N(\beta,\tau)\rightarrow\forall q\geq
p\>\exists r\geq
q\>(r,\tau,\tau_{1},\ldots,\tau_{k})\in\mathcal{F}_{\max(\alpha,\beta)}^{\psi})$.

> The forcing chain that decides a sentence in $\mathrm{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^{\mathrm{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\rightarrow\forall
> x\>\lnot(x\in y)$. At the bottom we have $\mathrm{Force}^{x\in
> y}(\alpha,p,x,y)$ and $\mathrm{Force}^{y=0}(\alpha,p,y,\check{0})$ defined
> for all $\alpha$ and $p$ as above. Then, $\mathrm{Force}^{\lnot(x\in
> y)}(\alpha,p,x,y):=\forall q\geq p\>\lnot\mathrm{Force}^{x\in
> y}(\alpha,q,x,y)$. Continuing up, $\mathrm{Force}^{\forall x\lnot(x\in
> y)}(\alpha,p,y):=$ $\forall x\>\forall\beta\>(N(\beta,x)\rightarrow\forall
> q\geq p\>\exists r\geq q$ $\mathrm{Force}^{\lnot(x\in
> y)}(\max(\alpha,\beta),r,x,y))$.595959Note 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 $\mathrm{Ord}(\beta)$.
> Finally, $\mathrm{Force}^{\phi}(\alpha,p,y):=$ $\forall q\geq
> p\>(\mathrm{Force}^{y=0}(\alpha,q,y,\check{0})\rightarrow\exists r\geq
> q\>\mathrm{Force}^{\forall x\>\lnot(x\in y)}(\max(\alpha,\beta),r,y))$.
> Unrolling this, we get:
>
> $\mathrm{Force}^{\phi}(\alpha,p,y):=\forall q\geq
> p\>(\mathrm{Force}^{y=0}(\alpha,q,y,\check{0})\rightarrow$ $\exists r\geq
> q\>\forall x\>\forall\beta\>(N(\beta,x)\rightarrow\forall s\geq r\>\exists
> t\geq s\>\forall u\geq t\>\lnot\mathrm{Force}^{x\in
> y}(\max(\alpha,\beta),u,x,y))$

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^{\in}$. Let
$Z^{\in}:=\\{q\in\mathbb{P}\>|\>$ there exists $(\sigma,r)\in\tau_{2}$ with
$r\geq q$ and $r\Vdash\tau_{1}=\sigma\\}$. By assuming FTF.Definability for
equality it follows that $Z^{\in}\in\mathrm{M}$.

$Z^{\in}$ is the set of all $q$ from whose “perspective” it is possible that
$\tau_{1}\in\tau_{2}$. On the other hand, $\mathcal{F}^{x\in y}_{\alpha}$
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}^{x\in y}_{\alpha}$
all extensions $q\geq p$ are caught in the net $Z^{\in}$.

Next task is to show that given $\tau_{1}^{G}\in\tau_{2}^{G}$ we have
$G\subset Z^{\in}$ therefore there is a $p$ all of whose extensions are in
$Z^{\in}$ 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}\>|\>(\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\geq 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^{\in}$. Since $p$ was arbitrary, $G\subset Z^{\in}$.
Therefore, there is some $p\in G$ such that every extension $q\geq p$ is in
$Z^{\in}$.

Let $p\in G$ such that every extension $q\geq p$ is in $Z^{\in}$. 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}=\check{\emptyset}$, by assuming FTF.Truth
for $=$. Then take $q^{\prime}\geq q,p$. Because $q^{\prime}\in Z^{\in}$,
there is an extension $r\geq q^{\prime}$ 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 $\mathrm{M}$ by FTF.Definability for $=$.
Therefore some $r^{\prime}\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^{\prime}\geq q,p$, and again there is $r\geq q^{\prime}$ with
$r\Vdash\tau_{1}=\sigma^{\prime}$ for some $(\sigma^{\prime},r)\in\tau_{2}$.
Therefore the set of $r$ with that property is dense above $q$, it is in
$\mathrm{M}$ by FTF.Definability for $=$, and therefore some $r^{\prime}\in G$
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}^{\in}$ iff
$p\Vdash\tau_{1}\in\tau_{2}$. If
$(p,\tau_{1},\tau_{2})\in\mathcal{F}_{\alpha}^{\in}$, then every extension
$q\geq p$ belongs to $Z^{\in}$ 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\geq p$. We must show that $q$ satisfies the condition “there is $r\geq q$
and $(\sigma,r)\in\tau_{2}$ such that
$(r,\tau_{1},\sigma)\in\mathcal{F}_{\max(\mathrm{nr}(\tau_{1}),\mathrm{nr}(\sigma))}^{x=y}$”.
Let $G$ be a generic ideal containing $q$, therefore $p\in G$ so
$\tau_{1}^{G}\in\tau_{2}^{G}$. Therefore $q\in Z^{\in}$ as we just showed, so
there is such an $r\geq 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}^{\in}$. $\square$

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

  * •

$Z^{\lnot}:=\\{q\in\mathbb{P}\>|\>q\not\Vdash\psi(\tau_{1},\ldots,\tau_{k})\\}$
where $\phi:=\lnot\psi$.

  * •

$Z^{\rightarrow}:=\\{q\in\mathbb{P}\>|\>$ either
$q\not\Vdash\psi(\tau_{1},\ldots,\tau_{k})$ or $\exists r\geq q$ such that
$r\Vdash\chi(\tau_{1},\ldots,\tau_{k})\\}$, where $\phi:=\psi\rightarrow\chi$.

  * •

$Z^{\forall}:=\\{q\in\mathbb{P}\>|\>$ for every $\mathbb{P}$-name $\tau$ there
is $r\geq q$ such that $r\Vdash\psi(\tau,\tau_{1},\ldots,\tau_{k})\\}$, where
$\phi:=\forall x\>\psi$.

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

####  4.5.5 Proof that $\mathrm{M}[G]$ is a model of ZFC

Next comes a case analysis where every axiom of ZFC is proven for
$\mathrm{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
$\mathrm{M}[G]$ is. $\square$

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

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

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

Starting with $\tau$, let $\pi=\\{(\sigma,p)\>|\>\sigma\subseteq\tau$ is a
$\mathrm{P}$-name and $p\in\mathbb{P}\\}$.606060More precisely,
$\pi:=\\{\sigma\in\mathcal{P}(\tau)^{\mathrm{M}}\\}\times\mathbb{P}\in\mathrm{M}$.
It easily follows that $\pi$ is a $\mathbb{P}$-name. Intuitively, $\pi$
contains as many subsets of $\tau$ as possible so it better work.

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

To show $\sigma^{\prime G}=\sigma^{G}$. Let $\rho^{G}\in\sigma^{\prime G}$,
then there is $p\in G$ such that $(\rho,p)\in\sigma^{\prime}$ and
$p\Vdash\rho\in\sigma$ so $\rho^{G}\in\sigma^{G}$. So
$\sigma^{\prime}\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^{\prime}$
$(\rho,p)\in\sigma^{\prime}$ which implies $\rho^{G}\in\sigma^{\prime G}$.
$\square$

Infinity. It follows from $\omega\in\mathrm{M}\subset\mathrm{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 $\mathrm{M}[G]$ and any set
$\tau^{G}\in\mathrm{M}[G]$, the set
$z:=\\{\sigma^{G}\in\tau^{G}\>|\>\phi(\sigma^{G})\\}$must be shown to belong
to $\mathrm{M}[G]$.616161The formula $\phi$ can have additional variables,
$\phi(x,x_{1},\ldots,x_{k})$ and for any $\tau_{1}^{G},\ldots,\tau_{k}^{G}$,
the set
$\\{\sigma^{G}\in\tau^{G}\>|\>\phi(\sigma^{G},\sigma_{1}^{G},\ldots,\sigma_{k}^{G})\\}$
should be in $\mathrm{M}[G]$. To avoid the clutter, the extra variables are
suppressed. It suffices to devise a $\mathbb{P}$-name $\upsilon$ evaluating to
$z$. With forcing in place, the obvious $\mathbb{P}$-name works:

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

Importantly, $\upsilon$ is a $\mathrm{P}$-name due to FTF:Definability,
specifically
$\\{(p,\sigma)\in\mathcal{F}_{\mathrm{nr}(\tau)}^{\phi}\>|\>(\sigma,p)\in\tau\\}$
is a set in $\mathrm{M}$ due to ComprehensionM since we already know that
$\mathcal{F}_{\mathrm{nr}(\tau)}^{\phi}$ is a set by Definability and that
$\mathrm{nr}(\sigma)<\mathrm{nr}(\tau)$.626262More explicitly,
$\\{x\in\mathrm{P}\times\mathrm{M}^{\mathrm{P}}\>|\>\exists\alpha\>\exists
p\>\exists\sigma\>\alpha=\mathrm{nr}(\tau)\land
x=(p,\sigma)\land(\sigma,p)\in\tau\land\mathrm{Force}^{\phi}(\alpha,p,\sigma)\\}$.

To show $\upsilon^{G}=z$ we show $\upsilon^{G}\subseteq z$ and
$z\subseteq\upsilon^{G}$. Let $\sigma^{G}\in\upsilon^{G}$, therefore
$(\sigma,p)\in\tau$ and $p\Vdash\phi(\sigma)$, therefore $\phi(\sigma^{G})$,
which implies that $\sigma^{G}\in z$.

Conversely, let $\sigma^{G}\in z$ therefore $\sigma^{G}\in\tau^{G}$ and
$\phi(\sigma^{G})$. Then, $(\sigma,p)\in\tau$ for some $p\in G$. Moreover, by
FTF:Truth there is some $q$ that forces $\phi(\sigma^{G})$. Let $r\in G$ be a
common extension of $p,q$. Then $(\sigma,r)\in\tau$ and by FTF:Coherence
$\tau\Vdash\phi(\sigma^{G})$ so by definition of $\upsilon$,
$(\sigma,r)\in\upsilon$ and therefore $\sigma^{G}\in\upsilon^{G}$. $\square$

Replacement Schema. Given any formula $\phi(x,y,z)$ relativized to
${\mathrm{M}[G]}$ and set $\pi^{G}\in\mathrm{M}[G]$ (the domain) such that for
any $\sigma^{G}\in\pi^{G}$ there is a unique $\tau^{G}$ such that
$\phi(\sigma^{G},\tau^{G},\pi^{G})$, we need to show that there is a set
$\rho^{G}\in\mathrm{M}[G]$ (the image of the domain under the class function
$\phi$) that contains all elements $\tau^{G}$ that are making
$\phi(\sigma^{G},\tau^{G},\pi^{G})$ true for some $\sigma^{G}\in\pi^{G}$.

Fix $\mathbb{P}$-name $\pi$ in $\mathrm{M}$. For every $(\sigma,p)\in\pi$, let
$\alpha_{\sigma,p}$ be the least ordinal in $\mathrm{M}$ such that there
exists $\tau$ with
$(p,\sigma,\tau,\pi)\in\mathcal{F}_{\alpha_{\sigma,p}}^{\phi}$, i.e., with
$p\Vdash\phi(\sigma,\tau,\pi)$, if any such $p$ exists, and let
$\alpha_{\sigma,p}=\emptyset$ if not. By Replacement in $\mathrm{M}$, the set
of these ordinals is in $\mathrm{M}$. To see this, consider the formula
$Ord(\alpha)\land(\exists
p\>\exists\tau\>(p,\sigma,\tau,\pi)\in\mathcal{F}_{\alpha}^{\phi}\lor\alpha=\emptyset)\land\forall\beta\in\alpha\>\lnot(\exists
p\>\exists\tau\>(p,\sigma,\tau,\pi)\in\mathcal{F}_{\beta}^{\phi})$. For any
set $\pi$ and any $(\sigma,p)\in\pi$ there is a unique $\alpha$ that makes
this formula true, therefore by Replacement we can collect into a set all
ordinals $\alpha$ that make the formula true for elements of $\pi$’s domain.

Therefore, the supremum of $\alpha_{\sigma,p}$ for any $(\sigma,p)$, call it
$\alpha^{*}$ is also in $\mathrm{M}$.

Now define $V_{\alpha}:=\\{\sigma^{G}\>|\>\sigma\in
N_{\alpha}\\}\in\mathrm{M}[G]$ for any $\alpha\in\mathrm{M}$. If we can show
that any $\tau^{G}$ such that $\phi(\sigma^{G},\tau^{G},\pi^{G})$ for
$\sigma^{G}\in\pi^{G}$ has to be in $V_{\alpha^{*}}$, then we can define the
set of all of such $\tau^{G}$ using ComprehensionM[G], which we just proved.
That is to say, we can define $\\{y\in V_{\alpha^{*}}\>|\>\exists
x\in\pi^{G}\>\phi(x,y,\pi^{G})\\}\in\mathrm{M}[G]$ by ComprehensionM[G].
Therefore, all we need to show is that $\mathrm{nr}(\tau)\leq\alpha^{*}$ for
any $\tau$ such that $\phi(\sigma^{G},\tau^{G},\pi^{G})$.

Let $\sigma^{G}\in\pi^{G}$ be arbitrary. We know $(\sigma,p)\in\pi$ for some
$p\in G$. Also, there is some $\tau^{G}$ making $\phi$ true and by FTF.Truth
there is some $q\in G$ that forces $\phi(\sigma,\tau,\pi)$. Taking $r\geq p,q$
as a common extension, we know $(\sigma,r)\in\pi$ as well as
$r\Vdash\phi(\sigma,\tau,\pi)$. Because $\alpha^{*}$ is the supremum of the
least ordinals $\alpha_{\sigma,p}$ where $p$ forces
$\phi(\sigma,\tau^{\prime},\pi)$, there must be some $\tau^{\prime}$ such that
$\mathrm{nr}(\tau^{\prime})\leq\alpha^{*}$ as well as
$r\Vdash\phi(\sigma,\tau^{\prime},\pi)$. However, $\phi$ maps unique $\sigma$
to unique $\tau$, therefore $\tau=\tau^{\prime}$ and consequently
$\mathrm{nr}(\tau)\leq\alpha^{*}$. $\square$

Axiom of Choice. (Sketch.) AC is equivalent to the well-ordering principle.
Let $\tau^{G}\in\mathrm{M}[G]$. We need to show that $\tau^{G}$ can be well
ordered. Starting with $\tau\subset N_{\alpha}\times\mathbb{P}$ for
$\alpha=\mathrm{nr}(\tau)$, we can well order $\tau$ using AC in $\mathrm{M}$:
$\tau=\\{(\sigma_{\beta},p_{\beta})\>|\>0\leq\beta<\gamma\\}$, whereby the
function $f:\tau\to\gamma$ mapping $(\sigma_{\beta},p_{\beta})$ to $\beta$ is
in $\mathrm{M}$. We can lift it up to $\mathrm{M}[G]$ with its canonical
$\mathbb{P}$-name $\check{f}$ and it will easily do the job of well ordering
$\tau^{G}$. Details are left to the reader. $\square$

Therefore, given any axiom $\phi$ of ZFC and any separative poset $\mathbb{P}$
defined in $\mathrm{M}$, it is a ZFC+ theorem that a generic $G$ over
$\mathbb{P}$ exists and $\mathrm{M}[G]$ is a set containing all elements of
$\mathrm{M}$ as well as $G$ and moreover $\phi^{\mathrm{M}[G]}$. Given any
finite list of axioms $\phi_{1},\ldots,\phi_{k}$,
$(\phi_{1}\land\ldots\land\phi_{k})^{\mathrm{M}[G]}$ can be derived in ZFC+.
Those axioms can then be used as explained in the next section to prove in
ZFC+ that $(\lnot\mathrm{CH})^{\mathrm{M}[G]}$. Then, proof of $\mathrm{CH}$
in ZFC would lead to contradiction by relativizing the proof within
$\mathrm{M}[G]$ (adding more axioms to the $\phi_{i}$’s as needed). We just
finished outlining the proof of the following theorem, which is a numerical
statement about syntactic properties of ZFC+ and can be formalized in Peano
Arithmetic:

Metatheorem. If $\mathbb{P}$ is a separative poset in $\mathrm{M}$ and $\phi$
is any theorem of ZFC, then there is a ZFC+ proof of "$(G$ is a generic ideal
over $\mathbb{P})$ and $($the set of $\mathbb{P}$-names
$\mathrm{M}^{\mathbb{P}}\in\mathrm{M})$ and $($the set $\mathrm{M}[G]$ of
$G$-evaluations of elements of $\mathrm{M}^{\mathbb{P}}$ is countable and
transitive$)$ and $\mathrm{M}\subsetneq\mathrm{M}[G]$ and $G\in\mathrm{M}[G]$
and $\phi^{\mathrm{M}[G]}$".

###  4.6 Forcing $\lnot\mathrm{CH}$ to hold in $\mathrm{M}[G]$

To recap, $\mathrm{M}[G]$ contains $G$ together with
$\aleph_{2}^{\mathrm{M}}$-many new subsets of $\aleph_{0}$ and simultaneously
the proof of $CH^{\mathrm{M}[G]}$ goes through. Are we done?

Not yet: we know that $\bigcup
G:\aleph_{2}^{\mathrm{M}}\times\aleph_{0}\to\\{0,1\\}$ is in $\mathrm{M}[G]$
and consequently
$|(2^{\aleph_{0}})^{\mathrm{M}[G]}|\geq\aleph_{2}^{\mathrm{M}}$, but we
haven’t shown that $\aleph_{2}^{\mathrm{M}[G]}=\aleph_{2}^{\mathrm{M}}$.
Perhaps among its many new sets $\mathrm{M}[G]$ also contains a function
$\aleph_{1}^{\mathrm{M}[G]}\to\aleph_{2}^{\mathrm{M}}$. Then, no contradiction
with $CH^{\mathrm{M}[G]}$ is shown.

Cardinal collapse. We need to show that introducing $G$ through forcing does
not create new functions from a smaller infinite cardinal to a larger infinite
cardinal. Such a function would collapse the larger cardinal to be equal to
the smaller one. Here is a simple way to achieve that through forcing. At the
ground countable model $\mathrm{M}$ define the forcing notion
$\mathbb{P}^{\prime}$ to consist of all finite partial bijections between
$\aleph_{\alpha}^{\mathrm{M}}$ and $\aleph_{\beta}^{\mathrm{M}}$ with
$\beta>\alpha$. Then $\mathrm{M}[G]$ will contain $\bigcup G$, which is a
complete bijection between $\aleph_{\alpha}^{\mathrm{M}}$ and
$\aleph_{\beta}^{\mathrm{M}}$. Recall that both of these are countable
ordinals. $\bigcup G$ would be a complete bijection because the set
$D_{\gamma}:=\\{p\in\mathbb{P}^{\prime}\>|\>\gamma$ is in the range of $p\\}$
is a dense subset of $\mathbb{P}^{\prime}$ for all
$\gamma\in\aleph_{\beta}^{\mathrm{M}}$ and $D_{\gamma}\in\mathrm{M}$,
therefore $G$ has to intersect it, i.e., $\bigcup G$ has to include $\gamma$
in its range. Similarly for its domain. Therefore
$\aleph_{\beta}^{\mathrm{M}}$ is of the same cardinality as
$\aleph_{\alpha}^{\mathrm{M}}$ in $\mathrm{M}[G]$. One may ask now, what about
$\aleph_{\beta}^{\mathrm{M}[G]}$? Well, this is some countable ordinal larger
than $\aleph_{\beta}^{\mathrm{M}}$ that $\mathrm{M}[G]$ “thinks” is the
$\beta$th infinite cardinal. Could new cardinals be introduced in
$\mathrm{M}[G]$? No: if a bijection already exists in $\mathrm{M}$ between two
ordinals, the same function still exists in $\mathrm{M}[G]$. New cardinals can
never appear, but cardinals of the ground model $\mathrm{M}$ can collapse.
Therefore, to conclude the proof we need to show that forcing with
$\mathbb{P}$ does not collapse cardinals.

The main idea is to examine the new functions $f^{G}\in\mathrm{M}[G]$ created
from the “perspective” of $\mathrm{M}$ and observe that their range cannot be
“too big” because each $\mathbb{P}$-name $\sigma$ of the domain has at most
countablyM many potential $\mathbb{P}$-name partners $\tau$ in the range. A
potential partner $\tau$ in the range is one for which there is any $q_{\tau}$
forcing $f(\sigma)=\tau$. If each $\sigma$ in the domain has at most
countablyM many potential partners in the range, then the range is at most
$\aleph_{0}$ times the domain in size from the perspective of $\mathrm{M}$,
and for infinite domain that implies same cardinality from the perspective of
$\mathrm{M}$.

More specifically, any function $f^{G}\in\mathrm{M}[G]$ between cardinals
$\kappa^{\mathrm{M}}<\lambda^{\mathrm{M}}$ has an associated $\mathbb{P}$-name
$f$ and some $p\in G$ that forces “$f$ is a function
$\kappa^{\mathrm{M}}\to\lambda^{\mathrm{M}}$”. Then, for every
$(\sigma^{G},\tau^{G})\in f^{G}$ (i.e., $f(\sigma^{G})=\tau^{G}$) there has to
be some $q\in G,q\geq p$ that forces $(\sigma,\tau)\in f$. Fixing $p$ and
$\sigma$, the potential distinct partners $\tau$ of $\sigma$ correspond to
distinct $q_{\tau}\geq p$ that are pairwise incompatible. The key property to
prove now is that there are at most countablyM many pairwise incompatible
elements in $\mathbb{P}$. If so, then there are at most countablyM many
potential partners $\tau$ for each $\sigma$.

> Definition. An antichain over a poset $\mathbb{P}$ is a set of pairwise
> incompatible elements. $\mathbb{P}$ satisfies the countable chain condition
> (ccc) if there is no uncountable antichain over $\mathbb{P}$.

Because $\mathrm{M}$ is countable, $\mathbb{P}$ is trivially ccc. The key will
be to prove $(\mathbb{P}$ is ccc$)^{\mathrm{M}}$. Once this is done, the
following lemma establishes that cardinals in $\mathrm{M}$ remain cardinals in
$\mathrm{M}[G]$. The idea is simple: given a function $f^{G}$, any assignment
$f^{G}(\sigma^{G})=\tau^{G}$ is forced by some $q\in G$. If ($\mathbb{P}$ is
ccc)M, then $\mathrm{M}$ “knows” that for any given $\sigma$, there are at
most countably many distinct $\tau$ forced by distinct and pairwise
incompatible $q_{\tau}\Vdash f(\sigma)=\tau$. Therefore, the cardinality of
the range of $f$ is forced to be at most that of the domain of $f$ times
$\aleph_{0}$, therefore $f$ cannot map an infinite cardinal to a larger
infinite cardinal. All of these statements are relativized to $\mathrm{M}$.

> Lemma. Let $\mathbb{P}$ be a poset in $\mathrm{M}$ such that ($\mathbb{P}$
> is ccc$)^{\mathrm{M}}$, $G$ a generic ideal, and $f^{G}:\eta\to\theta$ be a
> function in $\mathrm{M}[G]$ between ordinals $\eta<\theta$. Then:
>
>   1. 1.
>
> There exists a function $g\in\mathrm{M}$ from $\eta$ to $2^{\theta}$ such
> that $\forall\alpha<\eta\>f^{G}(\alpha)\in g(\alpha)$, and moreover
> $(g(\alpha)$ is countable$)^{\mathrm{M}}$.
>
>   2. 2.
>
> Infinite ordinals that are cardinals in $\mathrm{M}$ remain cardinals in
> $\mathrm{M}[G]$.
>
>

Proof. (1) Let $f$ be the $\mathbb{P}$-name for $f^{G}$ and $p\in G$ force
“$f:\check{\eta}\to\check{\theta}$ is a function”. For each $\alpha\in\eta$
let $g(\alpha)=\\{\beta\in\theta\>|\>\exists q\geq p$ such that $q\Vdash
f(\check{\alpha})=\check{\beta}\\}$. This is a set in $\mathrm{M}$ by
Comprehension and FTF.Definability. Moreover, $f^{G}(\alpha)\in g(\alpha)$.
Finally, if for each $\beta$ we pick one element $q_{\beta}$ that forces
$f(\check{\alpha})=\check{\beta}$, then $\\{q_{\beta}\>|\>\beta\in
g(\alpha)\\}$ is a set of pairwise incompatible elements and therefore at most
countableM by ($\mathbb{P}$ is ccc$)^{\mathrm{M}}$, and is in bijection with
$g(\alpha)$ by $\beta\to q_{\beta}$. Finally, because the latter function is
in $\mathrm{M}$, we have $(g(\alpha)$ is countable$)^{\mathrm{M}}$.

(2) Let $\theta$ be an infinite ordinal in $\mathrm{M}$ such that $(\theta$ is
not a cardinal$)^{\mathrm{M}[G]}$. Then let $\eta<\theta$ be an infinite
ordinal and $f^{G}:\eta\to\theta$ a surjection in $\mathrm{M}[G]$. Let
$g:\eta\to 2^{\theta}$ be a function in $\mathrm{M}$ as in part (1). Notice
that $\theta=\bigcup_{\alpha\in\eta}g(\alpha)$636363Because $f^{G}$ is a
surjection $\eta\to\theta$ and $f^{G}(\alpha)\in g(\alpha)$ for all
$\alpha\in\eta$. and now we get
$(|\theta|=|\bigcup_{\alpha\in\eta}g(\alpha)|\leq|\eta\cdot\aleph_{0}|=|\eta|)^{\mathrm{M}}$.
Therefore $\theta$ is not a cardinal in $\mathrm{M}$ either. In conclusion, a
cardinal in $\mathrm{M}$ remains a cardinal in $\mathrm{M}[G]$. $\square$

The key is now to prove that $(P$ is ccc$)^{\mathrm{M}}$. Equivalently, that
any uncountableM subset of $\mathbb{P}$ contains some pair of compatible
elements $p,q$. Recalling that all $p\in\mathbb{P}$ are finite partial
functions, this will boil down to a basic result in infinite combinatorics ,
the $\Delta$-system lemma.

> $\Delta$-system lemma. Let $X$ be an uncountable family of finite sets. Then
> there is an uncountable $Y\subseteq X$ and a finite set $r$, the root, such
> that every pair of sets in $Y$ intersect in precisely $r$: $\forall x,y\in
> Y\>x\cap y=r$.

Proof sketch. This is a basic result with many excellent expositions of the
proof available online. Briefly, let $X_{n}$ be the sets of size $n$ among
sets in $X$. At least one of these, say $X_{k}$ has to be uncountable
otherwise $X$ would be a countable union of countable sets. Let $m$ be the
maximum size of a set $r$ such that $r\subseteq x$ for uncountably many $x\in
X_{k}$. $\emptyset\subset x$ for every $x\in X_{k}$, therefore $0\leq m\leq
k$. So let $r$ be a set of size $m$ and $Y\subseteq X_{k}$ the uncountable
collection of all $x\supseteq r$. Any element $a$ of any $x\in Y$ is either
$\in r$ or in at most countably many sets in $Y$.

Form a graph whose vertices are the sets $x\in Y$ and edges connect any sets
$x,y$ whose intersection contains elements not in $r$. Any vertex in the graph
has at most a finite number of elements not in $r$, and consequently at most
countably many neighbors. So the graph has uncountably many vertices, each of
which has at most countably many neighbors. We show that there is an
uncountable independent set of vertices, where no two vertices are neighbors.
Such a set can be constructed with transfinite induction. At stage $0$ pick
any vertex $x_{0}$. at stage $\alpha\leq\aleph_{1}$, we have selected a
countable family of vertices $\\{x_{\beta}\>|\>\beta<\alpha\\}$ each of which
has at most countably many neighbors outside this collection, so there are
still uncountably many vertices from which to pick some $x_{\alpha}$ that is
not a neighbor of any $x_{\beta},\beta<\alpha$.

Therefore, pick an uncountable independent subset of $Y$. This is an
uncountable collection in which any $x\cap y=r$. $\square$

This lemma will prove useful in showing that $(P$ is ccc$)^{\mathrm{M}}$.
Given an uncountableM collection of finite partial functions in $\mathbb{P}$,
we will find an uncountableM subcollection whose domains pairwise intersect
precisely in some finite root domain $r$. Then, because each finite domain can
only generate finitely many distinct functions whose range is $\\{0,1\\}$,
there has to be some functions that are identical within $r$ and whose
remaining distinct domains can be patched together. That means they are
compatible, showing that there is no uncountableM incompatible collection of
partial functions in $\mathbb{P}$. More formally:

Lemma. $(P$ is ccc$)^{\mathrm{M}}$.

Proof. Let $S$ be an uncountableM collection of $p\in\mathbb{P}$ and let
$X=\\{\mathrm{Dom}(p)\>|\>p\in S\\}$. Any specific $\mathrm{Dom}(p)$ is a
finite set, which can support at most finitely many distinct functions to
$\\{0,1\\}$. Therefore $X$ is uncountableM. Now prove the $\Delta$-system
lemma relativized to $\mathrm{M}$ and find an uncountableM $Y\subseteq X$ and
a finite root $r$ such that $x\cap y=r$ for every $x,y\in Y$. For every $x\in
Y$ pick some $p_{x}\in S$ such that $x=\mathrm{Dom}(p_{x})$. The domains of
functions $\\{p_{x}\>|\>x\in Y\\}$ all intersect in precisely $r$. For any two
functions to be incompatible, they should differ in how they map $r$ to
$\\{0,1\\}$. Because there are finitely many ways to map $r$ to $\\{0,1\\}$,
there are distinct $p_{x},p_{y}$ such that $p_{x}|_{r}=p_{y}|_{r}$, i.e.,
which are compatible. $\square$

Theorem. $(\lnot\mathrm{CH})^{\mathrm{M}[G]}$ is a ZFC+ theorem.

Proof. In ZFC+, because $(P$ is ccc$)^{\mathrm{M}}$ we get
$\aleph_{2}^{\mathrm{M}[G]}=\aleph_{2}^{\mathrm{M}}$. Also, $(\bigcup
G:\aleph_{2}\times\aleph_{0}\to\\{0,1\\}$ is a function$)^{\mathrm{M}[G]}$.
Because for each $(\alpha,n)\in\aleph_{2}^{\mathrm{M}}\times\aleph_{0}$ the
set of $p\in\mathbb{P}$ containing $(\alpha,n)$ in their domain is a dense set
in $\mathrm{M}$, $G$ must intersect that set and therefore all of
$\aleph_{2}^{\mathrm{M}}\times\aleph_{0}$ is in the domain of $\bigcup G$,
i.e., $(\bigcup G$ is a complete function$)^{\mathrm{M}[G]}$. Moreover, for
any distinct $\alpha,\beta\in\aleph_{2}^{\mathrm{M}}$ the set of all
$p\in\mathbb{P}$ that contain $(\alpha,n),(\beta,n)$ mapping to distinct
values for some $n$ is a dense set in $\mathrm{M}$ and therefore $G$ must
intersect that set. Therefore each “row” of $\bigcup G$ is distinct. By a
similar argument each row of $\bigcup G$ is a subset of $\aleph_{0}$ not in
$\mathrm{M}$. In conclusion, (there are $\aleph_{2}$ distinct subsets of
$\aleph_{0})^{\mathrm{M}[G]}$ is a ZFC+ theorem. $\square$

Therefore, if ZFC is consistent, then so is ZFC + $\lnot\mathrm{CH}$.

####  4.6.1 What values can $2^{\aleph_{0}}$ take?

The above proof shows that
$|(2^{\aleph_{0}})^{\mathrm{M}}|\geq\aleph_{2}^{\mathrm{M}}$ but no exact
value for the cardinality of $2^{\aleph_{0}}$ is given. Forcing
$|2^{\aleph_{0}}|=\aleph_{2}$ is possible but will not be covered here.
However, notice that the value $\aleph_{2}$ plays no role in the proof. Can
the continuum be forced to take other values?

In fact, it can take almost any value! It can be
$\aleph_{3},\aleph_{2022},\aleph_{\aleph_{2}},\aleph_{\aleph_{\aleph_{2022}}},\ldots$.
There is only one restriction that comes from a well known and useful result,
König’s theorem:

> König’s theorem. Let $\kappa_{i},\lambda_{i}$, $i\in I$ be two infinite
> sequences of cardinals with $\kappa_{i}\leq\lambda_{i}$, $\forall i\in I$,
> where $I$ is an index set of any cardinality. Then
> $\Sigma\kappa_{i}<\Pi\lambda_{i}$.

Note the strict inequality in the above theorem, as well as the fact that the
$\kappa_{i}$ and $\lambda_{i}$ can be finite or infinite. Proof of this
theorem requires the Axiom of Choice.

A constraint on the value of the continuum follows. To describe it, the notion
of cofinality needs to be introduced.

> Definition: cofinality. Let $\kappa$ be any ordinal. A sequence of ordinals
> $\langle\lambda_{\xi}<\kappa\>|\>\xi<\beta\rangle$ is cofinal to $\kappa$ if
> for every $\alpha<\kappa$ there is a $\xi<\beta$ such that
> $\lambda_{\xi}>\alpha$. The cofinality of $\kappa$, denoted
> $\mathrm{cf}(\kappa)$, is the least $\beta$ for which such a sequence
> exists.
>
> Examples. The cofinality of the ordinal $2022$ is $1$: the sequence $\langle
> 2021\rangle$ suffices. The cofinality of $\omega$ is $\omega$: no finite
> sequence of finite numbers has $\omega$ as its limit. A cardinal $\kappa$ is
> called regular when it has this precise property of
> $\mathrm{cf}(\kappa)=\kappa$; otherwise it is called singular. The
> cofinality of $\aleph_{\aleph_{0}}$ is $\omega$: the sequence
> $\langle\aleph_{i}\>|\>i<\aleph_{0}\rangle$ is cofinal; therefore
> $\aleph_{\aleph_{0}}$ is singular.

An important corollary of König’s theorem involves the cofinality of an
infinite cardinal:

> Corollary. If $\lambda\geq\aleph_{0}$ then $\lambda<\lambda^{cf(\lambda)}$.
>
> Proof. Let $\langle\kappa_{\xi}<\lambda\>|\>\xi<cf(\lambda)\rangle$ be a
> cofinal sequence to $\lambda$. Use König’s theorem with
> $\lambda_{i}=\lambda$ for $i\in\mathrm{cf}(\lambda)$ to obtain
> $\Sigma_{\xi<cf(\kappa)}\kappa_{\xi}<\lambda^{\mathrm{cf}(\lambda)}$. Then,
> observe that $\Sigma_{\xi<\mathrm{cf}(\kappa)}\kappa_{\xi}=\lambda$ so the
> result follows. $\square$

It follows easily that the cofinality of continuum cannot be $\omega$: notice
that $(2^{\omega})^{\omega}=2^{2\omega}=2^{\omega}$. Assume now that
$\mathrm{cf}(2^{\omega})=\omega$. Let
$\langle\kappa_{i}<2^{\omega}\>|\>i<\omega\rangle$ be cofinal to $2^{\omega}$.
Then $\Sigma\kappa_{i}<(2^{\omega})^{\omega}$ by König’s theorem. However
$\Sigma\kappa_{i}=2^{\omega}$, contradiction.

Therefore, the cardinality of continuum cannot be $\aleph_{\omega}$ or
$\aleph_{\omega^{2}}$ or $\aleph_{\aleph_{\aleph_{\aleph_{\ldots}}}}$ because
all these have cofinality $\omega$. However, it can be bigger or smaller than
any of these values.

##  5 Bullet-point outline of the proof

###  5.1 Part I: logical argument

  1. 1.

Any sentence $\phi$ is equivalent to $\phi^{M}$ where $M$ is a countable
transitive set. In particular, given any finite list of axioms of ZFC
$\phi_{1},\ldots,\phi_{k}$, $\exists
M\>\mathrm{CntTrans}(M)\land\phi_{1}^{M}\land\cdots\land\phi_{k}^{M}$ is a ZFC
theorem. This is established by the Reflection Principle and Mostowski
collapse lemma.

  2. 2.

Therefore, for any theorem $\phi$ of ZFC, the proof can be copied to a proof
$\exists M\>\mathrm{CntTrans}(M)\land\phi^{M}$.

  3. 3.

Extend ZFC to ZFC+ by adding the new constant symbol $\mathrm{M}$, the axiom
$\mathrm{CntTrans}(\mathrm{M})$, and the axiom $\phi^{\mathrm{M}}$ for each
axiom $\phi$ of ZFC . If ZFC is consistent, so is ZFC+.

  4. 4.

In ZFC+, $\mathrm{M}$ is a symbol that represents a countable transitive set
by fiat and
$\aleph_{0}^{\mathrm{M}}<\aleph_{1}^{\mathrm{M}}<\aleph_{2}^{\mathrm{M}}<\ldots$
are countable ordinals that are uncountable cardinals in $\mathrm{M}$.

  5. 5.

Assume there is a ZFC proof of $\mathrm{CH}$ for contradiction. The proof is a
finite list of axioms $\phi_{1},...,\phi_{k}$ and their logical consequences
$\phi_{k+1},...,\phi_{n}=\mathrm{CH}$. The same proof will work in ZFC+ by
relativizing each $\phi_{i}$ to $\mathrm{M}$ to show $CH^{\mathrm{M}}$, that
is, $(2^{\aleph_{0}})^{\mathrm{M}}=\aleph_{1}^{\mathrm{M}}$.

  6. 6.

Extend $\mathrm{M}$ to a bigger set $\mathrm{M}[G]$ with a table $G$ that
encodes $\aleph_{2}^{\mathrm{M}}$-many new subsets of $\aleph_{0}$, so that
(a) for any axiom $\phi$ there is a ZFC+ proof that $\phi^{\mathrm{M}[G]}$;
(b) there is a ZFC+ proof that $\lnot\mathrm{CH}^{\mathrm{M}[G]}$. This is
accomplished in Part II, Forcing.

  7. 7.

By (6a), the proof of $CH^{\mathrm{M}}$ can be syntactically copied to a proof
$CH^{\mathrm{M}[G]}$ together with the ZFC+ proofs of $\phi^{\mathrm{M}[G]}$
for each axiom $\phi$ needed. Those axioms include $\phi_{1},\ldots,\phi_{i}$
as well as axioms required to complete the forcing construction in (6).

  8. 8.

By 7 and (6b), ZFC+ is inconsistent, therefore by (4) ZFC is inconsistent.
Assuming ZFC is consistent, the conclusion is that there is no proof of
$\mathrm{CH}$.

How to extend $M$ to $\mathrm{M}[G]$ is Part II, Forcing. This part is done
inside ZFC+.

###  5.2 Part II: forcing

Every statement below, unless otherwise indicated, is preceded with “it is
derivable in ZFC+ that…” In particular, $\mathrm{M}$ is postulated by fiat and
its existence is impossible to derive in ZFC due to Gödel’s incompleteness
theorem.

  1. 1.

Since $\mathrm{M}$ is countable, it contains countably many subsets of
$\aleph_{0}^{\mathrm{M}}=\aleph_{0}$, and $\aleph_{2}^{\mathrm{M}}$ is
countable. Therefore, there exist $\aleph_{2}^{\mathrm{M}}$-many new subsets
of $\aleph_{0}$ not in $\mathrm{M}$. Represent this collection by an object
$G$ such that $\bigcup G:\aleph_{2}^{\mathrm{M}}\times\aleph_{0}\to\\{0,1\\}$
is a complete function whose “rows” are functions $\aleph_{0}\to\\{0,1\\}$
representing pairwise distinct subsets of $\aleph_{0}$ that are not in
$\mathrm{M}$. $G$ will be added to $\mathrm{M}$ to produce a new set
$\mathrm{M}[G]$ that is a model of ZFC+ with
$\lnot\mathrm{CH}^{\mathrm{M}[G]}$.

  2. 2.

First, define the poset $\mathbb{P}$ consisting of all finite partial
functions $p:\aleph_{2}^{\mathrm{M}}\times\aleph_{0}\to\\{0,1\\}$ ordered by
inclusion; each $p$ is called a forcing condition. By Pairing, each
$p\in\mathbb{P}$ is in $\mathrm{M}$ and $\mathbb{P}\in\mathrm{M}$. Each $p,q$
are compatible if $\exists r\>p\leq r\land q\leq r$ and can be patched
together to a bigger partial function.

  3. 3.

Any complete function $\bigcup
G:\aleph_{2}^{\mathrm{M}}\times\aleph_{0}\to\\{0,1\\}$ is the union of a
maximal ideal of $\mathbb{P}$: a maximal downward closed subset of
$\mathbb{P}$ in which members are pairwise compatible.

  4. 4.

For $\mathrm{M}[G]$ to be a model and satisfy ComprehensionM[G], it has to
include the preimages under $G$ of sets $r\subset x\times\mathbb{P}$ for
$x,r\in\mathrm{M}$. In addition, this operation of taking preimages under $G$
can be performed transfinitely. To do so, define the $\mathbb{P}$-name
hierarchy $\mathrm{M}^{\mathbb{P}}\subset\mathrm{M}$ (a ZFC+ set that is a
proper $\mathrm{M}$-class), by
$N_{\alpha+1}:=\mathcal{P}(N_{\alpha}\times\mathbb{P})\cap\mathrm{M}$ for any
successor ordinal $\alpha$, and $N_{\alpha}:=\bigcup_{\beta<\alpha}N_{\beta}$
for limit ordinal $\alpha$.

  5. 5.

$\mathrm{M}^{\mathbb{P}}=\bigcup N_{\alpha}$. Define the $G$-evaluation of a
$\mathbb{P}$-name $\tau$ to be
$\tau^{G}:=\\{\sigma^{G}\>|\>(\sigma,p)\in\tau\land p\in G\\}$. If
$\mathrm{M}[G]$ is a model satisfying Comprehension, it has to include each
such $\tau^{G}$. Now by wishful thinking let
$\mathrm{M}[G]:=\\{\tau^{G}\>|\>\tau\in\mathrm{M}^{\mathbb{P}}\\}$, and aim to
prove that $\mathrm{M}[G]$ thus minimally defined is indeed a model.

  6. 6.

Define the canonical name of $x\in\mathrm{M}$ to be
$\check{x}:=\\{(x,p)\>|\>p\in\mathbb{P}\\}$ and
$\Gamma:=\\{(\check{p},p)\>|\>p\in\mathbb{P}\\}$, show $\check{x}^{G}=x$ and
$\Gamma^{G}=G$, concluding that $\mathrm{M}\subsetneq\mathrm{M}[G]$ and
$G\in\mathrm{M}[G]$.

  7. 7.

For $\mathrm{M}[G]$ to be a model, it has to satisfy all ZFC axioms. To prove
ComprehensionM[G], ComprehensionM needs to be used. Specifically,
$z:=\\{\sigma^{G}\in\tau^{G}\>|\>\phi(\sigma^{G})\\}$ has to be in
$\mathrm{M}[G]$ for every $\sigma,\tau\in\mathrm{M}^{\mathbb{P}}$. It suffices
to show that $z=\upsilon^{G}$ for some $\upsilon\in\mathrm{M}^{\mathbb{P}}$.

  8. 8.

The natural candidate is
$\upsilon:=\\{(\sigma,p)\in\tau\>|\>\psi_{\phi}(\sigma,p)\\}$ for some formula
$\psi_{\phi}$, whereby $\psi_{\phi}(\sigma,p)$ is true when $p\in G$ forces
$\phi(\sigma^{G})$ to be true.

  9. 9.

It immediately follows that $G$ has to be generic: no new infinite "AND"
information can be encoded in $G$. In particular, for every $p$ and every
sentence $\phi$, if every $q\geq p$ has an extension $r\geq q$ that makes
$\phi$ true in every ideal $G\ni r$, then $p$ is forced to make $\phi$ true:
$\phi$ has to be decided in $\mathrm{M}[G]$, and no $q\geq p$ can possibly
decide $\lnot\phi$ is true. Iterating this requirement by structural
induction, $p$ forces $\phi$ to be true whenever every $q\geq p$ has $r\geq q$
forcing $\phi$ to be true.

  10. 10.

Genericity of $G$ is defined by the concept of density. A subset
$D\subset\mathbb{P}$ is dense if for all $q\in\mathbb{P}$ there is a $r\geq q$
such that $r\in D$. $G$ is generic over $\mathrm{M}$ if $G\cap
D\not=\emptyset$ for any $D\in M$ that is a dense subset of $\mathbb{P}$. It
follows that if $G$ is generic, for any $p\in G$ and any sentence $\phi$, if
the set $D$ of $q\in\mathbb{P}$ that force $\phi$ to be true is dense above
$p$, then $p$ forces $\phi$ to be true.

  11. 11.

Generic ideals $G$ exist as long as the ground model is countable: enumerate
all dense $D_{1},D_{2},\ldots$ in $\mathrm{M}$; at each step $i+1$ pick
$p_{i+1}\in D_{i+1}$ such that $p_{i+1}\geq p_{i}$; let
$G=\\{p\in\mathbb{P}\>|\>p\leq p_{i}$ for some $i\\}$. $G$ is not in
$\mathrm{M}$ if $\mathbb{P}$ is separative: for any $f\in\mathrm{M}$ of the
same domain and range as $\bigcup G$, $\\{p\in\mathbb{P}\>|\>p$ disagrees with
$f$ in some position$\\}$ is dense $\in\mathrm{M}$.

  12. 12.

A condition $p$ forces $\phi(\tau_{1},\ldots,\tau_{k})$ if $p\in G$ implies
$\phi^{\mathrm{M}[G]}(\tau_{1}^{G},\ldots,\tau_{k}^{G})$. The fundamental
theorem of forcing (FTF) states that for any $\phi$, the collection of
$(p,\tau_{1},\ldots,\tau_{k})$ where $p\Vdash\phi$ and the $\tau_{i}$s have
max name rank $\alpha$ is a set $\mathcal{F}^{\phi}_{\alpha}\in\mathrm{M}$
(Definability), and $\phi^{\mathrm{M}[G]}$ iff there is some $p\in G$ that
forces $\phi$ (Truth). Moreover, $p\Vdash\phi$ and $q\geq p$ implies
$q\Vdash\phi$. FTF is a metatheorem: for any $\phi$ there is a separate ZFC+
proof of FTF for $\phi$.

  13. 13.

Using the FTF, the metatheorem that $\mathrm{M}[G]$ is a model is proven. For
any axiom $\phi$ of ZFC, there is a ZFC+ proof of $\phi^{\mathrm{M}[G]}$.
Therefore $CH^{\mathrm{M}[G]}$ goes through.

  14. 14.

It remains to show that forcing does not collapse cardinals. This is achieved
by showing that for each function $f$ in $\mathrm{M[G]}$ each element $x$ in
$f$’s domain is forced to map to at most countably many distinct $y$ in $f$’s
range by elements $q_{y}$ in $\mathbb{P}$. A combinatorial argument finishes
the proof.

##  6 Coming back to omitted steps

###  6.1 Reflection Principle

Any sentence can be reflected in a countable transitive set $M$. This is a
metatheorem, or better, an algorithm that takes any $\phi$ as input and
returns a ZFC proof of $\exists
M\>\mathrm{CntTrans}(M)\land\phi\leftrightarrow\phi^{M}$. We sketch the
algorithm here following the excellent exposition in Weaver (2014).

The first step is a lemma schema that takes as input a finite list of formulas
$\phi_{1},\ldots,\phi_{n}$ and produces a ZFC proof of existence of a
countable set $M$ that contains all the elements needed so that the formulas
have “similar” behavior with their variables restricted to $M$ as when their
variables are unconstrained. More precisely, for any
$\phi(x_{1},\ldots,x_{k})$ in the list with all free variables displayed and
for any $a_{1},\ldots,a_{k}\in M$, if there exists $x_{j}$ such that
$\phi(a_{1},\ldots,a_{j-1},x_{j},a_{j+1},\ldots,a_{k})$, then there exists
$x_{j}\in M$ such that
$\phi(a_{1},\ldots,a_{j-1},x_{j},a_{j+1},\ldots,a_{k})$.

Lemma Schema. Let $\phi_{1},\ldots,\phi_{n}$ be any formulas with free
variables among $x_{1},\ldots,x_{k}$. There is a ZFC proof that there exists a
countable set $M$ such that for any formula $\phi_{i}$ in the list and for any
variable $x_{j}$ and any constants $a_{1},\ldots,a_{k}\in M$, whenever
$\exists x_{j}\>\phi_{i}(a_{1},\ldots,x_{j},\ldots,a_{k})$ holds, $\exists
x_{j}\in M\>\phi_{i}(a_{1},\ldots,x_{j},\ldots,a_{k})$ also holds.646464Here,
$a_{j}$ is a dummy constant but it is not called out as such in order to
reduce notational clutter. That is to say, whenever there exists $x_{j}$ that
makes formula $\phi_{i}$ true with other variables assigned to specific
elements of $M$, keeping the same assignments for other variables there exists
$x_{j}\in M$ making $\phi_{i}$ true.

Proof Sketch. We create a countable sequence of sets $M_{0}=\omega\subset
M_{1}\subset M_{2}\subset\cdots$ whereby $M:=\bigcup_{l}M_{l}$. At each step
$l+1$, for every formula $\phi_{i}$ and variable $x_{j}$, and for all possible
assignments of the other variables to elements from $M_{l}$, if there exists
$x_{j}$ making the formula true, choose one such element and add it to
$M_{l+1}$.656565This requires AC, or at least that $\\{x_{j}\>|\>\phi(\ldots
x_{j}\ldots)\\}$ can be well-ordered. With AC, we can choose an element from
the set of $x_{j}$ of lowest rank making $\phi_{i}$ true, and details are
omitted.

In other words, for each $i,j$ and for each $a_{1},\ldots,a_{k}\in M_{l}$ if
$\exists x_{j}\>\phi_{i}(a_{1},\ldots,x_{j},\ldots,a_{k})$ then choose one
element $a$ such that $\phi_{i}(a_{1},\ldots,x_{j}=a,\ldots,a_{k})$ and add
$a$ to $M_{l+1}$.

The set $M_{l+1}$ is countable by induction: assuming $M_{l}$ is countable,
there are countably many tuples $a_{1},\ldots,a_{k}$ times finitely many
formulas times finitely many variables, and each such combination generates at
most one additional element to be added to $M_{l+1}$. Therefore $M$ is
countable.

Now assume that for some $a_{1},\ldots,a_{j}-1,a_{j}+1,\ldots,a_{k}\in M$,
$\exists x_{j}\>\phi_{i}(a_{1},\ldots,x_{j},\ldots,a_{k})$. In other words for
some $a$ not necessarily in $M$,
$\phi_{i}(a_{1},\ldots,a_{j}-1,a,a_{j}+1,\ldots,a_{k})$. Well, each one of
$a_{1},\ldots,a_{k}$ is in some $M_{l}$, so choose $l^{*}$ such that
$a_{1},\ldots,a_{k}\in M_{l^{*}}$. But then some $a^{*}$ should have been
added to $M_{l^{*}+1}$ such that $\phi_{i}(a_{1},\ldots,a^{*},\ldots,a_{k})$.
Therefore some such $a^{*}$ is in $M$. Therefore $\exists x_{j}\in
M\>\phi_{i}(a_{1},\ldots,x_{j},\ldots,a_{k})$.

Given any input formulas $\phi_{1},\ldots,\phi_{n}$, the above proof can be
written down mechanically in full ZFC formality. $\square$

Theorem: The Reflection Principle Algorithm. Given any input sentence $\phi$
there is a ZFC proof that there is a countable transitive set $M$ such that
$\phi\leftrightarrow\phi^{M}$.

Proof. Given $\phi$, the strategy to generate $M$ will be to break down $\phi$
into the list $\phi_{1},\ldots,\phi_{n}$ of all its component formulas, apply
the above lemma to the list, and then show by structural induction on $\phi$
that all subformulas as well as $\phi$ are reflected in the resulting set $M$.
For this to work technically, the list of formulas needs to be constructed
carefully. First, the axiom of extensionality will be needed (for all $x$ and
$y$, $x=y\leftrightarrow(\forall z\>z\in x\leftrightarrow z\in y)$. So let’s
assume our starting list is $\phi_{1}=\phi,\phi_{2}=$ Extensionality. Now we
break down to components to expand the list: if $\phi_{i}=\lnot\psi$ is in the
list, add $\psi$ to the list; if $\phi_{i}=\psi\land\chi$ or
$\phi_{i}=\psi\rightarrow\chi$ is in the list, add both $\psi$ and $\chi$ to
the list; if $\phi_{i}=\forall x\>\psi$, add $\psi$ to the list. Continue
until no more formulas can be added. Now we need another trick: if the
resulting list so far is $\phi_{1},\ldots,\phi_{n}$, apply the above lemma to
the negations: $\lnot\phi_{1},\ldots,\lnot\phi_{n}$.

Now let $M$ be the countable set resulting from the lemma. Using structural
induction starting from atomic $\phi_{i}$ (i.e., of the form $x=y$ or $x\in
y$) and moving up in formula complexity, we will show for each $\phi_{i}$ that
for all $a_{i},\ldots,a_{k}\in M$,
$\phi_{i}(a_{1},\ldots,a_{k})\leftrightarrow\phi_{i}^{M}(a_{1},\ldots,a_{k})$.

Let $\phi_{i}$ be atomic: well, $(x_{1}=x_{2})^{M}$ is $x_{1}=x_{2}$ and
$(x_{1}\in x_{2})^{M}$ is $x_{1}\in x_{2}$ so this case is trivial.

Let $\phi_{i}=\lnot\psi$. By inductive assumption we have
$\psi\leftrightarrow\psi^{M}$ for all $a_{j}\in M$, and therefore
$\lnot\psi\leftrightarrow\lnot\psi^{M}$ therefore
$\lnot\psi\leftrightarrow(\lnot\psi)^{M}$.

Similarly the cases of $\psi\rightarrow\chi$ or $\psi\land\chi$ are trivial.

The only case that is interesting is when
$\psi(x,x_{1},\ldots,x_{k})\leftrightarrow\psi^{M}(x,x_{1},\ldots,x_{k})$ has
been proven for a subformula that has the unbound variable $x$ (with other
unbound variables $x_{j}$ displayed), and we need to show that for all
$a_{1},\ldots,a_{k}\in M$:

$\forall x\>\psi(x,a_{1},\ldots,a_{k})\leftrightarrow\forall x\in
M\>\psi^{M}(x,a_{1},\ldots,a_{k})$

Fix the $a_{j}$s in $M$. If $\forall x\>\psi(x,a_{1},\ldots,a_{k})$, then
certainly $\forall x\in M\>\psi(x,a_{1},\ldots,a_{k})$. By inductive
assumption, $\psi(\ldots)\leftrightarrow\psi^{M}(\ldots)$ therefore $\forall
x\in M\>\psi^{M}(x,a_{1},\ldots,a_{k})$. Conversely, if $\forall
x\>\psi(x,a_{1},\ldots,a_{k})$ is false, then $\exists
x\>\lnot\psi(x,a_{1},\ldots,a_{k})$ and by the lemma some $x\in M$ should have
been included (here is why we needed to apply the lemma with all negations of
the $\phi_{i}$s) and therefore $\exists x\in
M\>\lnot\psi(x,a_{1},\ldots,a_{k})$, and by inductive assumption $\exists x\in
M\>\lnot\psi^{M}(x,a_{1},\ldots,a_{k})$ or equivalently $\forall x\in
M\>\psi^{M}(x,a_{1},\ldots,a_{k})$ is false.

Since the sentence $\phi$ is in the list, $\phi\leftrightarrow\phi^{M}$ is
established. Moreover, $M$ is countable and extensional: $\forall x,y\in
M\>x=y\leftrightarrow(\forall z\in M\>z\in x\leftrightarrow z\in y)$. Now the
Mostowski collapse theorem, discussed below, can be applied to $M$ to obtain
countable transitive set $M^{\prime}$ where
$\phi\leftrightarrow\phi^{M^{\prime}}$.

Given any input $\phi$, the above proof can be written down mechanically in
full ZFC formality. $\square$

It remains to establish that an extensional set $M$ can be converted to a
transitive set $N$ so that for every formula $\phi$,
$\phi^{M}\leftrightarrow\phi^{N}$. The map $f$ from $M$ to $N$ will be an
$\in$-isomorphism: a bijection such that $x\in y$ iff $f(x)\in f(y)$ for all
$x,y\in M$.

Theorem. Let $f:M\to N$ be an $\in$-isomorphism. Let
$\phi(x_{1},\ldots,x_{k})$ be any formula with free variables displayed. Then
for any $a_{1},\ldots,a_{k}\in M$, the formula

$\phi^{M}(a_{1},\ldots,a_{k})\leftrightarrow\phi^{N}(f(a_{1}),\ldots,f(a_{k}))$

is provable in ZFC.

Proof sketch. This is an easy induction on the structure of $\phi$. The base
cases $x=y$ and $x\in y$ as well as the cases of $\rightarrow$ and $\land$ are
trivial. Therefore, assume we have a ZFC proof that
$\phi^{M}(a_{1},\ldots,a_{k})\leftrightarrow\phi^{N}(f(a_{1}),\ldots,f(a_{k}))$
for all $a_{1},\ldots,a_{k}\in M$.

We need to show $\forall
x_{j}\>\phi^{M}(a_{1},\ldots,x_{j},\ldots,a_{k})\leftrightarrow\forall
x_{j}\>\phi^{N}(f(a_{1}),\ldots,x_{j},\ldots,f(a_{k}))$. Because $f$ is a
bijection, if $\forall x_{j}\>\phi^{M}(\ldots)$ fails, the $a_{j}$ that makes
it fail is mapped 1-1 to an $f(a_{j})$ that makes $\phi^{N}(\ldots
f(a_{j})\ldots)$ fail by inductive assumption, and therefore $\forall
x_{j}\>\phi^{N}(\ldots)$ fails. Similarly if $\forall x_{j}\>\phi^{M}(\ldots)$
holds, then for any $a_{j}$ $\phi^{M}(\ldots a_{j}\ldots)$ holds, by inductive
assumption $\phi^{N}(\ldots f(a_{j})\ldots)$ holds and therefore by $f$ being
surjective $\forall x_{j}\>\phi^{N}(\ldots)$ holds. $\square$

Finally, given a set $M$ where extensionality holds, we can find an
$\in$-isomorphism $f$ to a transitive set $N$. The following theorem is
provable in a much more general form, where the relationship does not need to
be $\in$ as long as it is well founded. However, we won’t need the general
form.

Theorem: Mostowski Collapse Lemma. Let $M$ be a set where ExtensionalityM
holds. $M$ is $\in$-isomorphic to a transitive set $N$.

Proof. Define $f:M\to V$ by $f(x)=\\{f(y)\>|\>y\in x\\}$. This definition is
by transfinite recursion and it makes sense because of Foundation.666666More
generally, instead of ’$\in$’ a relation $R$ that is well founded, i.e., where
any set of elements has an $R$-minimal element, suffices because well-
foundedness enables transfinite recursion on $R$.

The set $N:=\\{y\>|\>\exists x\in M\>y=f(x)\\}$ exists by Replacement. We need
to show that $f$ is an $\in$-isomorphism and that $N$ is transitive.

To show $f$ is an $\in$-isomorphism, let $y\in x\in M$. Then
$f(x)=\\{f(y)\>|\>y\in x\\}$ so by definition it follows that $f(y)\in f(x)$.

To show that $N$ is transitive, let $w\in z\in N$, to show $w\in N$. Well,
$z=f(x)$ for some $x\in M$, therefore $z=\\{f(y)\>|\>y\in x\\}$ therefore
$w=f(y)$ for some $y\in x$ therefore $w$ is in the image of $f$, i.e., $w\in
N$. $\square$

Therefore, given any sentence $\phi$, a ZFC proof of $\exists
M\>\mathrm{CntTrans}(M)\land\phi\leftrightarrow\phi^{M}$ can be written down
mechanically. This is a ridiculously powerful result. Given any finite number
of axioms of ZFC, they hold in a countable transitive set $M$. Equivalently,
given any ZFC proof of some $\phi$, we can convert it to a ZFC proof of
$\exists M\>\mathrm{CntTrans}(M)\land\phi^{M}$.

Example of Mostowski Collapse. The reader may wonder what, if anything, is the
effect of the Mostowski Collapse procedure in a set. Let’s give a simple
example of $M$ and calculate the Mostowski collapse:

$M:=\\{1,2,2022,\omega,\omega\cdot 2022,\\{2022,\omega\cdot 2022\\}\\}$

By definition $f(1)=\\{f(y)\>|\>y\in x\\}$. Now, $\emptyset\in 1$, however
because $\emptyset\not\in M$ it is not in the domain of $f$ therefore $f(1)$
becomes $\emptyset$ or if you prefer, $0$. Similarly, $f(2)=1$ and
$f(2022)=2$.

The reader can easily verify that $f(\omega)=\\{0,1,2\\}=3$ and similarly
$f(\omega\cdot 2022)=4$. Finally, $f(\\{2022,\omega\cdot 2022\\})=\\{2,4\\}$.

Therefore the resulting $N$ is $\\{0,1,2,3,4,\\{2,4\\}\\}$, a transitive set
$\in$-isomorphic to $M$ and quite a simplification from $M$.

Existence of $M$ versus existence of a proof of existence of $M$. Given
$\phi$, the Reflection Principle algorithm outputs a ZFC proof of $\exists
M\>\mathrm{CntTrans}(M)\land\phi\leftrightarrow\phi^{M}$. It always terminates
and can be implemented in software. The algorithm goes through all subformulas
of $\phi$ and writes down the respective ZFC subproofs as sketched above. The
resulting ZFC proof states the existence of an countable set $M$ with the
requisite properties. This latter proof, by contrast, is profoundly non-
constructive. It involves infinitely many iterative applications of the axiom
of choice. There is no ontological conclusion that can be drawn about the
existence of any such $M$. $M$ is neither shown to truly exist (whatever that
would mean), neither is anything of this sort needed for the proof of the
independence of $\mathrm{CH}$. All we need is that we can syntactically and
mechanically convert any ZFC theorem $\phi$ to a ZFC theorem $\exists
M\>\mathrm{CntTrans}(M)\land\phi^{M}$.

###  6.2 Forcing consistency of $\mathrm{CH}$

Consistency of $\mathrm{CH}$ is the second part of independence of
$\mathrm{CH}$. Godel (1939) originally showed it by building an inner model of
ZFC — a formula $L(x)$ that describes a proper class of sets such that all
axioms $\phi$ hold as $\phi^{L}$ and such that $CH^{L}$ holds. $L(x)$ is the
class of constructible sets, a topic beyond scope here. The reader is referred
to Smullyan and Fitting (2010).

The forcing machinery can be deployed to provide a much simpler proof of this
part. The argument below follows Weaver (2014).

Starting from the same ground model $\mathrm{M}$ in ZFC+, the goal now is to
extend through forcing to a model $\mathrm{M}[G]$ that contains a bijection
between $(2^{\aleph_{0}})^{\mathrm{M}[G]}$ and $\aleph_{1}^{\mathrm{M}[G]}$ so
that $(|2^{\aleph_{0}}|=\aleph_{1})^{\mathrm{M}[G]}$. Can the reader think of
what object $G$ we may want to add to $\mathrm{M}$?

The first thing that comes to mind is a bijection between the countable sets
$(2^{\aleph_{0}})^{\mathrm{M}}$ and $\aleph_{1}^{\mathrm{M}}$. Let’s define a
separative poset $\mathbb{P}$ that contains partial constructions $p$ of this
bijection such that $p\in\mathrm{M}$ for all $p\in\mathbb{P}$. Analogously to
proving consistency of $\lnot\mathrm{CH}$, we may be inclined to let $p$ be
finite partial bijections
$(2^{\aleph_{0}})^{\mathrm{M}}\to\aleph_{1}^{\mathrm{M}}$. So let’s follow
this through and see what properties $\bigcup G$ and $\mathrm{M}[G]$ have:

  * •

For any subset $s\subset\aleph_{0}$ in $\mathrm{M}$, the set
$D_{s}:=\\{p\in\mathbb{P}\>|\>s\in\mathrm{Dom}(p)\\}$ is a dense set in
$\mathrm{M}$, therefore $s\in\mathrm{Dom}(\bigcup G)$.

  * •

For any element $\alpha\in\aleph_{1}^{\mathrm{M}}$, the set
$D^{\prime}_{\alpha}:=\\{p\in\mathbb{P}\>|\>\alpha\in\mathrm{Ran}(p)\\}$ is a
dense set in $\mathrm{M}$, therefore $\alpha\in\mathrm{Ran}(\bigcup G)$.

  * •

In conclusion, $\bigcup G$ is a complete bijection and
$((2^{\aleph_{0}})^{\mathrm{M}}=\aleph_{1}^{\mathrm{M}})^{\mathrm{M}[G]}$.

Are we done? Not quite: the set $(2^{\aleph_{0}})^{\mathrm{M}[G]}$ could be
bigger than $(2^{\aleph_{0}})^{\mathrm{M}}$ if forcing with $\mathbb{P}$
introduced new subsets of $\aleph_{0}$. Moreover, $\aleph_{1}^{\mathrm{M}}$
could be countable in $\mathrm{M}[G]$ if forcing with $\mathbb{P}$ introduces
a new surjection $\aleph_{0}\to\aleph_{1}^{\mathrm{M}}$. And indeed, just like
in the case of forcing for consistency of $\lnot\mathrm{CH}$, forcing with
finite partial functions
$(2^{\aleph_{0}})^{\mathrm{M}}\to\aleph_{1}^{\mathrm{M}}$ introduces new
functions with domain $\aleph_{0}$ and in particular new subsets of
$\aleph_{0}$.

Here is some intuition why. Take any injective function $f\in\mathrm{M}$,
$f:\>\omega\to(2^{\aleph_{0}})^{\mathrm{M}}$. There are many such functions
that are always $\in\mathrm{M}$. For example, $f(n)=n$ is such a function
because $n\in(2^{\aleph_{0}})^{\mathrm{M}}$ when $n$ is viewed as an ordinal.
Also, $f_{k}(n):=kn$ is such a function, as is really any injective function
$f:\omega\to 2^{\aleph_{0}}$ definable by a formula $\phi(x,y)$ that is true
iff $x\in\omega$ and $y\in f(x)$.

Now take $\bigcup G\circ f$ to produce a function
$s_{f}:=\omega\to\aleph_{1}^{\mathrm{M}}$. Can the reader see how new subsets
of $\omega$ are formed?

Let’s cut the range into two infinite parts within $\mathrm{M}$, and call one
of them $0$ and the other $1$. For example (as in Weaver (2014)) we could say
that $\alpha<\omega$ corresponds to $0$ and
$\omega\leq\alpha<\aleph_{1}^{\mathrm{M}}$ corresponds to 1. Any partition in
two infinite pieces works as long as they are in $\mathrm{M}$.

This automatically converts $s_{f}$ to a function $\omega\to\\{0,1\\}$, or
equivalently a subset of $\omega$. Could this subset possibly be in
$\mathrm{M}$ already? Not if $G$ is generic: given any $p\in\mathbb{P}$, and
given any $\mathrm{M}$-set $t\subset\omega$, it is necessarily possible to
extend $p$ to $q\geq p$ that makes $s_{f}$ and $t$ differ in some position.
That is where we need both pieces of the partition to be infinite so that $p$
exhausts neither of them.

The problem of generating new $\omega$-subsets arises because any
$p\in\mathbb{P}$ only forces a finite part of $s_{f}$. How can we change
$\mathbb{P}$ in a way to ensure that $s_{f}\in\mathrm{M}$ whenever
$f\in\mathrm{M}$? The solution of how to do this emerges by observing that
given $\bigcup G:(2^{\aleph_{0}})^{\mathrm{M}}\to\aleph_{1}^{\mathrm{M}}$, any
$f:\omega\to(2^{\aleph_{0}})^{\mathrm{M}}$ in $\mathrm{M}$ induces a countable
partial bijection
$p:(2^{\aleph_{0}})^{\mathrm{M}}|_{\mathrm{Ran}(f)}\to\aleph_{1}^{\mathrm{M}}$,
whose domain is $\mathrm{Ran}(f)$ and such that $p\subset\bigcup G$.

So, if we ensure that $\mathbb{P}$ contains all countable partial bijections
$p:(2^{\aleph_{0}})^{\mathrm{M}}\to\aleph_{1}^{\mathrm{M}}$ such that
$p\in\mathrm{M}$, the hope is that $G$ won’t introduce any new ones, and
therefore it won’t introduce any new subsets $s$ of $\omega$. Here is the
rationale: consider a chain of elements of $\mathbb{P}$,
$p_{1}<p_{2}<p_{3}<\cdots$. Given $f:\omega\to(2^{\aleph_{0}})^{\mathrm{M}}$
in $\mathrm{M}$, and given a partition of $\aleph_{1}^{\mathrm{M}}$ in two
parts mapping to $0$ and $1$, each $p_{i}$ partially defines a subset $s_{f}$
of $\omega$ by $p_{i}\circ f:\omega\to\\{0,1\\}$. In $\mathrm{M}[G]$, the
complete subset $s_{f}$ defined by $\bigcup G|_{\mathrm{Ran}(f)}\circ f$ is
present. However, notice that $\bigcup
G|_{\mathrm{Ran}(f)}=\bigcup_{i}p_{i}\circ f$, where $p:=\bigcup_{i}p_{i}$ is
just a countable partial bijection
$(2^{\aleph_{0}})^{\mathrm{M}}\to\aleph_{1}^{\mathrm{M}}$. Because each
$p_{i}\in\mathrm{M}$ we have $p\in\mathrm{M}$ and consequently
$p\in\mathbb{P}$. Therefore $s_{f}$ is already a member of $\mathrm{M}$!

We can formalize this with a lemma:

Definition. A poset $\mathbb{P}$ is $\omega$-closed if for any infinite chain
$p_{1}<p_{2}<p_{3}<\cdots$ of elements $p_{i}\in\mathbb{P}$,
$\bigcup_{i}p_{i}\in\mathbb{P}$.

Lemma. Let $\mathbb{P}$ be ($\omega$-closed)M and let $X\in\mathrm{M}$. Any
function $f:\omega\to X$ in $\mathrm{M}[G]$ is already in $\mathrm{M}$.

Proof. Let $S\in\mathrm{M}$ be the set of all functions $\omega\to X$ in
$\mathrm{M}$. Let $\tau$ be a $\mathbb{P}$-name for $f$ and let $p$ force
“$\tau$ is a function $\check{\omega}\to\check{X}$”. If we show that the set
of $r$ that force $\tau\in\check{S}$ is dense above $p$, i.e., that at $p$ it
is necessarily possible that $f$ is in $S$, then $(f\in S)^{\mathrm{M}[G]}$
and therefore $f\in S$.

Because $p$ forces “$\tau$ is a function $\check{\omega}\to\check{X}$”, it
forces “$\forall x\in\check{\omega}\>\exists y\in\check{X}$ such that $(x,y)$
is a pair of values in $\tau$”. Therefore for any $n\in\omega$ and
$\sigma=\check{n}$, the set of $q$ that force “$\exists y\in\check{X}$ such
that $(\sigma,y)$ is a pair of values in $\tau$” is dense above $p$. Therefore
the set of $r$ that force “$(\check{n},\check{c_{n}})$ is a pair of values in
$\tau$” for some $c_{n}\in X$ is dense above $q$.

Now starting with any $q\geq p$ let $p_{0}\geq q$ force “$\tau$ maps
$\check{0}$ to $\check{c_{0}}$” for some $\check{c_{0}}$, let $p_{1}\geq
p_{0}$ force “$\tau$ maps $\check{1}$ to $\check{c_{1}}$” for some
$\check{c_{1}}$, and so on defining a sequence $p_{0}\leq p_{1}\leq
p_{2}\leq\cdots$. Since ($\mathbb{P}$ is $\omega$-closed)M, $r:=\bigcup
p_{i}\in\mathbb{P}$ and $r$ forces “$(\check{n},\check{c_{n}})$ is a pair of
values in $\tau$” for every $n\in\omega$ therefore $r\Vdash\tau\in\check{S}$.
Because $q$ was arbitrary, the set of $r$ that force $\tau\in\check{S}$ is
indeed dense above $p$ and therefore $f\in S$. $\square$

Theorem. $CH^{\mathrm{M}[G]}$ is a ZFC+ theorem.

Proof. By the lemma above, in $\mathrm{M}[G]$ there are no new functions
$f:\omega\to X$ for any $X\in\mathrm{M}$. Therefore there are no new subsets
of $\aleph_{0}$ and moreover there is no surjection
$\aleph_{0}\to\aleph_{1}^{\mathrm{M}}$, which means that
$(2^{\aleph}_{0})^{\mathrm{M}[G]}=(2^{\aleph}_{0})^{\mathrm{M}}$ and
$\aleph_{1}^{\mathrm{M}[G]}=\aleph_{1}^{\mathrm{M}}$.

In conclusion, $\bigcup G$ is a bijection from
$(2^{\aleph}_{0})^{\mathrm{M}[G]}$ to $\aleph_{1}^{\mathrm{M}[G]}$. $\square$

##  7 Alternative forcing proofs of consistency of $\lnot\mathrm{CH}$w

There are many alternative proofs of consistency of $\lnot\mathrm{CH}$.
However, all of them are based on forcing. They share the underlying structure
of the poset $\mathbb{P}$ that encodes a collection of new subsets of
$\aleph_{2}$ and some nonstandard version of logic that implements the
nonstandard logic of forcing—the “necessarily possible”, or $\forall q\geq
p\>\exists r\geq q$ such that “$\ldots$”.

###  7.1 Original syntactic approach by Cohen

The very original construction by Cohen described in two parts in his 1963 and
1964 PNAS papers was perhaps the cleanest after all. In the first part (1963)
he defined forcing. Here is part of the definition, with notation changed to
match this manuscript:

> "Definition 6. By induction, we define the concept of “$p$ forces $\phi$” as
> follows: I. If $r>0$, $p$ forces $\forall_{\alpha}x\>\phi(x)$ if for all
> $q\geq p$ $q$ does not force $\lnot\phi(\mathcal{F}_{\beta})$ for
> $\beta<\alpha$. $p$ forces $\exists_{\alpha}x\>\phi(x)$ if for some
> $\beta<\alpha$, $p$ forces $\phi(\mathcal{F}_{\beta})$. […] The most
> important part of Definition 6 is I, the other parts are merely obvious
> derivatives of it."

Here, $\forall_{\alpha}$ and $\exists_{\alpha}$ are quantifiers limited to
rank $<\alpha$. Describing Cohen’s construction of sets $\mathcal{F}$ would be
too big a digression.

In Cohen’s original construction, the poset $\mathbb{P}$ is defined in the
ground model and then truth is assigned in $\mathrm{M}[G]$ as follows. The
collection of all sentences of ZFC, allowing for parameters ranging across
$\mathrm{M}[G]$, is countable. Enumerate all sentences:

$\psi_{1},\psi_{2},\psi_{3},\ldots,\psi_{n},\ldots$

Now it is shown that if $p\not\Vdash\phi$ then there is $q\geq p$ such that
$q\Vdash\lnot\phi$. Then, starting with $p_{0}=\\{\\}$, at each step $i$
extend to $p_{i+1}\geq p_{i}$ by considering $\psi_{i}$. If $p_{i}\Vdash\phi$,
then let $p_{i+1}=p_{i}$. Otherwise there is $q\geq p_{i}$ such that
$q\Vdash\lnot\psi_{i}$. Let $p_{i+1}:=q$. At the end of the construction we
have a complete sequence $p_{0}\leq p_{1}\leq p_{2}\leq\cdots$ that decides
the truth of every sentence $\psi_{i}$ in the resulting model.

There are many tricky technical details for all this to work. The ordering of
the sentences as well as ranks of each element of the model are quite
involved. Notice also that the ground model has to be countable from the
perspective of the “outside” universe $V$: all possible sentences are
enumerated in $V$.

Despite the technical complexities, the main idea is perhaps the simplest:
Cohen wanted to add $\aleph_{2}$-many subsets of $\aleph_{0}$ and obtain a
model $\mathrm{M}[G]$. To achieve that, he picked an order that works for all
sentences $\psi_{i}$ of $\mathrm{M}[G]$ and constructed a $G$ that decides
them one-by-one by brute force. The later installations of forcing achieve the
same task in a more elegant and less syntactical way by using dense sets, but
obscure the honest clarity of the goal.

###  7.2 Standard versus nonstandard models

It is worthwhile to comment on the role of countable models versus nonstandard
models. A standard model $M$ of ZFC is one where $\in_{M}:=\in_{V}\cap(M\times
M)$ is true set membership and sentences follow the standard binary logic. To
produce the standard model $M[G]$ where $\mathrm{CH}$ breaks, a generic $G$ is
needed, which in turn necessitates that $M$ is countable. However, the
consistency of $\lnot\mathrm{CH}$ does not strictly require that a standard
model is produced. The forcing relation itself provides a notion of $\in$ in
the ground model $M^{\mathbb{P}}$ with nonstandard rules—$\sigma$ “in” $\tau$
with respect to $p$ if $\sigma^{G}\in\tau^{G}$ in $M[G]$ when $p\in G$—and
nonstandard logic that defines different truth values of every sentence
localized to every $p\in\mathbb{P}$. It can be shown that all axioms are true
in this nonstandard assignment of truth—they are true at $p=\\{\\}$—and
therefore all theorems go through as before. Then, it can be shown that
$\lnot\mathrm{CH}$ holds at $p=\\{\\}$ in this nonstandard logic.676767In
fact, even a sentence $\phi$ that is not false at $\\{\\}$ and is true in some
$p\in\mathbb{P}$ is automatically shown to be consistent; for
$\lnot\mathrm{CH}$ the stronger statement of truth at $p=\\{\\}$ applies. In
this way, the ground model can be any $M$ or even $V$ itself. With that idea
in mind, there are proofs of consistency of $\lnot\mathrm{CH}$ that are based
on nonstandard models such as Boolean valued models and S4 modal logical
models. In these models, existence of a generic $G$ is not needed. Instead,
the properties that such a generic $G$ would have, had it existed, are just
the guiding principle in assigning truth values to sentences for every $p$ in
the forcing notion $\mathbb{P}$. The forcing notion itself plays pretty much
the same role in all these approaches.

###  7.3 Boolean valued models

A Boolean algebra is an algebra on the subsets of a set $S$, with operations
$a\land b:=a\cap b$, $a\lor b:=a\cup b$, $\lnot a:=S\setminus a$, where $1:=S$
and $0:=\\{\\}$. The partial order $\leq$ is defined by $\subseteq$. Boolean
algebras generalize truth values: the algebra of $\\{0,1\\}$ is the simplest
Boolean algebra, generated by $S=\\{\emptyset\\}$.

The poset $\mathbb{P}$ can give rise to a Boolean algebra, and then a Boolean
valued model can be defined. The reader is referred to Bell (1977) or Jech
(2002) for the full details, as well as to the highly readable exposition by
Timothy Chow (2007). Risking confusion of the reader, below is a very brief
introduction to Boolean algebras and a few words on how this is done.

An ideal of a Boolean algebra $B$ is a set $I$ such that (1) $0\in I;1\not\in