Advanced Set Theory (Lecture)

Course on Set Theory, and based on Kunen Set Theory. It was hold by Dr. Hazel Brickhill at the University of Constance during my 2nd Semester.

1st Lecture: Intro

• 1878 the Continuum Hypothesis has been stated by G. Cantor
• 1900 ca. D. Hilbert points for the century, ZFC has been formulated and K. Gödel] proved his Incompleateness Theorems
• 1940 K. Gödel proved $ZFC/⊢\neg CH$
• 1963 P. Cohen proved $ZFC/⊢CH$

We will focus more on the proof by Cohen, since it uses the method called Forcing which will be of our interest during the course. First, let’s examine a couple of ways which would seem to work but because of Gödel Second Incompleateness Theorem, namely that $T/⊢con(T)$ for a given theory $T$:

• $ZFC⊢(ZFC/⊢CH)$ but in order to do that you need $ZFC⊢con(ZFC)$ which goes against the Second Incompleateness Theorem.

• Alternatively: $ZFC/⊢CH\leftrightarrow con(ZFC+\neg CH)$, then you get $ZFC⊢con(ZFC)$ which does against the Second Incompleateness Theorem.

On the other hand, we might: $con(ZFC)\Rightarrow con(ZFC+\neg CH)$ which seems to be doable for both proofs.

Remember that $con(ZFC)\Rightarrow \text{"}ZFC$ is satisfiable”, which means that ZFC must have a model. Finding a model of ZFC, as far as I know, should consisting in defining a language ${\mathcal{L}}_{ϵ}$, which consists of the usual first order logic + the symbol $ϵ$ which denotes the usual $\in$. The prof. then mentioned two methods which we might follow, though I didn’t actually get it.

2nd Lecture

The reason why we’re interested in this process is because we want to show that $(V_k,\in )\models ZFC$, but this notion of satisfaction is not one we have defined within ${\mathcal{L}}_{ϵ}$. This can be done (and is important for some results) but takes some care. Instead we take a different approach here by relativizing formulae.

Relativization is a process that takes formulae from a given language ${\mathcal{L}}_{ϵ}$ and restricts the domain of their quantifiers to a set $W$. In order to define this process we started to analyse which formulae remain exactly the same and which changes. The following is the definition by  recursion of Relativisation:

• $(x\in y{)}_W:=x\in y$

• $(x=y{)}_W:=x=y$

• $(\neg \varphi {)}_W:=\neg {\varphi }_W$

• $(\varphi \wedge \psi {)}_W:={\varphi }_W\wedge {\psi }_W$

since the other connectives can be defined through these, there’s no need to write them all. With the quantifiers things changes:

• $({\exists }_x\varphi (x){)}_W:={\exists }_x(x\in W\wedge {\varphi }_W(x))$

• $({\forall }_x\varphi (x){)}_W:={\forall }_x(x\in W\to {\varphi }_W(x))$

For every formula $\varphi$ in ${\mathcal{L}}_{ϵ}$ there exists an ${\varphi }_W$. Though, not always if a formula holds in a theory its relativization to a certain set must hold as well. For example we saw that the Axiom of Extentionality: ${\forall }_x{\forall }_y({\forall }_z(z\in x\leftrightarrow z\in y)\to x=y)$ on the set $W:=\{\varnothing ,\{\{\varnothing \}\}\}$ doesn’t hold. It holds iff. the set $W$ is transitive, def. $W$ is transitive iff. $(x\in W\wedge y\in x)\to y\in W$; to see more, look at Relativising Axioms.

Remember that what we want to show when relativising is that for $\varphi$ and ${\varphi }_W$ it holds that:$((W,ϵ)\models \varphi )\iff {\varphi }_W$Comulative Hierarchy: we denote, as in Wikipedia, with $V_{\alpha }$ for an ordinal $\alpha$ the set defined by recursion as: (K. writes it as $R(\alpha )$)

• $V_0:=\varnothing$ 

• for an ordinal $\beta$: $V_{\beta +1}:=\mathcal{P}(V_{\beta })$

• for any limit ordinal $\lambda$: $V_{\lambda }:={\bigcup }_{\beta <\lambda }{V}_{\beta }$

Similarly, one can define it as:

• $V_{\alpha }:=\bigcup \{\mathcal{P}\{V_{\beta }|\beta \in \alpha \}\}$

Remember that an ordinals are the sets generated by the usual operations of $S$, successor, addition, multiplication… A limit ordinal is an ordinal that is not 0 nor a successo ordinal, e.g. remember that $\omega$ has no predecessor, on the other hand, obviously $\omega +1$ has a predecessor.

The image we get is the usual $V$ since for any ordinal $\alpha$ we have $V_{\alpha }\subset V_{\alpha +1}$.

Definition: we say that $A$ is grounded if there is an ordinal $\alpha$ s.t. $A\in V_{\alpha }$($\iff A\subseteq V_{\alpha +1}$). If $A$ is grounded, let $rk(A)$ be the least $\alpha$ s.t. $A\subset V_{\alpha }$. (Ax. of Foundation assumes that all sets are grounded.)

Note: if $A\in B$ then $rk(A)<rk(B)$

Axiom of Foundation: there are three equivalent statements:

• every non empty set $A$ has a member $m$ s.t. $m\cap A=\varnothing$

• there is no function s.t. $dom(f)=\omega \wedge {\forall }_{n\in \omega }f(n+1)\in f(n)$

• all sets are grounded

Absoluteness Defined

Definition: we say a formula $\varphi$ is absolute for $W$ if $FV(\varphi )\subseteq \{x_1,...,x_n\}$ and ${\forall }_{x_1\in W}...{\forall }_{x_n\in W}({\varphi }_w(x_1,....,x_n)\leftrightarrow \varphi (x_1,...,x_n))$Where $FV(\varphi )$ denotes the set of free variables of $\varphi$ and is inductively defined as follows:

• $FV(P(t_1,...,t_n)):=var(P(t_1,...t_n))$

• $FV(\neg \varphi ):=FV(\varphi )$

• $FV((\varphi \to \psi )):=FV(\varphi )\cup FV(\psi )$

• $FV({\forall }_x\varphi ):=FV(\varphi )\setminus \{x\}$ 

$FV$ is a function defined by recursion on the complexity of $\mathcal{L}$-formulae.

These examples of formulae that are absolute for any transitive set $W$:

1. $z=\varnothing$

2. $x\subseteq y$

3. $z=x\cup y$

4. $z=x\cap y$

5. $z=\{x,y\}$

6. $z=(x,y)$

Notice that all of those have no quantifier, then clearly there cannot be any difference in their relativisation and are therefore absolute.

How to Compute

In order to prove that a formula $\varphi$ is absolute there is a simple procedure to follow:

Rewrite $\varphi$ s.t. every subformula is either a formula in ${\mathcal{L}}_{ϵ}$ or another absolute formula for transite sets. Remember that $(\neg \varphi {)}_W=\neg {\varphi }_W$  and  $(\varphi \wedge \psi {)}_W={\varphi }_W\wedge {\psi }_W$, therefore any other sentence made by logical connectives and absolute formulas will be absolute too. Concrete examples can be found in Relativising Axioms.

Non-Absolute Formulae in Transitive Sets

These formulae require the set $W$ to be not transitive in order to be equivalent in both their forms, namely $\varphi$ and ${\varphi }_W$. You can find complete proofs in the uploaded PDF “Relativizing and absoluteness”.

Let’s start with an example:

1. $\mathcal{P}(x)=y$ 

Normally it holds that $\mathcal{P}(2)\ne 3$, since $2:=\{0,1\}=\{\varnothing ,\{\varnothing \}\}$, $\mathcal{P}(2)=\{\varnothing ,\{\varnothing \},\{\{\varnothing \}\},\{\varnothing ,\{\varnothing \}\}\}\ne \{\varnothing ,\{\varnothing \},\{\varnothing ,\{\varnothing \}\}\}=:3$, 

Consider $(\omega ,\in )$ since the only difference lays in the fact that $\{\{\varnothing \}\}\in \mathcal{P}(2)$ and it isn’t in 3; but since $\{\{\varnothing \}\}\notin \omega$, since it doesn’t corresponds to any number then $(\omega ,\in )\models \mathcal{P}(2)=3$. To conclude: $(\mathcal{P}(2)=3{)}_{\omega }\wedge \neg (\mathcal{P}(2)=3)$.

2)  $x\times y=z$

Let’s try to prove it absolute for transitive sets: the first step is writing it in ${\mathcal{L}}_{ϵ}$, so: $x\times y:=\{(a,b)|a\in x\wedge b\in y\}$, at first sight, one might think it as being absolute since $(a,b)$, $a\in x$, $\varphi \wedge \psi$ are all absolute. But remember, in order to say that a formula is absoltute, we need $(a,b)\in W$, though this is not secured by the assumptions; even if both $a$ and $b$ were in $W$ (which, I suppose, is not secured either) then it must not hold that $(a,b)\in W$. Similarly consider $z=W\cap (x\times y)$, it might be (or not) that $z\in W$, then depending on $W$, it might be that $(W,\in )\models z=x\times y$.

Relativising Axioms

When we try to relativise an axiom $\varphi$ to a set $W$ we claim: $(W,\in )\models \varphi \iff {\varphi }_W$Some examples: 

The Axiom of Extentionality is defined as: ${\forall }_x{\forall }_y({\forall }_z(z\in x\leftrightarrow z\in y)\to x=y)$, I start by the claim:

$(W,\in )\models ({\forall }_x{\forall }_y({\forall }_z(z\in x\leftrightarrow z\in y)\to x=y){)}_W\iff {\forall }_{x\in W}{\forall }_{y\in W}({\forall }_{z\in W}(z\in x\leftrightarrow z\in y)\to x=y)$

Now consider $W=\{\varnothing ,\{\{\varnothing \}\}\}$ then $(W,\in )/\models$ Ax. Ext., since if we pick $x=\varnothing$, $y=\{\{\varnothing \}\}$, since they don’t contain any of the elements in $W$ they satisfy the antecedent and should then be equal.

Lemma: $W$ is transitive then $(W,\in )\models$ Ax. Ext.

Proof.: Let $W$ be transitive and $x,y\in W$ with $x\ne y$. Then there some set $z$ with

$z\in x\nleftrightarrow z\in y$. Without loss of generality assume $z\in x$ and $z\notin y$. Then

$z\in W$ by transitivity.

Axiom of Separation

Lemma: (K. 2.6) If ${\forall }_{z\in M}(\mathcal{P}(z)\subset M)$ then $M\models ($Ax. of Sep.${)}_M$.

Proved in K. $\square$ 

The Axiom of Emptyset is defined as: ${\exists }_x(x=\varnothing )$, let’s start with the first step for proving it absolute, rewrite it in ${\mathcal{L}}_{ϵ}$, so: ${\exists }_x{\forall }_y(x\in y\leftrightarrow y\ne y)$. Now let’s relativise it to $W$ and derive the conclusions: ${\exists }_{x\in W}{\forall }_{y\in W}(x\in y\leftrightarrow y\ne y)\iff {\exists }_{x\in W}(x\cap W=\varnothing )$ (see K. 115). Let’s find some $W$ for which the the Ax. Emp. doesn’t hold: let $W=\{\{\varnothing \}\}$ then $(W,\in )\models$ Ax. Emp. even though $\varnothing \notin W$.

Prop.: if $W$ is not empty then $(W,\in )\models$ Ax. Empt.

Proof.: By Ax. Foundation there is $t\in W$ with $y\cap W=\varnothing$.

The Axiom of Foundation is defined as: ${\forall }_x(x\ne \varnothing \to {\exists }_y(y\in x\wedge x\cap y=\varnothing ))$ I relativise it: ${\forall }_{x\in W}(x\ne \varnothing \to {\exists }_{y\in W}(y\in x\wedge x\cap y=\varnothing ))$, using the absoluteness of $x=\varnothing$ and $z=x\cap y$ proved above. Let $x\in W\wedge x\ne \varnothing$, then by Ax. Foundation ${\exists }_{y\in x}(x\cap y=\varnothing )$ but then by transitivity of $W$: $y\in W$.

Finally we get:

Lemma: if $W$ is transitive and non-empty then $(W,\in )$ satisfies the Axioms of Exstentionality, Emptyset and Foundation.

The Proof of $(V_{\alpha },ϵ)\models ZFC$

Lemma: For a limit ordinal $\alpha$, $(V_{\alpha },\in )$ satisfies the axioms of pairing, union, powerset and the axiom scheme of separation. If additionally $\alpha >\omega$ then $(V_{\alpha },\in )$ also satisfies the Axiom of Infinity

Some needed definitions first: an ordinal $\lambda$ is a limit ordinal if there is an ordinal less than $\lambda$, and whenever $\beta$ is an ordinal less than $\lambda$, then there exists an ordinal $\gamma$ such that $\beta <\gamma <\lambda$. For example, $\omega$ is the smallest ordinal greater than every natural number. All ordinals you build starting from $\omega$ are countable, though, even if their cardinality is the same, they can differ. We denote with ${\omega }_1$ the first uncountable ordinal and the sequence: ${\omega }_1,{\omega }_2,...,{\omega }_{\omega },{\omega }_{\omega +1},...$ is (strictly) increasing in cardinality. And then $V_{\alpha }$ is defined as the set containing all ordinals smaller than $\alpha$. Let’s start with the first three axioms:

The Axiom of Paring relativised to $V_{\alpha }$: $({\forall }_x{\forall }_y{\exists }_{z}z=\{x,y\}{)}_{V_{\alpha }}$ since, as we saw, $z=\{a,b\}$ is absolute for every set, we can just rewrite it, so: $({\forall }_{x\in V_{\alpha }}{\forall }_{y\in V_{\alpha }}{\exists }_{z\in V_{\alpha }}z=\{x,y\}{)}_{V_{\alpha }}$, left to show is just that $z=\{x,y\}\in V_{\alpha }$ which holds since: $rk(\{x,y\})=max\{rk(x),rk(y)\}+1<\alpha \Rightarrow \{x,y\}\in V_{\alpha }$. These rules come from the definition of $V_{\alpha }$.

The Axiom of Union relativised to $V_{\alpha }$: $({\forall }_x{\exists }_{z}z=\bigcup x{)}_{V_{\alpha }}$ which is equivalent to  ${\forall }_{x\in V_{\alpha }}{\exists }_{z\in V_{\alpha }}z=\bigcup x$, since $a=\bigcup b$ is absolute on any set, then left to show is only that $z\in V_{\alpha }$, which holds since $rk(\bigcup x)\le rk(x)+1<\alpha$ so $\bigcup x\in V_{\alpha }$.

The Axiom of Powerset relativised to $V_{\alpha }$: $({\forall }_x{\exists }_y{\forall }_z(z\in y\leftrightarrow z\subseteq x){)}_{V_{\alpha }}$ which is equivalent to ${\forall }_{x\in V_{\alpha }}{\exists }_{y\in V_{\alpha }}{\forall }_{z\in V_{\alpha }}(z\in y\leftrightarrow z\subseteq x)$ since $z\subseteq x$ is absolute for any set. And since $rk(\mathcal{P}(x))=rk(x)+1$ so $x\in V_{\alpha }\Rightarrow \mathcal{P}(x)\in V_{\alpha }$.

The Axiom of Infinity relativised to $V_{\alpha }$: $({\exists }_x(\varnothing \in x\wedge {\forall }_y(y\in x\to \{y\}\cup y\in x)){)}_{V_{\alpha }}$ and since both $\varnothing \in x$ and $\{y\}\cup y\in x$ are absolute formulae for all sets, then it is equivalent to: ${\exists }_{x\in V_{\alpha }}(\varnothing \in x\wedge {\forall }_{y\in V_{\alpha }}(y\in x\to \{y\}\cup y\in x))$. Then $x\in V_{\alpha }$, $\varnothing \in x$, ${\forall }_{y}y\in x\to \{y\}\cup y\in x$ so in particular that holds for any $y$ in $V_{\alpha }$.

3rd Lecture

Definition: (ext.) $trcl(x):=\{a|a{\in }^{\ast }x\}$ where $a{\in }^{\ast }x$ means that there is a $\in$-path from $a$ to $x$.

Note: $trcl(x)$ is the smallest transitive $y$ s.t. $x\subseteq y$. Also $trcl(x\cup y)=trcl(x)\cup trcl(y)$ holds.

Definition: a cardinal $k$ is inacc. iff it isn’t a result of cardinal arithmetic from smaller cardinals.

Definition: $cf(k):=\min \{|A|:A\subseteq k\wedge {\forall }_{\beta <k}{\exists }_{\alpha \in A}\beta \le \alpha \}$, min size needed to be unbounded

Definition: a cardinal $k$ is regular iff $cf(k)=k$ else it’s singular.

Example: (ext.) Consider $\kappa ={\aleph }_{\omega }$, that is the first cardinal number which is larger than ${\aleph }_n$ for every finite n. We have that $⟨{\aleph }_n:n\in \omega ⟩$ is a cofinal sequence, as every ordinal below $\kappa$ is smaller than some ${\aleph }_n$, but this is merely a countable set while $\kappa$ is very much uncountable, so $cf({\aleph }_{\omega })=\omega$ hence ${\aleph }_{\omega }$ is singular.

For computing $cf(k)$ we should consider the following simple rules (ext.):

• $cf({\aleph }_0)={\aleph }_0$

• $cf({\aleph }_{\alpha +1})={\aleph }_{\alpha +1}$, hence all cardinals ${\aleph }_{\beta }$, for $\beta$ a successor ordinal, are regular

• $cf({\aleph }_{\lambda })={\sup }_{\alpha <\lambda }{\aleph }_{\alpha }=cf(\lambda )$ for $\lambda$ a limit ordinal, e.g. $cf({\aleph }_{{\aleph }_3+{\omega }^3})=cf({\aleph }_3+{\omega }^3)=\omega$ 

Definition: (K. IV.6.1) For any infinite cardinal $k$, $H(k):=\{x:|trcl(x)|<k\}$, we write $V_k$ for $H(k)$.

Lemma: (K. IV.6.4) For any infinite $k$ the following hold:

• $H(k)$ is transitive

• $x\in H(k)\to {\bigcup }_x\in H(k)$

• $x,y\in H(k)\to \{x,y\}\in H(k)$

• $(x\in H(k)\wedge y\subset x)\to y\in H(k)$

• $k$ is regular $\to {\forall }_x(x\in H(k)\leftrightarrow x\subset H(k)\wedge |x|<k)$

Lemma: (K. IV.6.3) For $k$ regular, $H(k)=R(k)\leftrightarrow (k=\omega \vee k$ is strongly inacc.$)$

Lemma: (K. IV.6.2) For any infinite $k$, $H(k)\subset R(k)$

Therefore all that we have proved in the last lecture on $V_{\alpha }$ it must hold for $V_k$ too, hence:

Theorem: For an inaccessible cardinal $k$, $(V_k,\in )\models ZFC$.

(Also in K. IV.6.5 $(k$ reg. $\wedge$  $k>\omega )\to H(k)\models ZFC-P$)

Now we want this model to be countable, though it is not, since $k$ is an inaccessible cardinal.

What we proved the last lecture was that for every limit ordinal $\alpha >\omega$ and $(V_{\alpha },\in )\models ZFC$ except for Ax. of Replacement.

Lemma: if $k$ is inacc. then $x\in V_k\to |x|<k$

Note: this just trivially follows from the definition above of $H(k)$

Lemma: if $k$ is regular $x\in V_k\wedge |x|<k\to x\in V_k$ MISTAKE

The Ax. of Replacement  is a axiom schema, take a $\varphi \in {\mathcal{L}}_{ϵ}$ with $x,y\in FV(\varphi )$. We have to show that $(func(\{z:\varphi \})\to {\forall }_x{\exists }_y(y=\{z:\varphi {\}}^{\prime \prime }{)}_{V_k}$ where $func(\{z:\varphi \})$ denotes that there the class $\{z:\varphi \}$ is a function. ==IDK $\{z:\varphi {\}}^{\prime \prime }$.==

First split the two parts $(func(\{z:\varphi \}){)}_{V_k}\to ({\forall }_x{\exists }_{y}y=\{z:\varphi {\}}^{\prime \prime }{)}_{V_k}$, then start with the first part  $({\forall }_z(\varphi (z)\to {\exists }_u{\exists }_v((z=(u,v)\wedge \forall v^{\prime }(\varphi ((u,v^{\prime })\to v=v^{\prime })){)}_{V_k}$, (just by espanding $func$) and then, by relativisation: ${\forall }_{z\in V_k}(\varphi (z)\to {\exists }_{u\in V_k}{\exists }_{v\in V_k}((z=(u,v)\wedge {\forall }_{v^{\prime }\in V_k}(\varphi ((u,v^{\prime })\to v=v^{\prime })$.

We can see that it holds for $\{z|{\varphi }_{V_k}(z)\wedge z\in V_k\}$, which therefore is a function, though we still have to get to $\{z:\varphi \}$. Define: $f:=\{z:{\varphi }_{V_k}\wedge z\in V_k\}$ and apply the Ax. of Rep. to $f$ and get ${\forall }_x{\exists }_z(z=f^{\prime \prime }x)$. Let $x\in V_k$ be arbitrary and $y=f^{\prime \prime }(x)$. We need to show (i) $y\in V_k$ and (ii) $(y=\{z:{\varphi }^{\prime \prime }x\}{)}_{V_k}$.

• (i) Clearly $y\le V_k$. As $x\in V_k$ by Prop $|x|\le k$ and $|y|\le |x|<k$, thus by Prop. 2 $y\in V_k$.

• (ii) $(y=\{z_{\varphi }{\}}^{\prime \prime }x{)}_{V_k}$ is ${\forall }_{v\in V_k}(v\in y\leftrightarrow {\exists }_{u\in z}\varphi ((u,v)){)}_{V_k}$, as $x,y\in V_k(v\in y\leftrightarrow {\exists }_{u\in x}{\varphi }_{V_k}((u,v))$ This is true as it is just expressing $y=f^{\prime \prime }x$.

$QED$

Alternatively, from Kunen:

Definition: we say $Si(k)$, $k$ is strongly inacc., iff those are satisfied

• $k>{\aleph }_0$

• $k$ is inacc.

• $\alpha <k\to 2^{\alpha }<k$ 

Theorem: (IV.6.6) for $k$ reg. and $k>\omega$ tfae:

• $H(k)\models ZFC$

• $H(k)=R(k)$

• $Si(k)$

Lemma: (K. IV.6.8) $Si(k)$ then "$Si(\alpha )$" is absolute for $H(k)$.

Some Definitions

Def. let $W\subseteq Z$  be set or class terms and $\varphi \in {\mathcal{L}}_{ϵ}$, with $FV(\varphi )=\{x_1,...,x_n\}$. We say $\varphi$ is absolute between $W$ and $Z$ if ${\forall }_{x_1},...,{\forall }_{x_n}({\varphi }_W(x_1,...,x_n)\leftrightarrow {\varphi }_Z(x_1,...,x_n))$.

Before we compared a set with $V$ only, namely the universe of sets, the notion defined here is a weaker version. Even weaker are the two following terms:

Downward absolute if: ${\forall }_{x_1},...,{\forall }_{x_n}({\varphi }_W(x_1,...,x_n)\to {\varphi }_Z(x_1,..,x_n))$

Upward absolute if: ${\forall }_{x_1},...,{\forall }_{x_n}({\varphi }_Z(x_1,...,x_n)\to {\varphi }_W(x_1,...,x_n))$ 

We say that $\mathcal{N}$ is a substructure of $\mathcal{M}$ if $\mathcal{N}\subseteq \mathcal{M}$ and the interpretation function $\mathcal{H}$ of $\mathcal{N}$ is the restriction of the interpretation function for $\mathcal{M}$. 

For $\varphi \in \mathcal{L}$, $FV(\varphi )=\{x_1,...,x_n\}$, say $\mathcal{N}{\le }_{\varphi }\mathcal{M}$ if ${\forall }_{x_1},...{\forall }_{x_n}(\mathcal{N}\models \varphi (a_1,...a_n)\iff \mathcal{M}\models \varphi (a_1,...,a_n))$

Definition $\mathcal{N}\le \mathcal{M}$ or, in words, $\mathcal{N}$ is an elementary substructure of $\mathcal{M}$ for all $\varphi \in \mathcal{L}$ it holds that $\mathcal{N}{\le }_{\varphi }\mathcal{M}$, we also say $(W,\in )\le (Z,\in )$ if all $\varphi \in {\mathcal{L}}_{ϵ}$ are absolute betweeen $W,Z$.

Definition A list of formula ${\varphi }_0,{\varphi }_1,...$ is subfor. closed if all subfor. of a for. on the list is on the list.

Lemma (Traski-Vaught Test K. IV.7.3) Let ${\varphi }_1,...,{\varphi }_n$ be a subformula closed list, $M\subset N$, tfae:

• ${\varphi }_1,...,{\varphi }_n$ are absolute for $M,N$

• Whenever ${\varphi }_i$ of the form ${\exists }_x{\varphi }_j(x,y_1,...,y_l)$, ${\forall }_{y_1,...,y_l\in M}({\exists }_{x\in N}{\varphi }_j^N(x,y_1,...,y_l)\to {\exists }_{x\in M}{\varphi }_j^N(x,y_1,...,y_l))$Note: when ${\varphi }_i$ has some other shape, then it is trivial, since we are in a subformula closed list, the only other case is when ${\varphi }_i$ has no quantifier, and is therefore trivially absolute on all sets.

Proof. (i) $\Rightarrow$ (ii) is clear. Fix  and assume , i.e . Then by absoluteness of , we get  so .

(ii) $\Rightarrow$ (i) By indiction on leght of ${\varphi }_i$, so we assume that (IH) is not absolutely hold for subformulae.

• ${\varphi }_i$ atomic - by definition of absolute if its atomic $x\in y$ or $x=y$, they’re defined as $(x\in y{)}_W/(x\in y{)}_Z$.

• ${\varphi }_i$= ${\varphi }_j\wedge {\varphi }_k$ by IH ${\varphi }_1,{\varphi }_j,{\varphi }_k$ are absolute so by def of relativisation ${\varphi }_i$ is absolute.

• Similarly for ${\varphi }_i=\neg {\varphi }_j$

Now the interesting part:

${\varphi }_i={\exists }_x{\varphi }_j(x,\vec{y})$, fix $\vec{y}\in W$ then ${\varphi }_i(\vec{y}{)}_W$ \leftrightarrow $\exists x\in W{\varphi }_j(x,\vec{y}{)}_W$ $\leftrightarrow (IH)\exists x\in W{\varphi }_j(x{\vec{y}}_Z$ $\leftrightarrow {\exists }_{x\in Z}{\varphi }_j(x,\vec{y}{)}_Z$. All is then equivalent to ${\varphi }_i(\vec{y}{)}_Z$.

$QED.$  understand proof; should I?

Def. for $\varphi \in {\mathcal{L}}_{ϵ}$ if $FV(\varphi )=\varnothing$, then we say $\varphi \in {\Delta }_0$ namely if $\varphi$ has bounded variables only:

• $x\in y$, $y=x\in {\Delta }_0$

• $\varphi ,\psi \in {\Delta }_0$ then $\neg \varphi$, $\varphi \wedge \psi \in {\Delta }_0$

• if $\varphi \in {\Delta }_0$ then $({\exists }_x\varphi (x))\in {\Delta }_0$ 

Lemma let $W$ be a transitive set, then any ${\Delta }_0$ formula is absolute for $W$.

Proof. By ind. on lenght of for., and with the former lemma, we need to show that if $\varphi$ is of the form ${\exists }_x(x\in a\wedge \psi (x,\vec{y},a))$ then \forall_{a \in W} \forall_\vec{y} \in W (\exists_x(x \in a \land \psi(x, \vec{y},a))\rightarrow \exists_{x\in W}(x \in a \land \psi (x, \vec{y},a)))_W

So let a, $\vec{y}\in W$ and suppose ${\exists }_x\in W\psi (x,\vec{y},a)$ and $\psi$ is ${\Delta }_0$ as $\varphi$ is ${\Delta }_0$ and of leght less then $\varphi$ so by IH $\varphi$ is absolute. for $W$ i.e. $\psi (x,\vec{y},a)\to \psi (x,y,a{)}_W$. Why is there some $x$ in $W$? Further as a in $W$, a $\le E$ so $x\in a\leftrightarrow x\in W\cap a$ then $\exists x\in a\psi (x,\vec{y},a)\Rightarrow {\exists }_{x\in W}(x\in a\wedge \psi (\vec{x},y,a))$ since these two are already relativesed to $W$, then it implies $(e\in a\wedge \psi (x,\vec{y},a){)}_W$.

4th Lecture

Recap from ext.

Reflection Theorem from Kunen

We need here to instantiate the Löwenheim-Skolem theorem in order to “find a set $M$ s.t. every formula is absolute for $M$. In particular, if $\varphi$ is a sentence, then ${\varphi }^M\leftrightarrow \varphi$, so if $\varphi$ is an axiom of $ZFC$, ${\varphi }^M$ will be true. Actually, becasue of the problem (Gödel) discussed above, if we work within $ZFC$ we can only prove the existence of an $M$ for which an arbitrarily prescribed finite list of formulae are absolute.” (K. p.135) This restriction though still allows us to find a model for any finite set of axioms and no more than a finite set of axioms is what constitutes any kind of proof. Thanks to the Tarski-Vaught test presented in the previous lecture we can now easily tell whether a set of formulae is absolute for $M$, let’s paste it here too:

Lemma (Traski-Vaught Test (2) K. IV.7.3) Let ${\varphi }_1,...,{\varphi }_n$ be a subformula closed list, $M\subset N$, tfae:

• ${\varphi }_1,...,{\varphi }_n$ are absolute for $M,N$

• Whenever ${\varphi }_i$ of the form ${\exists }_x{\varphi }_j(x,y_1,...,y_l)$, ${\forall }_{y_1,...,y_l\in M}({\exists }_{x\in N}{\varphi }_j^N(x,y_1,...,y_l)\to {\exists }_{x\in M}{\varphi }_j^N(x,y_1,...,y_l))$Note: this method allows us to consider onlu truth of formuale in the larger class, $N$. In our first application, we take $N=V$ and tru to find a set, $M=R(\beta )$ s.t. ${\varphi }_1,...,{\varphi }_n$ are abs. for $M$:

Reflection Theorem: for a(ny) list of formuale ${\varphi }_1,...,{\varphi }_n$ $ZF⊢{\forall }_{\alpha }{\exists }_{\beta >\alpha }({\varphi }_1,...,{\varphi }_n\text{ are absolute for }R(\beta ))$Kunen first states a more general version of the theorem and proves that one, we didn’t see that version in class though. The set of formulae here is clearly finite, though “Platonistically, we could carry out the arguments of 7.3-7.6 with all formulas simultaneously and show that ${\forall }_{\alpha }{\exists }_{\beta >\alpha }({\bigwedge }_{i\in \omega }{\varphi }_i^{R(\beta )})$ where ${\varphi }_i$ list all axioms of $ZFC$. But this argument cannot be formalised within $ZFC$ […] given axioms ${\varphi }_1,...,{\varphi }_n$ of $ZFC$, the first $R(\beta )$ which is a model of ${\bigwedge }_{i=1}^n{\varphi }_i$ is not a model of $ZFC$, and the proof of Cor. 7.7 explicitly procuces a theorem of $ZFC$, namely ${\exists }_{\alpha }({\bigwedge }_{i=1}^n{\varphi }_i^{R(\beta )})$, which is false in this $R(\beta )$.” (K. p.139)

Downward Löwenheim-Skolem Theorem from ext.

Theorem: (Down. Lö-Sk) for inf. $\mathcal{M}$ and inf. $|M|\ge k\ge |\mathcal{L}|$ then exists $\mathcal{N}$ s.t. $|N|=k$, $\mathcal{N}\subseteq M$.

Proof. easily divisible in three steps:

1. For each $\varphi (y,x_1,...,x_n)\in \mathcal{L}$ the $AC$ implies the existence of a function $f_{\varphi }:M^n\to M$ s.t. for all $a_1,...,a_n\in M$ either $\mathcal{M}\models \varphi (f_{\varphi }(a_1,...,a_n),a_1,...,a_n)$ or $\mathcal{M}\models \neg {\exists }_y\varphi (y,a_1,...,a_n)$.

2. From the family of functions $f_{\varphi }$ we can define $F$ on $\mathcal{P}(M)$ as: $F(A)=\{f_{\varphi }(a_1,...,a_n)\in M|\varphi \in \sigma \wedge a_1,...,a_n\in A\}$ for any $A\subseteq M$.

3. Call $F_{\omega }$ the iteration of $F$ countably many times. Now for an arbitrary $k$ pick one $A\subseteq M$ s.t. $|A|=k$, define $N:=F_{\omega }(A)$ (3.1), one can see that also $|N|=k$ (3.2), also $\mathcal{N}$ is an elem. substr. of $\mathcal{M}$ by the Tarsky-Vaught Test (3.3).

T.-V. test: $\mathcal{N}⪯\mathcal{M}\iff {\forall }_{\varphi (c,y_1,...,y_n)}{\forall }_{b_1,...,b_n\in N}\mathcal{M}\models {\exists }_x\varphi (x,b_1,...,b_n)\to {\exists }_{a\in N}\mathcal{M}\models \varphi (a,b_1,...,b_n)$.

We instantiate the Down. Lö-Sk Theorem in the following theorem:

Theorem: (K. IV.7.8) for a structure $\mathcal{M}$ and a list of formulae ${\varphi }_1,...,{\varphi }_n$ then:${\forall }_{X\subset M}{\exists }_{A}X\subset A\subset M\wedge ({\varphi }_1,..,{\varphi }_n\text{ are absolute for }A,M)\wedge |A|\le \max \{\omega ,|X|\}$Though this is not really what we did in class and I’m not sure about this yet. See the next lecture

Messy Lecture Notes

**Downward Löwenheim-Skolem Theorem

Theorem: Let $\mathcal{M}$ be an infinite $\mathcal{L}$-structure, fix a cardinal $k$ with $max(|\mathcal{L}|,{\aleph }_0)\le k\le |M|$ and let $S\subseteq M$ with $|S|\le k$. Then there is an $\mathcal{N}\le \mathcal{M}$ s.t. $S\subseteq N$ and $|N|=k$.

Proof. we prove this for $\mathcal{L}={\mathcal{L}}_{ϵ}$ and f-models. Fix M an infinite set and $k\le |M|$ an infinite cardinal.

possiamo usare il teorema per prendere una countable substructure of ZFC o qualcosa di più complesso, è quello per cui ci serve questo teorema. Ora continuo con la dimostrazione.

and $S\le Mqith$|S| \le k. (Ma noi vogliamo che alla fine S abbia esattamente la dimensione di k. Iniziamo con S perche tutto quello che sta in S allora sta in N, quindi cerchiamo priam di lavorare con S, poi vediamo). If $|S|<k,let{S}^{\prime }\le MwithS\le S^{\prime }and|S^{\prime }|=k.SonowweusethepreaviouslemmatobuildupN\subseteq Mwith(N,\text{psilon})\le (M,ϵ),clearalistofallformiulaein$\mathcal{L}\epsilon$issubformulaclosed.Let$R$beawellorderingonM(byaxiomofchoice).Wedefineanyexistensialformula(thosethatstartwith{\exists }_x)namely$\phi = \exists_x \psi$.Let{n}_{\varphi }be|FV(\varphi )|.WedefineaSkolemfunction$f\phi :M^{n_\phi} \rightarrow M$asfollowsfor$\vec{y} \in M^{n_\phi}, if $(M,ϵ)\models {\exists }_x\psi (x\vec{y})$. now let $f_{\varphi }(\vec{y})$ by R-least in M s.t. (M, \epsilon) \models \psi(f_\phi(\vec{y}, \vec{y}) if $(M,ϵ)/\models {\exists }_x\psi (c,\vec{y})$ set f_\psi(\vec{y})=0. Now set N_0 = S’ and define by recursion $N_{i+1}=N_i\cup \{f_{\varphi }^{\prime \prime }{N}_i^{n_{\varphi }}|\varphi \in {\mathcal{L}}_{ϵ}s.t\varphi {\exists }_x\psi$ for some $\psi \}$. Set $N={\bigcup }_{i\in W}{N}_i$.

Claim $|N|=k$.

clearly $|N|\ge k$ as $|N_0|=k$.

|N_| \le |N_0| \oplus (| N_o^{n_\phi}| \oper \aleph_0) \le k \oplus k (k che moltiplica k per n_\phi volte) Heisenberg theorem says that these make no difference

quindi alla moltiplicazione alla fine moltiplichiamo anche \aleph_0, la cardinalita di tutto questo, appunto per heisenberg theorem è proprio k, non aumenta, resta uguale.

similarly |N_i| = |N_0| = k, thus |N| \le |N_0| \oplus |N_1|. \oplus…

Claim 2 (N, \epsilon) \le (M, \epsilon)

By lemma (that we proved the last lecture) we just need to show that. ${\forall }_{y_1}...{\forall }_{y_{n_{\varphi }}\in N}({\exists }_{x\in M}\psi (x,\vec{y}{)}_M\to {\exists }_{x\in N}\psi (x,\vec{y}{)}_N)$. BY induction on the leght of formulae we assume that \psi is absolute for M and N, then let $\vec{y}\in N$ and assume ${\exists }_{x\in M}\psi (x,\vec{y}{)}_M$. Then there must be some $i$ s.t. vec{y} \in N_i^{n_\phi}. Thus $f_{\varphi }(\vec{y})\in N_{i+i}\subseteq N$. So $\psi (f_{\varphi }(\vec{y}),\vec{y}{)}_M$ and by IH $\psi (f_{\varphi }(\vec{y}),\vec{y}{)}_N$. Thus ${\exists }_{x\in N}\psi (x,\vec{y}{)}_N$. 

$Q.E.D.$ check proof

Such $\mathcal{N}$ is called a Skolem Hull of $\mathcal{M}$.

Now consider $M=V_{\lambda }$, $\lambda$ is inaccessible, $S=\varnothing$,  $k={\aleph }_0$.

Def. Let \mathcal{M} be an \mathcal{L} structure X \subseteq M^n is definable in \mathcal{M} iff there is an \mathcal{L}-formula \phi with n free varibales s.t. for a_1, … a_n \in M. \mathcal{M} \models \phi(a_1, …, a_n) \Leftrightarrow (a_1, …, a_n) \in X. So consider the case in which X \subseteq and X is a sigleton {a}. e.g. {\emptyset} is definable in V_\lambda.

Aby hereditarily finite set is definable in V_k, \omega can be defined, but also \omega +1, \omega + \omega, \omega^\omega and also \omega_1= \alpeh_1 but also \omega_2 and also \aleph_\omega, these can all be defined. We have very much countable ordinals and some uncountable. Though we cant define all countable ordinal, otherwise… una formual definisce una sola cosa, abbiamo countable ordinals quindi di quelle prima omega prima di omega 1 ne avremo tanti, a tanti ma non abbastanza per arrivare ad \omega_1 per il fatto che quello è uncountable ed al massimo possiamo definire countable many things, e quindi countably many formulas e quindi di tutte quelle omega che ho scritto ne abbiamo definito un ammount finito anche se \omega_1 non è countable. Quindi di fatto quello che abbiamo è una linea di countable models poi un saltino e dopo abbiamo \omega_1.

La tecnica che abbiamo usato ora grazie al Loewenheim.sk. th. è un metodo carino, parti da un set (presumo N) e poi vai avanti. Ma non è un metodo perfetto, ce ne serve uno migliore. quel teorema ad esempio non funziona se anziche noi anziche iniziare con N avessimo iniziato con V, cosa non funziona se facciamio cosi? Axiom of choice non dice che possiamo avere un welll ordering on V, cosa che abbiamo imposto per M invece. Un altro problema invece è che… boh non ho ben capito. Ok quindi boh mi ha guardato dicendo eh voi filosofi, e boh on ho capito.

boh check

Montague-Lory Reflection Theorem

Let ${\varphi }_1,...,{\varphi }_n\subset {\mathcal{L}}_{ϵ}$, then $ZFC⊢{\forall }_{\alpha }{\exists }_{\beta <\alpha }(\vec{\varphi }$ are absolute for $V_{\beta })$

Notice that (i) this is a theorem schema and (ii) I can pick $\vec{\varphi }$ to be all axioms of $ZFC$ (not finite!!) then $ZFC⊢{\forall }_{\alpha }{\exists }_{\beta <\alpha }(\bigwedge \vec{\varphi }{)}_{V_{\beta }}$.

Proof. ==Online ext.==

From: Wikipedia:

A naive version: “for any property of $V$ we can find a set with the same property”, we should be more careful on what properties we allow.

Gödel: “The universe of all sets is structurally indefinable.”

Thm${}_1$: for any formula $\varphi (x_1,...,x_n)$ with parameters, if $\varphi (x_1,...,x_n)$ is true (in the set-theoretic universe $V$), then there is a level $V_{\alpha }$ of the cumulative hierarchy such that $V_{\alpha }\models \varphi (x_1,...,x_n)$.

Thm${}_2$: for any finite number of formulas of $ZFC$ we can find a set $V_{\alpha }$ in the cumulative hierarchy such that all the formulae in the set are absolute for $V_{\alpha }$.

==does it have something to do with it? yt Antonio==

==Watch yt conference 1:42== 

5th Lecture

Mostowski Collapsing Lemma

Definition: we say that a relation $R$ is extensional on $A$ iff:${\forall }_{x,y\in A}{\forall }_{z\in A}(zRx\leftrightarrow zRy)\to x=y$Note: the rel. $\in$, by Ax. of Ext., is ext. on $V$, in fact this is the Identity criterion for sets. (K. III.5.15)

Theorem: For $W$, a rel. $R$ on $W$ ext., exists a unique tran. set $M$ and an isom. $\pi :(W,R)\cong (M,ϵ)$.

Then we notice do the two following passages:

Theorem: (K. IV.7.8) for a structure $\mathcal{M}$ and a list of formulae ${\varphi }_1,...,{\varphi }_n$ then:${\forall }_{X\subset M}{\exists }_{A}X\subset A\subset M\wedge ({\varphi }_1,..,{\varphi }_n\text{ are absolute for }A,M)\wedge |A|\le \max \{\omega ,|X|\}$We first pick a subset of $\mathcal{M}$, call it $X$, then we apply the Down Lö-Sk Th. to it and get $A_{(X)}$.

Then we apply the Mostowski Collapsing lemma to each $A_{(X)}$ to obtain a transitive model, all properties will be preserved, so:

Lemma: (K. IV.7.9) There exists a $\pi$ s.t. $\pi :(A,\in )\cong (M,\in )$.

Hence for each formula $\varphi (x_1,...,x_n)$ we have: ${\forall }_{x_1,...,x_n\in A}\varphi (x_1,...,x_n{)}^A\leftrightarrow \varphi (\pi (x_1),...,\pi (x_n){)}^M$.

Corollary: (K. IV.7.10) let $M$ a t.m., for any $X\subset M$ there is an $A_{(X)}$ s.t.  

• $X\subset A$

• ${\bigwedge }_{i=1}^n({\varphi }_i^M\leftrightarrow {\varphi }_i^A)$ 

• $A$ is trans.

• $|A|\le \max (\omega ,|X|)$

Corollary: (K. IV.7.11) let ${\varphi }_1,...,{\varphi }_n$ be axioms extending $ZFC$ then ${\varphi }_1,...,{\varphi }_n⊢{\exists }_A|A|=\omega \wedge A\text{ is trans. }\wedge {\bigwedge }_{i=1}^n{\varphi }_i^A$Thanks to the Down. Lö-Sk Theorem we can conclude that “in $ZFC$ can we can prove the existence of a ctm $\mathcal{M}$ for any desired finite fragment of $ZFC$. By listing enough axioms, we can ensure that all the specific absoluteness results of §3 and §5 hold for $\mathcal{M}$, and that $\mathcal{P}(x{)}^M$ and ${\omega }_{\alpha }^M$ are defined. But these concepts are not abso­lute. ${\omega }_1^M$ is a countable ordinal which $\mathcal{M}$ “thinks” is uncountable; but that just means that there is no function in $\mathcal{M}$ from $\omega$ onto ${\omega }_1^M$. Likewise, ${\mathcal{P}}^M(\omega )=\mathcal{P}(\omega )\cap M$ is really countable, but not by someone living in $\mathcal{M}$. The fact that sets in $\mathcal{M}$ can be really countable but uncountable from the point of view of $\mathcal{M}$ (i.e., “countable” is not absolute) is known as the Skolem Paradox.” (K. p.141)

Forcing

Preface

We have previously proved that we can produce a model of a finite ampunt of axioms of $ZFC$ within $ZFC$. Now we use the method of forcing to produce a model $A_{(X)}$ for any finite list of axioms $X$ of $ZFC+\neg CH$. Such $A$ will be a generic extension of models $M$ for suitably many axioms of $ZFC$. Our claim will be $Con(ZFC)\to Con(ZFC+\neg CH)$, the proof will follow this schema:

1. For contradiction assume $\neg Con(ZFC+\neg CH)$, hence $ZFC+\neg CH⊢\perp$

2. Then there is a finite list of axioms ${\varphi }_1,...,{\varphi }_n\subset ZFC+\neg CH$, s.t. ${\varphi }_1,...,{\varphi }_n⊢\perp$

3. With Forcing we show $ZFC⊢{\exists }_A{\bigwedge }_{i=1}^n{\varphi }_i^A$, hence $ZFC⊢{\exists }_A{\perp }^A$ we just did it!!

4. Hence $ZFC⊢\perp$, hence $Con(ZFC)\to Con(ZFC+\neg CH)$.

Definitions

Definition (K. VII.2.1) A Forcing Poset is a triple $(\mathbb{P},\le ,1)$, where $\mathbb{P}$ is a set, $\le$ is a pre-order on $\mathbb{P}$ (i.e. transitie and reflexive) and $1$ is an element of $\mathbb{P}$ and is the largest element under the ordering, namely ${\forall }_{p\in \mathbb{P}}p\le 1$. All elements of $\mathbb{P}$ are called forcing conditions.

Notation $p\le q$ (said as “p extends q”), also abuse notation using $\mathbb{P}$ to refer to $(\mathbb{P},\le ,1)$.

Note that $1$ ensures that the orderig is connected, 

Note that if $\le$ is a partial order $\Rightarrow 1$ is unique

Notation $\neg (p\perp q)$ (said as ”$p$ and $q$ are compatible”) if ${\exists }_{r\in \mathbb{P}}r\le p\wedge r\le q$, i.e. they have a common extension.

Note that in a diamond all elements are compatible.

Note that in a tree two elements are compatible iff. they belong to the same branch.

Example Consider $(\mathcal{P}(\omega ),\subseteq ,\varnothing )$ as a forcing poset. You have $\varnothing$ on top, then all (infinite) singletons, then, in the second layer you have all sets with two elements, which are connected to the singletons above by inclusion. A the bottom you’ll then find $\omega$, the shape is diamond and therefore all elements are compatible since all can be extended to $\omega$.

Example Let $\mathbb{P}\subseteq \omega$ s.t. $\mathbb{P}|={\aleph }_0$, consider $(\mathbb{P},{\subseteq }^{\ast },\omega )$ with $p{\subseteq }^{\ast }q\iff |p\setminus q|<{\aleph }_0$. Notice then that $p\perp q\iff |p\cap q|<{\aleph }_0$, also notice that there is no least element.

Def. (in relata è un altro esempio ma lo useremo dopo quindi capiscilo bene)

Definition $F_n(I,J)$ for sets $I,J$ is the set of all finite partial functions from $I$ to $J$.

Example Consider $(Fn(I,J),{\subseteq }^{\ast },\varnothing )$ as a forcing poset, where say $dom(p)=A$ ($\subseteq I$ ) and $dom(q)=B$ ($\subseteq A$) then $p{\subseteq }^{\ast }q\iff {\forall }_{i\in A}p(i)=q(i)$ Notice also that if $p$ and $q$ agree on $dom(p)\cap dom(q)$ then we have $p\cup q\in Fn(I,J)$. Also $p\cup q\le p$ and $p\cup q\le q$.

Definition Let $\mathbb{P}$ be a forcing poset, let $D\subseteq \mathbb{P}$, we say $D$ is dense in $\mathbb{P}$ iff ${\forall }_{p\in \mathbb{P}}{\exists }_{q\in D}q\le p$.

Example Let $I$ be infinite and $J\ne \varnothing$, then pick $i\in I$ then define $\{q\in Fn(I,J)|i\in dom(q)\}$. Let $p\in Fn(I,J)$ and define $D_i$ s.t. if $i\in dom(p)$ then $p\in D_i$ else define $q:=p\cup \{(i,j)\}$, for an $j\in J$. Then for any $p\in Fn(I,J)$ we found $q\in D_i$ s.t. and $q\le p$ (for any $i\in I$).

Now define $L:=\{q\in Fn(I,J)|(i,j)\in q\}$, notice that it is not a dense if $|J|\ge 2$, since if we have $j^{\prime }\ne j$, then $p:=\{i,j^{\prime }\}$ ($\in Fn(I,J)$) and $\neg {\exists }_{q\in Fn(I,J)}q\le p$ and $q\in L$.

Notice that if $\mathbb{P}$ has a minimum, i.e. it is diamond shaped, call it $x$, then $\{x\}$ is a dense set.

Definition (K. II.2.4) Let $\mathbb{P}$ be a forcing poset, then $G\subseteq \mathbb{P}$ is a filter on $\mathbb{P}$ iff.

1. $1\in G$

2. ${\forall }_{p,q\in G}{\exists }_{r\in G}r\le q\wedge r\le p$ 

3. ${\forall }_{p\in G}{\forall }_{q\in \mathbb{P}}q\le p\to q\in G$

note if $G\ne \varnothing$ then $3.\to 1.$

Example The model theoretic filter on $I$ is the set theoretic filter on the forcing poset $(\mathcal{I},\subseteq ,I)$.

If $\mathbb{P}$ has a partial order, then 𝟙.

Example $\mathbb{P}=Fn(I,J)$, $I$ infinite, $J\ne \varnothing$, $G$ a filter on $\mathbb{P}$, then any $p,q,\in G$ agree on $dom(p)\cap dom(q)$.

Messy Notes

Also if $Z\le W$ with $R{|}_{Z\times Z}=ϵ{|}_{Z\times Z}$ and for $v\in Z,u\in W$ with $uRv\to u\in Z$. ehm..?

6th Lecture

Definition $r\in \mathbb{P}$ is an atom of $\mathbb{P}$ if there are no $p,q\le r$  s.t. $p\perp q$.

Example

1. $(\mathcal{P}(\omega ),\subseteq ,\omega )$, all elements are atoms

2. If the order is linear, then all elements are atoms

3. A tree that branches at every node is atomless

4. $Fn(I,J)$, $J\ne \varnothing$, $I$ finite has atoms (those that have no trivial extension, namely the functions defined on the whole $I$)

5. If $I$ is infinite and $|J|\ge 2$ then $Fn(I,J)$ is atomless, you can always extend any $f$ to another function defined on a new $i$ s.t. you take two different ways, s.t. $f_1(i)\ne f_2(i)$.

Definition say $G$ is $\mathbb{P}$-gen. over $M$ iff $G$ is a filter on $\mathbb{P}$ and: ${\forall }_{D\subset \mathbb{P}\wedge D\text{ dense}}D\in M\to G\cap D\ne \varnothing$Lemma If $\mathbb{P}\in M$, $M$ c.t.m of $ZFC$, $\mathbb{P}$ atomless and $G$ is $\mathbb{P}$-gen. over $M$, then $G\notin M$.

Example $\mathbb{P}=Fn(I,J)$, $I$ infinite, $J\ne \varnothing$, $G$ a filter on $\mathbb{P}$, then any $p,q,\in G$ agree on $dom(p)\cap dom(q)$. So setting $f_G:={\bigcup }_G$ is a function. $D_i:=\{p\in Fn(I,J)|i\in dom(p)\}$, $D_i$ is dense in $\mathbb{P}$ so if ${\forall }_{i\in I}G\cap D_i\ne \varnothing$ then $f_G:I\to J$.

Existence Lemma (K. VII.2.3) 

Let $M$ be a ctm s.t. $\mathbb{P}\in M$ then ${\forall }_{p\in \mathbb{P}}{\exists }_{G\mathbb{P}\text{-gen. over }M}p\in G$ 

Claim. Let $\{D_n|n\in \omega \}$ be a count. family of dense subset of $\mathbb{P}$, and let $p\in \mathbb{P}$. Then there is a filter $G$ on $\mathbb{P}$ s.t. $p\in G$ and $G\cap D_n\ne \varnothing$ for any $i\in \omega$

Proof. let $\{D_i|i\in \omega \}$ enumerate all dense subsets of $\mathbb{P}$ which are in $M$. Chose a sequence $(q_n{)}_{n\in \omega }$ s.t. $p=q_0\ge q_1\ge q_2\ge ...$  and $q_{n+1}\in D_n$, then notice that $\{q_n|n\in \omega \}$ is a filer, since all elements are compatible.

Definition (K. VII.2.5) $\tau$ is a $\mathbb{P}$-name iff $\tau$ is a relation s.t. ${\forall }_{(\sigma ,p)\in \tau }\sigma$ is a $\mathbb{P}$-name $\wedge p\in \mathbb{P}$.

Also $V^{\mathbb{P}}$ denotes the class of all $\mathbb{P}$-names, defined by recursion as:

1. $\varphi \in V^{\mathbb{P}}\to \{(\varphi ,p),(\varphi ,q)\}\in V^{\mathbb{P}}$ for $p,q\in \mathbb{P}$.

2. $\varphi \in V^{\mathbb{P}}\to \{\{(\varphi ,p),(\varphi ,q)\},p\}\in V^{\mathbb{P}}$ for $p,q\in \mathbb{P}$.

3. $\varphi \in V^{\mathbb{P}}\to \{(\varphi ,1)\}\in V^{\mathbb{P}}$

Note that the ordering isn’t relevant here.

Definition $M$ is a tran. of $ZFC$ s.t. $\mathbb{P}\in M$, then $M^{\mathbb{P}}:=V^{\mathbb{P}}\cap M=\{\tau \in M|(\tau$ is a $\mathbb{P}$-name ${)}_M\}$.

Definition (K. VII.2.7)for $\tau$ a $\mathbb{P}$-name, $G\subset \mathbb{P}$, by rec. $val(\tau ,G):={\tau }_G:=\{val(\sigma ,G)|{\exists }_{p\in G}(\sigma ,p)\in \tau \}$.

Then the generic extension $M[G]:=\{{\tau }_G|\tau \in M^{\mathbb{P}}\}$ for a ctm $M$ s.t. $\mathbb{P}\in M$.

Lemma: (K. after VII.2.9): (i) ${\varnothing }_G=\varnothing$, (ii) $p\in G\to val(\{(\varnothing ,p)\},G)=\{\varnothing \}$ else $=\varnothing$.

Lemma: (Pascal 19.09): for a name $\tau =\{\sigma ,p\}$ we have:

• $p\in G\to \{(\sigma ,p){\}}_G={\sigma }_G$

• $p\notin G\to \{(\sigma ,p){\}}_G=\varnothing$ 

Examples ${\varnothing }_G=\varnothing$, $G$ is a filter then $1\in G$ then say:

• $\tau =\{(\sigma ,1),(\theta ,1)\}$ then ${\tau }_G=(val(\sigma ,G),val(\theta ,G))=\{{\sigma }_G,{\theta }_G\}$.

• $\tau =\{(\{(\varnothing ,p),(\varnothing ,q)\},r)\}$, for $p\in G,q\notin G,r\in G$ so:

1. ${\tau }_G=val(\{(\{(\varnothing ,p),(\varnothing ,q)\},r)\},G)=\{(\{(\varnothing ,p),(\varnothing ,q)\},r){\}}_G$

2. $=\{(\{(\varnothing ,p),(\varnothing ,q)\},r{)}_G\}=\{(\varnothing ,p),(\varnothing ,q){\}}_G=\{\{(\varnothing ,p){\}}_G,\{(\varnothing ,q){\}}_G\}=\{\varnothing ,\varnothing \}=\{\varnothing \}$.

$\tau =\{(\{(\varnothing ,p),(\varnothing ,q)\},r)\}\wedge p\notin G,r\notin G$, then we have ${\tau }_G=\varnothing$ sinec $r\notin G$

$\tau =\{(\{(\varnothing ,p),(\varnothing ,q)\},r)\}\wedge p\notin G,r\in G,q\in G$ then ${\tau }_G=\{\{(\varnothing ,p){\}}_G,\{(\varnothing ,q){\}}_G\}=\{\varnothing ,\varnothing \}=\{\varnothing \}$ ==$\ne \{\{\varnothing \}\}$

7th Lecture

Recall from the previous lecture the following definition: For a $\mathbb{P}$-name $\tau$ and $G\subseteq \mathbb{P}$ define by rec. on $val(\tau ,G):={\tau }_G:=\{{\sigma }_G|{\exists }_{p\in G}(\sigma ,p)\in \tau \}$, we set $M[G]:=\{{\tau }_G|\tau \in M^{\mathbb{P}}\}$.

Lemma 1. For $M[G]$ it holds:

1. $M\subset M[G]$
2. $G\in M[G]$
3. $M[G]$ is countable and transitive
4. $M[G]\models ZFC$
5. $M[G]$ is minimal (for any set $N$ with the above features we have $M[G]\subset N$),

For proving that, we’ll need some definitions and lemmas:

Definition For a set $x$, define by rec. $\check{x}:=\{(\check{y},1)|y\in x\}$, clearly $\check{x}$ is a $\mathbb{P}$-name.

Proof of 1.1.

Lemma (K. VII.2.11) Let $G$ be a filter on $\mathbb{P}$, then:

1. ${\forall }_{x\in M}\check{x}\in M^{\mathbb{P}}$ and ${\check{x}}_G=x$
2. $M\subseteq M[G]$ Proof. 1. $\Rightarrow$ 2. trivial, and for 1. notice that: $\check{x}\in M^{\mathbb{P}}$ by absoluteness of  $\stackrel{ˇ}{}$  and ${\check{x}}_G=x$ by induction as ${\check{x}}_G=\{{\check{y}}_G|y\in x\}$. $\square$ 

Proof of 1.2.

Definition Define $\Gamma :=\{(\check{p},p)|p\in \mathbb{P}\}$, so ${\Gamma }_G=\{{\check{p}}_G|p\in G\}=$ (by 1.1.) $\{p|p\in G\}=G$, so $\Gamma$ must name $G$, ${\Gamma }_G=G$, $\Gamma$ is definable within $M$ and clearly is a $\mathbb{P}$-name. $\square$

Proof of 1.4.

As in Kunen:

Definition: (K. VII.2.16) 

1. $up(\sigma ,\tau )=\{(\sigma ,1),(\tau ,1)\}$

2. $op(\sigma ,\tau )=up(up(\sigma ,\sigma ),up(\sigma ,\tau ))$

Lemma: (K. VII.2.17) if $\sigma ,\tau \in M^{\mathbb{P}}$:

1. $up(\sigma ,\tau )\in M^{\mathbb{P}}$ and $val(up(\sigma ,\tau ),G)=\{{\sigma }_G,{\tau }_G\}$

2. $op(\sigma ,\tau )\in M^{\mathbb{P}}$ and $val(op(\sigma ,\tau ),G)=({\sigma }_g,{\tau }_G)$

Lemma: (K. VII.2.18) Ax. of Ext., Found., Pair., Union are true in $M[G]$.

Proof. Ext. holds because $M[G]$ is trans., Found. holds for any set, pairing is trivial from 2.17(1.).

For Union: if $a\in M[G]$, there is a $b\in M[G]$ s.t. ${\bigcup }_a\subset b$; fix $\tau \in M^{\mathbb{P}}$ s.t. $a={\tau }_G$, let $\pi ={\bigcup }_{dom(\tau )}$, then $\pi \in M^{\mathbb{P}}$, so ($b=$)${\pi }_G\in M[G]$. If $c$ is any element of $a,c={\sigma }_G$ for some $\sigma \in dom(\tau )$. Since $\sigma \subset \pi ,c={\sigma }_G\subset {\pi }_g=b$, thus ${\bigcup }_a\subset b$.

I continue the path as in Kunen:

Definition: let $E\subset \mathbb{P}$ and $p\in \mathbb{P}$, we say that $E$ is dense below $p$ iff: ${\forall }_{q\le p}{\exists }_{r\le q}r\in E$

Lemma: (K. VII.2.20) $\mathcal{M}$ trans., $\mathcal{M}\models ZFC$, $\mathbb{P}\in M$, $E\subset \mathbb{P}$, $E\in M$, let $G$ be a $\mathbb{P}$-gen. over $M$, then

1. Either $G\cap E\ne \varnothing$ or ${\exists }_{q\in G}{\forall }_{r\in E}r\perp q$.

2. If $p\in G$ and $E$ is dense below $p$, then $G\cap E\ne \varnothing$.

8th Lecture

From Kunen, consider the following example: fix a ctm $\mathcal{M}$ for $ZFC$, let $\mathbb{P}=(Fn(\omega ,2),\supseteq ,1)$, where $1$ is the empty function. We see that $\mathbb{P}\in M$, since its definition is absolute for transitive models (?). If $G$ is a filter on $\mathbb{P}$, say $f_G={\bigcup }_G$ (we know that $f_G\in G$ since ${\forall }_{p,q\in G}{\exists }_{r\in G}r\le q\wedge r\le p$ holds in a filter) is a function with $dom(f_G)\subseteq \omega$, so, for each $n$, let $D_n=\{p\in \mathbb{P}|n\in dom(p)\}$, then $D_n$ is dense and $D_n\in M$ (by abs. of its def. (?)). Thus if $G$ is $\mathbb{P}$-gen. over $M$, then we have that: ${\forall }_{n\in \omega }G\cap D_n\ne \varnothing$, so $dom(f_G)=\omega$.

Claim. $f_G\in M[G]$. We proved that $G\in M[G]$, we also know that Ax. of Union is absolute fro transitive models of $ZF$, therefore ${\bigcup }_G\in M[G]$.

We also proved that if $G$ is $\mathbb{P}$-gen. then $G\notin M$ (VII.2.4.). $E=\{p|p⊈f\}$, then $E$ is dense and $G\cap E=\varnothing$, so if $f_G\in M$ then also $E\in M$ but by def. of the gen. it can’t be the case.

Let’s introduce forcing, we start with a little story:

the people in $M$ can’t construct a $G$ that is $\mathbb{P}$-gen., they may have faith that there exists a being to whom their universe, $M$, is countable. Such a being would have a generic $G$ and an $f_G={\bigcup }_G$. The people in $M$ have no epistemic access to those objects, though they have names for them: $\Gamma$ and $\Phi$. There are some properties that those people can find out of $f_G$ and $G$, e.g. that $f_G\in Fn(\omega ,2)$, but they don.t know e.g. what $f(0)$ is equal to, since that depends on the $G$ chosen. They know that $\{(0,0)\}\in G\to f_G(0)=0$ and $\{(0,1)\}\in G\to f_G(0)=1$ (since they know that $f_G={\bigcup }_G$ and all those functions must agree on where $0$ goes). They can evolve even more and construct a language, a forcing language, where a sentence $\psi$ uses names $M^{\mathbb{P}}$ to assert on $M[G]$ , e.g. the proposition $\Phi (\check{0})=\check{1}$. The person in $M$ may not know whether a given $\psi$ is true in $M[G]$ because it will depend on $G$ to which they can’t access. We write then $p⊩\psi$ to mean that for any $G$ which are $\mathbb{P}$-gen. over $M$ if $p\in G$ then ${\psi }^{M[G]}$. For instance: $\{(0,0)\}⊩\Phi (\check{0})=\check{0}$ and $\{(0,1)\}⊩\Phi (\check{0})=\check{1}$. They also write $1⊩\Phi \in Fn(\omega ,2)$ and $1⊩\Phi ={\bigcup }_{\Gamma }$, these are formulae true for all generics $G$. We deduce then that people in $M$ are able to decide some $p⊩\psi$. This is needed to see that $M[G]\models ZFC$, in fact, even after that, people in $M$ will build very complicated $\mathbb{P}$ for which the desired axioms are forced to be true in $M[G]$. By definition of $⊩$ we know that if $p⊩\psi$ for some $p\in G$ then $M[G]$, though, the converse is true too, in fact: 

Equivalence Lemma (L. 10): ${\psi }^{M[G]}\to {\exists }_{p\in G}p⊩\psi$. For instance, if $\Phi (\check{0})=\check{0}$, then $\{(0,0)\}\in G$, this holds for any $G$.

Now we prove point (5) from the previous lecture, claim: Let $\mathcal{M}$ be a transitive model of $ZFC$ s.t. $M\subseteq N$ and $G\in N$, then $M[G]\subset N$.

Proof. The def of $val(\tau ,G){\tau }_G$ is absolute between transitive models of $ZFC$ so if $M^{\mathbb{P}}\subseteq M\subseteq N$ and $G\in N$ then $val(\tau ,G)\in N$ for $\tau \in M^{\mathbb{P}}$. So:

Lemma: For all $\tau \in M^{\mathbb{P}}$:

1. $rk({\tau }_G)\le rk(\tau )$
2. $o(M[G])=o(M)$ ($o$ denotes the ordinals) Proof. in the Notes $\square$

We are left to show that $M[G]\models$ Ax. Sep. i.e. for any formula $\varphi$ in ${\mathcal{L}}_{ϵ}$, $\vec{a}$, $b\in M[G]$ then there is an $S\in M[G]$ s.t. $S=\{z|z\in b\wedge \varphi (z,\vec{a}{)}_{M[G]}\}$. Considering the following simple example:

Example: take $b=\omega$, $\varphi =z\in a$, $a={\tau }_G$; I need then to fined a name $\sigma \in M^{\mathbb{P}}$ s.t. ${\sigma }_G={\tau }_G\cap \omega$. Why not just take $\sigma$ to be ${\tau }_G\cap \omega$? Because if ${\tau }_G\notin M$ then we can’t assume ${\tau }_G\cap \omega \in M$. An alternative is: If $\tau$ is of the form $\{({\check{x}}_i,p_i)|i\in I\}$ then $\sigma =\{{\check{x}}_i,p_i|i\in I\wedge x_i\in \omega \}$, this works but in general, for something in $dom\tau$, we don’t know if it’s of that form. For instance suppose $(\pi ,p)\in \tau$ and $\pi =\{(\check{n},p_n)|n\in \omega \}$. Then ${\pi }_G\in \omega$ iff there is some $n\in \omega$ s.t. ${\forall }_{m\le n}{p}_m\in G$ and ${\forall }_{n<m}{p}_m\notin G$. Thus if there is a $q\in \mathbb{P}$, $n\in \omega$ s.t. $p\ge q$, ${\forall }_{m\le n}{p}_m\ge q$ and ${\forall }_{n<m}{p}_m\perp q$, then $q\in G\Rightarrow {\pi }_G\in {\tau }_G\cap \omega$ so we could put $(\pi ,q)$ in $\sigma$.

Definition: we say that $F{\mathcal{L}}_{M,\mathbb{P}}$ is the collection of formulae in the language $\mathcal{L}$ extended with constant symbols for each name $M^{\mathbb{P}}$.

Example: if $\varphi$ is a formula of ${\mathcal{L}}_{ϵ}$ with $z$ as a free variable then $\varphi (\check{n},\tau )$ is in $F{\mathcal{L}}_{M,\mathbb{P}}$. So let $\psi$ be a sentence of $F{\mathcal{L}}_{M,\mathbb{P}}$ (namely without free variables), then $M[G]\models \psi$ has the usual model theoretic meaning with $\in$ interpreted as membership and any constant symbol/$\mathbb{P}$-name $\tau$ interpreted as ${\tau }_G$.

Definition: let $\psi \in F{\mathcal{L}}_{M,\mathbb{P}}$ and $p\in \mathbb{P}$, say: $p{⊩}_{\mathbb{P},M}\psi$ iff for all $\mathbb{P}$-generic filters $G$ over $M$ with $p\in G$ we have $M[G]\models \psi$.

Also (K. VII.3.1): let $\varphi (x_1,...,x_n)\in {\mathcal{L}}_{ϵ}$, $FV(\varphi )=x_1,...,x_n$, let $M$ be a ctm for $ZFC$, $\mathbb{P}$ in $M$, ${\tau }_1,...,{\tau }_n\in M^{\mathbb{P}}$ and $p\in \mathbb{P}$, so $p{⊩}_{\mathbb{P},M}\varphi ({\tau }_1,...,{\tau }_n)$ iff ${\forall }_{G\mathbb{P}\text{-gen. }\wedge p\in G}{\varphi }^{M[G]}(val({\tau }_1,G),...,val({\tau }_n,G))$Example: let $\Gamma =\{(\check{p},p)|p\in \mathbb{P}\}$ be the name for generic if $p\le q$ then $p⊩q\in \Gamma$, i.e. for all filters $G$ s.t. $p\in G$ we have $M[G]\models \check{q}\in \Gamma$, i.e. $M[G]\models {\check{q}}_G\in {\Gamma }_G$, i.e. $(q\in G{)}_{M[G]}$, i.e. $q\in G$. So we say that if $p$ extends $q$ and $q$ is in the generic, then $p$ is in the generic too.

It also holds that $1⊩\psi$ iff. $M[G]\models \psi$ for all $\mathbb{P}$-gen. filters $G$ over $M$, e.g. $1⊩$Ax. Union by the lemma of the last week. If $\mathbb{P}$ is atomless and $p\perp q\in \mathbb{P}$, then $p⊩\check{q}\in \Gamma$. But $1/⊩\check{q}\in \Gamma$ and $1/⊩\check{p}\notin \Gamma$, we may have $p/⊩\psi$ and $p/⊩\neg \psi$. Also $1⊩\check{\omega }\in \check{(\omega +1)}$.

Lemma: If $p⊩\varphi$ and $q\le p$ then $q⊩\varphi$.

Proof. If $q\le p$ and $p\in G$ for a filter $G$, then $q\in G$ by upward closure, so all generics s.t. $q\in G$ are a subset of all those s.t. $p\in \varphi$, so if ${\varphi }^{M[G]}$ holds in the latter, it must hold in the former too. $\square$ 

Example: Back to the previous example, we have: $\sigma =\{(\check{n},p)|n\in \omega \wedge p\in \mathbb{P}\wedge p⊩\check{n}\in \tau \}$, $\sigma$ is a name but is it definable in $M$ (i.e. is $\sigma \in M^{\mathbb{P}}$)? Clearly not, so we have a problem:

Problem:

1. We defined $⊩$ using generic for $M$, and these are generally not in $M$, so we have no obvious reson to think $\sigma \in M$.
2. How can we be sure that ${\sigma }_G=\omega \cap {\tau }_G$. So ${\sigma }_G\subseteq \omega \cap {\tau }_G$ since if $G$ is a generic with $p\in G$, hen $n\in \sigma$ iff $p⊩\check{n}\in \tau$, hence $M[G]\models \check{n}\in \tau$ then $n\in \tau \cap \omega$. But how do we know, for every $n\in \omega \cap {\tau }_G$ there is some $p\in \mathbb{P}$ s.t. $p⊩\check{n}\in \tau$? In order to solve this we now state two lemmas: the truth lemma and the definability lemma:???

Truth Lemma: Let $\psi$ be a sentence in $F{\mathcal{L}}_{M,\mathbb{P}}$, $G$ a $\mathbb{P}$-generic filter over $M$, then: $M[G]\models \psi \text{ iff there is a }p\in G\text{ s.t. }p⊩\psi$Note: "$\Leftarrow$" is obvious from the definition of $⊩$.

Example: look at the proof of (5) in the next lecture Definability Lemma: Let $\varphi$ be a formula of ${\mathcal{L}}_{ϵ}$ with $FV(\varphi )=\{x_1,...,x_n\}$, then $\{(p,\mathbb{P},\le ,1,{\theta }_1,...,{\theta }_n)|(\mathbb{P},\le ,1)\text{ is a forcing poset }\wedge p\in \mathbb{P}\wedge {\theta }_1,...,{\theta }_n\in M^{\mathbb{P}}\wedge p{⊩}_{M,\mathbb{P}}\varphi ({\theta }_1,...,{\theta }_n)\}$is definable without parameters in $M$.

Note: You should also check the Tarski Undefinability Lemma, which states that truth in a model can’t be defined within itself.

With these lemmas we’ll see that $\sigma$ works as it should.

Definability Lemma for $\varphi =x\in y\Rightarrow \sigma \in M^{\mathbb{P}}$ and the Truth Lemma implies that $(n\in {\tau }_G\cap \omega {)}_{M[G]}$ i.e. $M[G]\models \check{n}\in \tau \cap \check{\omega }\Rightarrow {\exists }_{p\in G}p⊩\check{n}\in \tau \wedge \check{\omega }\Rightarrow p⊩\check{n}\in \tau \Rightarrow (\check{n},o)\in \sigma \Rightarrow n\in {\sigma }_G$, thus $\omega \cap {\tau }_G\subseteq {\sigma }_G$.

In the next lecture we’ll finish the proof of (4).

9th Lecture

Recall that $p⊩\varphi$ for some $\varphi \in F{\mathcal{L}}_{M,\mathbb{P}}$. So $p⊩\varphi$ iff $M[G]\models \varphi$, so the DL says that $p⊩\varphi$ is definable, so

Lemma: for any $\mathbb{P}\in M$ and sentence $\varphi ,\psi \in F{\mathcal{L}}_{M,\mathbb{P}}$ it holds:

1. No $p$ forces boht $\varphi$ and $\neg \varphi$

2. If $\varphi ,\psi$ are logically equivalent then $p⊩\varphi$ iff $p⊩\psi$

3. $p⊩\varphi$ and $q\le p$ then $q⊩\varphi$

4. $p⊩\varphi \wedge \psi$ iff $p⊩\varphi \wedge p⊩\psi$

Proof. all clear from def. $\square$

Lemma: $M[G]\models$ Ax. Sep.

Proof. Fix a formula $\varphi$ of ${\mathcal{L}}_{ϵ}$ with $y\notin FV(\varphi )$ … , forget the proof

Theorem $M[G]\models ZFC$

Proof. There are just Power set and Replacement missing, those are proven in the notes. $\square$

You also find the Axiom of Choice proven in this book.

forget those proofs.

Lemma: I continue the previous list with other properties of forcing:

5. $p⊩\neg \varphi$ iff $\neg {\exists }_{q\le p}q⊩\varphi \wedge p⊩\varphi$ iff $\neg {\exists }_{q\le p}q⊩\varphi$

6. $p⊩\varphi \to \psi$ iff ${\exists }_{q\le p}q⊩\varphi \wedge q⊩\neg \psi$

7. $p⊩\varphi \vee \psi$ iff. $\{q\le p|q⊩\varphi \vee q⊩\psi \}$ is dense below $q$

Proof.

(5) "$\Rightarrow$" clear from $(p⊩\varphi \wedge q\le p)\to q⊩\varphi$.

"$\Leftarrow$" Assume $p/⊩\neg \varphi$, then we can find sucha a generic $G$ with $p\in G$ and $M[G]\models \varphi$. By TL here is $r\in G$ s.t. $r⊩\varphi$; since $G$ is a filter we can find $q\in G$ s.t. $q\le p$ then $q⊩\varphi$, hence, by (3), contradiction. ((very easy, use this as an example of the TL))

(6) The same as in (5) if you remember that $\varphi \to \psi \iff \neg (\varphi \wedge \neg \psi )$.

(7) $p/⊩\neg \psi \to \psi$ ($\iff \psi \vee \psi$), then it is eq by (6) to: ${\exists }_{r\le p}r⊩\neg \psi \wedge r⊩\neg \varphi {\iff }^{(5)}{\exists }_{r\le p}{\forall }_{q\le r}q/⊩\psi \wedge q/⊩\psi$. Definition: (K. VII.2.19) A set $E$ is dense below $p$ if ${\forall }_{q\le p}{\exists }_{r\le q}r\in E$.

Now observe that if $M[G]\models \varphi$ and $p\in G$ then there is a $q\in G$ s.t. $q\le p$ and $q⊩\varphi$. $\square$

Lemma: let $\varphi (x)\in F{\mathcal{L}}_{M,\mathbb{P}}$ with only $x$ as a free variable:

1. $p⊩{\forall }_x\varphi (x)$ iff $p⊩\varphi (\tau )$ forall $\tau \in M^{\mathbb{P}}$

2. $p⊩{\exists }_x\varphi (x)$ iff $\{q\le p|{\exists }_{\tau \in M^{\mathbb{P}}}q⊩\varphi (\tau )\}$ what on this set?

Proof. (1) $M[G]\models {\forall }_x\varphi (x)$ iff $M[G]\models \varphi (\tau )$ for all $\tau \in M^{\mathbb{P}}$, so if $p⊩{\forall }_x\varphi (x)$ iff for all $\tau \in M^{\mathbb{P}}$ then all generics be with $p\in G$ and $M[G]\models \varphi (\tau )$  iff ${\forall }_{\tau \in M^{\mathbb{P}}}p⊩\varphi (\tau )$.

(2) By (5) and (1) $p⊩\neg {\forall }_x\varphi (x)\iff$ for all $r\le p$, $r/⊩{\forall }_x\neg \varphi (x){\iff }^{(1)}{\forall }_{r\le p}{\exists }_{\tau \in M^{\mathbb{P}}}r/⊩\neg \varphi (\tau )$ ${\iff }^{(5)}{\forall }_{r\le p}{\exists }_{\tau \in M^{\mathbb{P}}}{\exists }_{q\le r}q⊩\varphi (\tau )$, $\square$

10th Lecture

Today we want to prove the TL and the DL, it is of no use for the application of forcing and, in order to do so, we need to define ${⊩}^{\ast }$, so:

Definition: (K. VII.3.3) let $\varphi \in {\mathcal{L}}_{ϵ}$ s.t. $FV(\varphi )=x_1,...,x_n$, $p\in \mathbb{P}$, ${\tau }_1,...,{\tau }_n\in V^{\mathbb{P}}$, then:

1. $p{⊩}^{\ast }{\tau }_1={\tau }_2$ iff

2. for all $({\pi }_1,s_1)\in {\tau }_1$, $\{q\le p|q\le s_1\to {\exists }_{({\pi }_2,s_2)\in {\tau }_2}q\le s_2\wedge q{⊩}^{\ast }{\pi }_1={\pi }_2\}$ is dense below $p$ and

3. for all $({\pi }_2,s_2)\in {\tau }_2$, $\{q\le p|q\le s_2\to {\exists }_{({\pi }_1,s_1)\in {\tau }_1}q\le s_1\wedge q{⊩}^{\ast }{\pi }_2={\pi }_1\}$ is dense below $p$ and

4. $p{⊩}^{\ast }{\tau }_1\in {\tau }_2$ iff $\{q|{\exists }_{(\pi ,s)\in {\tau }_2}q\le s\wedge q{⊩}^{\ast }\pi ={\tau }_1\}$ is dense below $p$

5. $p{⊩}^{\ast }\varphi ({\tau }_1,...,{\tau }_n)\wedge \psi ({\tau }_1,...,{\tau }_n)$ iff $p{⊩}^{\ast }\varphi ({\tau }_1,...,{\tau }_n)$ and $p{⊩}^{\ast }p⊩\psi ({\tau }_1,...,{\tau }_n)$

6. $p{⊩}^{\ast }\neg \varphi ({\tau }_1,...,{\tau }_n)$ iff there is no $q\le p$ s.t. $q{⊩}^{\ast }\varphi ({\tau }_1,...,{\tau }_n)$

7. $p{⊢}^{\ast }{\exists }_x\varphi (x,{\tau }_1,...,{\tau }_n)$ iff $\{r|{\exists }_{\sigma V^{\mathbb{P}}}r{⊩}^{\ast }\varphi (\sigma ,{\tau }_{,}...,{\tau }_n\}$ is dense below $p$

Lemma: $p⊩\varphi ({\tau }_1,...,{\tau }_n)\leftrightarrow (p{⊩}^{\ast }({\tau }_1,..,{\tau }_n){)}^M$

Why this? People in $M$ can’t properly use the relation $⊩$ since that has been defined in $V$ and not in $M$ and therefore involves a knowledge of all possible generics. Instead, we should be able to decide within $M$ whether $p⊩\varphi$ hence we define this second relation s.t. it basically does the same, in fact $p⊩\varphi \iff p{⊩}^{\ast }\varphi$.

Lemma: let $\varphi \in F{\mathcal{L}}_{M,\mathbb{P}}$, tfae:

1. $p{⊩}^{\ast }\varphi$

2. $\{p_1\le p|p_1{⊩}^{\ast }\varphi \}$ is dense below $p$

3.  $\neg {\exists }_{q\le p}q{⊩}^{\ast }\neg \varphi$ 

(Proof in the Notes)

Lemma: for $\varphi \in F{\mathcal{L}}_{M,\mathbb{P}}$, if $p{⊩}^{\ast }\varphi$ and $p_1\le p$ then $p_1{⊩}^{\ast }\varphi$

Lemma: let $D\subset \mathbb{P}$ with $D\in M$ dense below $p$ ($\in \mathbb{P}$) if $G$ is $\mathbb{P}$-generic over $M$ and $p\in G$, then $G\cap D\ne \varnothing$.

Equivalence Lemma: (K. VII.3.6) let $M$ be ctm of $ZFC$, $\mathbb{P}\in M$, let $FV(\varphi )=(x_1,...,x_n)$, ${\tau }_1,...,{\tau }_n\in M^{\mathbb{P}}$:

1. For all $p\in \mathbb{P}$: $p⊩\varphi ({\tau }_1,...,{\tau }_n)\leftrightarrow (p{⊩}^{\ast }\varphi ({\tau }_1,...,{\tau }_n){)}^M$

2. TL: For all $\mathbb{P}$-gen. over $M$, $G$: $M[G]\models \varphi ({\tau }_{1,G},...,{\tau }_{n,G})\leftrightarrow {\exists }_{p\in G}p⊩\varphi ({\tau }_1,...,{\tau }_n)$ 

Equivalence Lemma: (Lecture Notes)

Lemma: let $M$ be a ctm with $\mathbb{P}\in M$ and $G$ be a $\mathbb{P}$-generic over $M$. Fix $\varphi \in F{\mathcal{L}}_{M,\mathbb{P}}$ then:

1. if $p\in G$ and $p{⊩}^{\ast }\varphi$ then $M[G]\models \varphi$

2. if $M[G]\models \varphi$ then there is some $p\in G$ s.t. $p{⊩}^{\ast }\varphi$

Not proved

Corollary: let $M,\mathbb{P},\varphi$ be as in in the previous lemma, then $p⊩\varphi \iff p{⊩}^{\ast }\varphi$.

Proof. $p{⊩}^{\ast }\varphi \Rightarrow$ for an generic $G$ (s.t. $p\in G$), $M[G]\models \varphi {\iff }^{def}p⊩\varphi$. Now suppose $p⊩\varphi$ but $p/{⊩}^{\ast }\varphi$, by the first lemma of today (3) we have ${\exists }_{q\le p}q{⊩}^{\ast }\neg \varphi$, then for such a $q$, by def of "${⊩}^{\ast }$" we have $\neg {\exists }_{r\le q}r{⊩}^{\ast }\varphi$. Let $G$ be a generic with $q\in G$, then $p\in G$ so $M[G]\models \varphi$ by def of $⊩$. By lemma the last lemma (2) $s\in G$ s.t. $s{⊩}^{\ast }\varphi$ since $q$, $s\in G$, ${\exists }_{r\in G}r\le q\wedge r\le s$, then we get $r{⊩}^{\ast }\varphi$ by the first lemma of today (1), then we get contradiction and our claim is proved, $\square$.

11th Lecture

Example From Kunen

Brief Recap

Pars $I$

1. Define $Fn(I,J)$

2. $...\to dom({\bigcup }_G)=I\wedge ran({\bigcup }_G)=J$

3. Set $\mathbb{P}=Fn(k\times \omega ,2)$, ${\bigcup }_G:k\times \omega \to 2$, $f_{\alpha }(n):={\bigcup }_G(\alpha ,n)$

4. $\{f_{\alpha }|\alpha <k\}\in M[G]$ by abs.

5. $D_{\alpha ,\beta }$ is dense

6. $G\cap D_{\alpha ,\beta }\ne \varnothing$, hence $f_{\alpha }\ne f_{\beta }$ 

7. Then we have $(2^{\omega }\ge |k|{)}^{M[G]}$

Pars $II$

1. Define $ccc$ 
2. $|J|\le \omega \to F(I,J)$ has $ccc$
3. Def. preserves cardinals
4. Def. preserves cofinalities
5. cof $\to$ card
6. $...\to$ cof
7. $(\mathbb{P}$ has $ccc{)}^M$ pres. cof and card

Pars $III$

$\mathbb{P}:=({\omega }_2^M\times \omega ,2)$ has $ccc$, hence ${\omega }_2^M={\omega }_2^{M[G]}$, hence $(2^{\omega }\ge {\omega }_2{)}^{M[G]}$, hence $M[G]\models \neg CH$.

Definition: $Fn(I,J)=\{p:|p|<\omega \wedge func(p)\wedge dom(p)\subseteq I\wedge ran(p)\subseteq J\}$, $p\le q:=p\supseteq q$, $1:=\varnothing$

Notice that since “finite” is absolute so is the definition of $Fn(I,J)$. Hence if $I,J\in M$ then $Fn(I,J)=Fn(I,J{)}^M\in M$. Then for a filter $G$ on $Fn(I,J)$, note that ${\bigcup }_G\in G\subset Fn(I,J)$. 

Now, for $J\ne \varnothing$, define $D_i=\{f\in Fn(I,J)|i\in dom(f)\}$ and note that it is dense for any $i\in I$. Furthermore, by absoluteness, $D_i\in M$ if $I,J\in M$; thus if $G$ is a gen. over $M$, then ${\forall }_{i\in I}G\cap D_i\ne \varnothing$ then $dom({\bigcup }_G)=I$. Hence:

Lemma: $(I,J\in M\wedge |I|\ge \omega \wedge J\ne \varnothing \wedge G$ is$Fn(I,J)$-gen. ov. $M)\to dom({\bigcup }_G)=I\wedge ran({\bigcup }_G)=J$.

Now take a $k$ s.t. $k\in M$ and $(k>\omega {)}^M$, let $\mathbb{P}=Fn(\omega ,k)$ and $G$ a $\mathbb{P}$-gen. over $M$. Then ${\bigcup }_G\in M[G]$ ==(by abs. of $\bigcup$)==, and $G$ is a func. from $\omega$ onto $k$, so in $M[G]$ we see that $k$ is a countable ordinal. We say that $\mathbb{P}$ collapses $k$. So: $(k>\omega {)}^M\wedge (k<\omega {)}^{M[G]}$.

Similarly we can use a different $I,J$ so that $Fn(I,J)$ will help us to obtain a model of $\neg CH$. Take the same $k$ but now $\mathbb{P}:=Fn(k\times \omega ,2)$, for a gen. $G$, then ${\bigcup }_G:k\times \omega \to 2$, this can be regarded as a $k$ sequence of functions, let $f_{\alpha }(n)=({\bigcup }_G)(\alpha ,n)$ for $\alpha <k$, $n<\omega$. By absoluteness $\{f_{\alpha }|\alpha <k\}\in M[G]$, all elements of this sequence are distinct since for $\alpha \ne \beta$:$D_{\alpha ,\beta }=\{p\in \mathbb{P}|{\exists }_{n\in \omega }(\alpha ,n)\in dom(p)\wedge (\beta ,n)\in dom(p)\wedge p(\alpha ,n)\ne p(\beta ,n)\}$Note that $D_{\alpha ,\beta }$ is dense in $M$, since, like for $D_i$, you can always extend those functions since $I$ is infinite, so $G\cap D_{\alpha ,\beta }\ne \varnothing$ then $f_{\alpha }\ne f_{\beta }$. Thus we notice that $M[G]$ contains a $k$-sequence of distinct functions from $\omega$ into $2$, then:

Lemma: if $k\in M$ and $G$ a $Fn(k\times \omega ,2)$-gen. over $M$ then $(2^{\omega }\ge |k|{)}^{M[G]}$.

If we now take $k=({\omega }_2{)}^{M[G]}$, then we could say that $2^{\omega }\ge {\omega }_2$ in $M[G]$ hence, $M[G]\models \neg CH$. We need first to check that $k$ is actually $({\omega }_2{)}^{M[G]}$, this is not obvious, we have seen how a slight change in the $\mathbb{P}$ can cause changes on countable and uncountable cardinals, we’ll prove that this is not the case since $Fn(k\times \omega ,2)$ has the $ccc$ in $M$. Let’s start with:

Definition: let $\mathbb{P}$ be a forcing poset and $A\subset \mathbb{P}$, then $A$ is an antichain iff ${\forall }_{p,q\in A}p\perp q$, namely all elements are pairwise incompatible. $A$ is a maximal antichain iff $A$ is an antichain and there is no $r\in \mathbb{P}\setminus A$ s.t. $\{r\}\cup A$ is an antichain, i.e. ${\forall }_{r\in \mathbb{P}\setminus A}{\exists }_{p\in A}/p\perp r$.

Example: in a tree ordering any level is an antichain and if every node branches then any level is a maximal antichain (watch the notes for a picture).

Example: $\mathbb{P}=Fn(\omega ,k)$ set $p_{\alpha }=\{0,\alpha \}$, then $\{p_{\alpha }|\alpha \in k\}$ is an antichain of size $k$ so it is maximal, $\neg (p_{\alpha }\perp p)=\{(0,\alpha ),(1,\beta )\}$.

Definition: $\mathbb{P}$ has the countable chain condition ($ccc$) iff all antichains in $\mathbb{P}$ are countable, also $\mathbb{P}$ has the $\lambda -cc$ iff all antichains in $\mathbb{P}$ are of size $<\lambda$. Hence $ccc\sim {\omega }_1-cc$.

Example: Consider a binary tree ordering, is it $\omega -cc$? No! Take the binary tree $\{(0,1),(0,0,1),(0,0,0,1),...\}$ is an infinite antichain, it is though a ${\omega }_1-cc$ since the whole tree is countable. In general notice that $\mathbb{P}$ has the $|\mathbb{P}{|}^{+}-cc$.

Lemma: let $I,J\ne \varnothing$, $\mathbb{P}=Fn(I,J)$ has the $ccc$ iff $J$ is countable. If $J$ is infinite, $\mathbb{P}$ has the $|J{|}^{+}-cc$.

I can just instantiate this lemma to get:

Lemma: $|J|\le \omega \to Fn(I,J)$ has $ccc$.

There are many others $\mathbb{P}$ with $ccc$. The relevance of the $ccc$ in forcing is that we have the following lemma which gives us a way to approximate within $M$ any function in $M[G]$.

Lemma: Assume: $\mathbb{P}\in M$, $(\mathbb{P}$ is $ccc{)}^M$, $A,B\in M$, $G$ is $\mathbb{P}$-gen. over $M$, $f\in M[G]$ s.t. $f:A\to B$. There is a $F:A\to \mathcal{P}(B)$ s.t. $F\in M$, ${\forall }_{a\in A}f(a)\in F(a)$, ${\forall }_{a\in A}(|F(a)|\le \omega {)}^M$. ??

In order to see the use of this we shall first define:

Definition: let $\mathbb{P}\in M$ we say that $\mathbb{P}$ preserves cardinals iff whenever $G$ is $\mathbb{P}$-gen. over $M$ we have:${\forall }_{\beta \in o(M)}(\beta >\omega \wedge \beta \text{ is a cardinal}{)}^M\to (\beta \text{ is a cardinal}{)}^{M[G]}$Since $\omega$ is absolute, it is a problem only if $\beta >\omega$. Also if $\beta$ is a cardinal of $M[G]$ it also is one in $M$, since any function in $M$ from a smaller ordinal onto $\beta$ must be in $M[G]$ too why??. Similarly:

Definition: let $\mathbb{P}\in M$ then $\mathbb{P}$ preserves cofinalities if $G$ is a $\mathbb{P}$-gen. over $M$ and $\gamma$ is a limit ordinal in $M$ and $cf(\gamma {)}^M=cf(\gamma {)}^{M[G]}$.

Lemma: (K. VII.5.8)  $\mathbb{P}$ preserves cofinalities $\to$ $\mathbb{P}$ preserves cardinals

To simplify how to check preservation of cofinalities we know

Lemma: (K. VII.5.9) let $\mathbb{P}\in M$, if ‘whenever $G$ is a $\mathbb{P}$-gen. over $M$ and $k$ a regular uncountable cardinal of $M$, then $(k$ is reg.${)}^{M[G]}$’, then $\mathbb{P}$ preserves cofinalities.

Hence we derive

Theorem: if $\mathbb{P}\in M$ and $(\mathbb{P}$ has $ccc{)}^M$, then $\mathbb{P}$ preserves cofinalities and hence cardinals.

Now we have all tools we need to produce a model of $\neg CH$.

Let $\mathbb{P}:=Fn({\omega }_2^M\times \omega ,2)$, hence $\mathbb{P}$ has $ccc$ in $M$, thus it preserves cardinals, so ${\omega }_2^M={\omega }_2^{M[G]}$, then $(2^{\omega }\ge {\omega }_2{)}^{M[G]}$. But can we make $2^{\omega }={\omega }_2$? Clearly $(2^{\omega }\ge {\omega }_2{)}^M$ holds also in any cardinal preserving extension of $M$.

Other Notes

Lemma: let $\varphi \in F{\mathcal{L}}_{M,\mathbb{P}}$, tfae:

1. $p{⊩}^{\ast }\varphi$

2. $\{p_1\le p|p_1{⊩}^{\ast }\varphi \}$ is dense below $p$

3.  $\neg {\exists }_{q\le p}q{⊩}^{\ast }\neg \varphi$ 

(Proof in the Notes)

Lemma: for $\varphi \in F{\mathcal{L}}_{M,\mathbb{P}}$, if $p{⊩}^{\ast }\varphi$ and $p_1\le p$ then $p_1{⊩}^{\ast }\varphi$

Lemma: let $D\subset \mathbb{P}$ with $D\in M$ dense below $p$ ($\in \mathbb{P}$) if $G$ is $\mathbb{P}$-generic over $M$ and $p\in G$, then $G\cap D\ne \varnothing$. 

Messy Notes

From the Lecture Notes

Here some general notes on the procedure and the use of the previous lemmas in the process of proving independence of $CH$:

Let $M\models ZFC$ be a ctm and $\mathbb{P}\in M$ an atomless forcing poset, also $G$ a $\mathbb{P}$-generic over $M$. Then, by a previous lema, we have: (i) $M[G]\models ZFC$ is a ctm, (ii) $G\in M[G]\setminus M$ and (iii) $M[G]$ is minimal s.t. (i) and (ii) hold.

We now want to show that $con(ZFC)\Rightarrow con(ZFC+\neg CH)$, so if $M\models ZFC+\neg CH$. Also recall $\mathbb{P}=Fn(I,J)$, $I$ is infinte, $J=\varnothing$. $I,J\in M$ if $G$ is $\mathbb{P}$-generic over $M$ then ${\bigcup }_G=:f_G$ is a function with $dom(f_G)=I$, $ran(f_G)=J$,$f_G\notin M$.

Example: $Fn(\omega ,2)$, if $G$ is a generic over $M$, then ${\bigcup }_G$ is a characteristic foundation for a new subset of $\omega$. Let $k\in M$ with $(k={\omega }_2{)}_M$, meaning that according to $M$ there is an element corresponding to ${\omega }_2$ even if $k$ is countable.

Let then $\mathbb{P}=Fn(k\times \omega ,2)$ and $G$ be a $\mathbb{P}$-generic over $M$. Let $f_G={\bigcup }_G$. Then $f_G:k\times \omega \to 2$ as above. We can think of $f_G$ as coding $k$-many functions $h_{\alpha }:\omega \to 2$ where $H_{\alpha }(n):=f_G(\alpha ,n)$. Then $E_{\alpha ,\beta }=\{p\in \mathbb{P}|{\exists }_{n\in \omega }(\alpha ,n),(\beta ,n)\in dom(p)\wedge p(\alpha ,n)\ne p(\beta ,n)\}$ is dense for $\alpha <\beta <k$: for $q\in \mathbb{P}$ we extend $q$ to $p: =. q \cup {((\alpha, n), 0), ((\beta, n),

1)}$where$n > max({m | \exists_{\gamma \in k} \gamma, m  \in dom(q)})$,then$p \in E_{\alpha, \beta}$,then$G$mustmeeteach$E_{\alpha, \beta}$andtherefore$h_\alpha \not = h_\beta$for$\alpha \not = \beta$.

4.7, recall the first lemma of the last week: if $G$ is a generc over M, $M[G]\models \varphi$, $p\in G$, then there is $q\in G$ s.t. $q⊢\varphi$ and $q<p$.

Let $M$ be a ctm and $(k={\omega }_2{)}_M$, let $G$ be a $Fn(k\times \omega ,2)$-generic over $M$, $f_G={\bigcup }_G$. Define $h_{\alpha }:\omega \to 2$ by $h_{\alpha }(n)=f_G(\alpha ,n)$, then for $\alpha \ne \beta$, $h_{\alpha }\ne h_{\beta }$ and $\{h_{\alpha }|\alpha <k\}\in M[G]$, but now, how do we know htat $M[G]\models |k|>{\omega }_1$?

For $(k={\omega }_2{)}_M$ we need to check $(k={\omega }_2{)}_{M[G]}$.

Example: let $Q=Fn(\omega ,k)$ with $(k={\omega }_2{)}_M$ as above, then we know for $H$ a $Q$-generic over $M$, $f_H:={\bigcup }_H$, $f_H:\omega \to k$ is surj. Thus $M[H]\models k$ is countable. there will be an ordinal $\lambda \in M[H]$ s.t. $(\lambda ={\omega }_2{)}_{M[H]}$ but $\lambda >k$.

Definition: for a forcing poset $\mathbb{P}\in M$:

1. $\mathbb{P}$ preserves cardinals iff ${\forall }_{G,\mathbb{P}\text{-generic over }M}{\forall }_{\beta (<0)}(\beta \text{ is a cardinal}{)}_M\text{ iff }(\beta \text{ is a cardinal }{)}_{M[G]}$.

2. $\mathbb{P}$ preseres cofinalities iff for all $\mathbb{P}$-generic and for all ordinals $\gamma (<o[M])$, $(cf(\gamma ){)}_M=(cf(\gamma ){)}_{M[G]}$.

Notice that the example above does not preserve cardinals nor cofinalities.

Note: In 1. "$\Rightarrow$" always holfas as $\beta$ is a cardinal iff there is no bijection $f:\alpha \to \beta$ for some $\alpha <\beta$, and $M\subseteq M[G]$ and. being a bijection is absolute between ctm. In 2.  we have $(cf(\gamma ){)}_M=(cf(\gamma ){)}_{M[G]}$ for similar reasons, being a cofinite map is absolute for transitive sets.

In 1. this is true for $p\le \omega$ by absoluteness.

A question we may still have is: why are we interested in $cf$ while $CH$ ahas nothing to do with it?

Lemma: 

1. $\mathbb{P}$ pres. $cf$ iff for all gen. $G$ and limit $\beta$ s.t. $\omega <\beta <o[M]$ then $(\beta$* is reg.*${)}_M\to (\beta$ is reg.${)}_{M[G]}$.

2. If $\mathbb{P}$ preserves $cf$ then $\mathbb{P}$ preserves cardinals.

Proof. check it from the Notes

Definition: let $\mathbb{P}$ be a forcing poset and $A\subset \mathbb{P}$, then $A$ is an antichain iff ${\forall }_{p,q\in A}p\perp q$, namely all elements are pairwise incompatible. $A$ is a maximal antichain iff $A$ is an antichain and there is no $r\in \mathbb{P}\setminus A$ s.t. $\{r\}\cup A$ is an antichain, i.e. ${\forall }_{r\in \mathbb{P}\setminus A}{\exists }_{p\in A}/p\perp r$.

Example: in a tree ordering any level is an antichain and if every node branches then any level is a maximal antichain (watch the notes for a picture).

Example: $\mathbb{P}=Fn(\omega ,k)$ set $p_{\alpha }=\{0,\alpha \}$, then $\{p_{\alpha }|\alpha \in k\}$ is an antichain of size $k$ so it is maximal, $\neg (p_{\alpha }\perp p)=\{(0,\alpha ),(1,\beta )\}$. clear??

Definition: $\mathbb{P}$ has the countable chain condition ($ccc$) iff all antichains in $\mathbb{P}$ are countable, also $\mathbb{P}$ has the $\lambda -cc$ iff all antichains in $\mathbb{P}$ are of size $<\lambda$. Hence $ccc\sim {\omega }_1-cc$.

Example: Consider a binary tree ordering, is it $\omega -cc$? No! Take the binary tree $\{(0,1),(0,0,1),(0,0,0,1),...\}$ is an infinite antichain, it is though a ${\omega }_2-cc$ since the whole tree is countable. uhm...? sus In general notice that $\mathbb{P}$ has the $|\mathbb{P}{|}^{+}-cc$. what is that +?

Lemma: let $I,J\ne \varnothing$, $\mathbb{P}=Fn(I,J)$ has the $ccc$ iff $J$ is countable. If $J$ is infinite, $\mathbb{P}$ has the $|J{|}^{+}-cc$.

Proof on the Notes, it is a huge proof, so I should check it once at least. $\square$

Theorem: If $\mathbb{P}\in M$ and $(\mathbb{P}$ is ccc${)}_M$, then $\mathbb{P}$ preserves cofinalities and hence cardinals.

12th Lecture

I list here 5 numbered lemmas and a theorem, some of them have been proved already here.

Lemma 1. if $G$ is $\mathbb{P}$-generic over $M$ and $M[G]\models \varphi$, $p\in G$, then ${\exists }_{q\in G}q⊩\varphi \wedge q\in p$.

Lemma 2. 

1. $\mathbb{P}$ pres. $cf$ iff for all gen. $G$ and limit $\beta$ s.t. $\omega <\beta <o[M]$ then $(\beta$* is reg.*${)}_M\to (\beta$ is reg.${)}_{M[G]}$.

2. If $\mathbb{P}$ preserves $cf$ then $\mathbb{P}$ preserves cardinals.

Lemma 3. let $I,J\ne \varnothing$, $\mathbb{P}=Fn(I,J)$ is $ccc$ iff $J$ is countable.

Lemma 4. if $\mathbb{P}$ preserves card. and $G$ is $\mathbb{P}$-generic, then ${\forall }_{\alpha ,h<o(M)}M\models k={\aleph }_{\alpha }$ iff $M[G]\models k={\aleph }_{\alpha }$. 

Theorem: if $\mathbb{P}\in M$ and $(\mathbb{P}$ is $ccc$${)}_M$ then $\mathbb{P}$ preserves cofinalities and hence preserves cardinals.

Lemma 5. let $\mathbb{P}\in M$, $(\mathbb{P}$ is $ccc$${)}_M$ and $A,B\in M$, et $G$ be $\mathbb{P}$-generic over $M$ and $f\in M[G]$ with $f:A\to B$. Then there is $F:A\to \mathcal{P}(B)$ s.t. $F\in M$ s.t. for all $a\in A$, then $f(a)\in F(a)$.

It also holds that for each $a\in A$, $(F(a)$is countable${)}_M$

Definition: for an infinite cardinal $k$, a set $J$, we name $col(k,J)$ the forcing poset $\mathbb{P}=\{f:I\to J|I\subseteq k\wedge |I|<k\}$, $\le :=\subseteq$, $1:=\varnothing$. 

Properties of this are: 

• in $col(k,J)$ we find partial functions from $k$ to $J$ of size $<k$

• $col(k,J)$ clearly is a forcing poset

• it is atomless if $|J|\ge 2$

• it is not absolute for $k>\omega$

• $col(\omega ,J)=Fn(\omega ,J)$

So for $M$ a ctm and $G$ a $(col(k,J){)}_M$-generic over $M$, $f_G=\bigcup \{p|p\in G\}$ is a function with domain $k$ and range $J$, then remember the argumetn for $Fn(I,J)$.

$f_G\in M_G$ so $M[G]\models |J|\le |k|$, we’ll use $col({\omega }_1,\lambda )$ where $(\lambda =2^{{\aleph }_0}{)}_M$, $M[G]\models |\lambda |\le |({\omega }_1{)}_M|$ but $\lambda >({\omega }_1{)}_M$, so $({\omega }_1{)}_M<\lambda$ so $M[G]\models |\lambda |=|({\omega }_1{)}_M|$. So, in order to prove $M[G]\models CH$ we now need to show $(2^{{\aleph }_0}{)}_M=(2^{{\aleph }_0}{)}_{M[G]}$ and $({\omega }_1{)}_M=({\omega }_1{)}_{M[G]}$.

Definition: A poset $\mathbb{P}$ is $<k$-closed iff every sequence $⟨p_{\gamma }|\gamma <\alpha ⟩$ of lenght $\alpha <k$ s.t. $\gamma \le \delta <\alpha$, $p_{\delta }\le p_{\gamma }$ has a lower bound, i.e. ${\exists }_{p\in \mathbb{P}}{\forall }_{\gamma <\alpha }p\le p_{\gamma }$.

Lemma: If $k$ is regular $col(k,J)$ is $<k$-closed.

Proof. let $⟨p_{\gamma }|\gamma <\alpha ⟩$ be as above, the conditions in the sequence are over all comparable, so $p:=\bigcup \{p_{\gamma }|\gamma <\alpha \}$ is a partial function. By regularity of $k$, $p$ has size $<k$, thus $p\in col(k,\lambda )$, also $p\le p_{\gamma }$ for each $\gamma <\alpha$ by def. $\square$

Lemma: suppose $(\mathbb{P}$ is $<k$-closed${)}_M$, $G$ is a generic, then every cardinal $\beta \le k$ of $M$ is a cardinal of $M[G]$, i.e. for $\beta \le k$, $(\beta$is a cardinal${)}_M\to (\beta$is a cardinal${)}_{M[G]}$, it preserves only cardinals smaller of a certain $\beta$.

13th Lecture

Definition: a poset $\mathbb{P}$ is $<k$-closed iff every sequence $⟨p_{\gamma }|\gamma <\alpha ⟩$, of lenght $\alpha <k$ s.t. $\gamma \le \delta <\alpha \Rightarrow p_{\delta }\le p_{\gamma }$ has a lower bound, i.e. ${\exists }_{p\in \mathbb{P}}{\forall }_{\gamma <\alpha }p\le p_{\gamma }$.

Lemma 1. if $k$ is regular, $col(k,\lambda )$ is $<k$-closed

Lemma 2. suppose $(\mathbb{P}$ is $<k$-closed${)}_M$, $G$ is $\mathbb{P}$-gen. over $M$, let $\alpha <k$ and $f:\alpha \to \beta$ s.t. $f\subset M[G]$, then $f\in M$.

Corollary: suppose $(\mathbb{P}$ is $<k$-closed${)}_M$, $G$ a $\mathbb{P}$-generic over $M$, then every cardinal $\beta \le k$ of $M$ (i.e.$(\beta$ is a cardinal${)}_M$) is a cardinal of $M[G]$.

Theorem: Let $M$ be a ctm of $ZFC$, $(\lambda =2^{{\aleph }_0}{)}_M$, $(\mathbb{P}=col({\omega }_1,\lambda ){)}_M$ and $G$ a $\mathbb{P}$-generic over $M$, then $M[G]\models CH$.

Note: this theorem brings us from a model of $\neg CH$ ($M$) to a model where $CH$ holds ($M[G]$). The reverse direction, namely from a model of $CH$ to one of $\neg CH$ can be done as preaviously shown by $Fn({\omega }_2\times \omega ,2)$.

Proof. let $f_G={\bigcup }_G$, we know $f_G$ is a surjection form $({\omega }_1{)}^M$ onto $\lambda$ (since we are in the poset $col(\lambda ,{\omega }_1)$). As $\lambda \ge ({\omega }_1{)}^M$ and $f_G\in M[G]$, so $M[G]\models |({\omega }_1{)}^M|=\lambda$. By lemma 1. we know that $(\mathbb{P}$ is $<{\omega }_1$-closed${)}^M$, so, by cor. $({\omega }_1{)}^{M[G]}=({\omega }_1{)}^M$. By lemma 2 we know that for every function $f:\omega \to 2$, s.t. $f\in M[G]$, $f\in M$ thus ${(}^{\omega }2{)}^{M[G]}\subseteq {(}^{\omega }2{)}^M\subseteq {(}^{\omega }2{)}^{M[G]}$, so ${(}^{\omega }2{)}^{M[G]}={(}^{\omega }2{)}^M$. Hence in $M[G]$ we have: $2^{\omega }=|{(}^{\omega }2{)}^M|=|\lambda |=|({\omega }_1{)}^M|=({\omega }_1{)}^{M[G]}$, hence $M[G]\models 2^{\omega }={\omega }_1$ i.e. $M[G]\models CH$.

1. On $col(\lambda ,{\omega }_1)$, take $f_G:={\bigcup }_G:({\omega }_1{)}^M\to \lambda$ surj.

2. Since we have $f_G\in M[G]$ and $f_G$ is surj. and $\lambda \ge ({\omega }_1{)}^M$, then $M[G]\models |({\omega }_1{)}^M=\lambda$.

3. Lemma 1: $(\mathbb{P}$ is $<{\omega }_1$-closed${)}^M$, so, by cor: $({\omega }_1{)}^{M[G]}=({\omega }_1{)}^M$

4. Lemma 2: ${\forall }_{f:\omega \to 2}f\in M[G]\to f\in M$, hence $(2^{\omega }{)}^{M[G]}=(2^{\omega }{)}^M$

5. Then in $M[G]$ we have: $(2^{\omega }{)}^{M[G]}=(2^{\omega }{)}^M$ by above and $(2^{\omega }{)}^M=|\lambda |$ because $\lambda =|\mathbb{R}|$.

6. Also: $|\lambda |=({\omega }_1{)}^M$ by 2. and hence, since we are in $M[G]$ IDK

7. Hence $M[G]\models 2^{\omega }={\omega }_1$. $\square$

There is a recap with the bigger picture of the whole procedure on the Notes, there is not much advantage in writing all of this down here again, since some things are just not relevant for the exam and other are clearer on the sheet.

Claim (trivial)

By lemma 1. in Lecture 13 we know that for $k$ regular then $col(k,J)$ is $<k$-closed, i.e. all decreasing sequences of cardinality less than $k$ are bounded. No decreasing sequence in $col(k,J)$ can be longer than $k$, since the longest would start from $\varnothing$ and start mapping elements in $k$, at most $k$ can get mapped, hence we can state:

Lemma 1. All decreasing sequences in $col(k,J)$ are bounded.

Since $col(k,J)$ is a partial order where every chain (decreasing sequence) is bounded, we can apply the Zorn’s lemma and find out that:

Lemma 2. ${\exists }_{l\in col(k,J)}\neg {\exists }_{p\in col(k,J)}k\le l$.

This element has no reason to be unique though. In order to get some sort of uniqueness we would need the partial order to be “downward directed”, namely, for a forcing poset $\mathbb{P}$:

Lemma 3. If every chain in $\mathbb{P}$ has an lower bound and ${\forall }_{x,y\in \mathbb{P}}{\exists }_{z\in \mathbb{P}}x\ge z\wedge y\ge z$ holds then the least element $l$ is unique.

Proof. here $\square$

We get this exact kind of structure, by definition, in a filter, in fact:

Lemma 4. If $G$ is a filter and all decreasing sequences are bounded, then there is a unique least element.

Recall that the first condition for $G$ to be a filter is ${\forall }_{p,q\in G}{\exists }_{r\in G}r\le q\wedge r\le p$, 

Lemma 5. Let $G$ be a filter in $col(k,J)$ then there exists a unique least element $l$.

Proof. By lemma 1. we see that every sequence in $G$ must be lower bounded too, then we apply lemma 4. $\square$

This result shows that for every chosen generic $G$, there will be one element only which carries all informations of the generic, this is the case since we know that $(l\le p\wedge p⊩\varphi )\to l⊩\varphi$. Then:

Theorem Let $G$ be $col(k,J)$-gen. then there is a unique $l\in G$ s.t. $M[G]\models \varphi \leftrightarrow l⊩\varphi$.

"$\Rightarrow$" If $M[G]\models \varphi$, then by $TL$ there is a $p\in col(k,J)$ s.t. $p⊩\varphi$. There is a unique least element by lemma 5., and since $l\le p$ we know $l⊩\varphi$.

"$\Leftarrow$" If $l⊩\varphi$, since $l\in G$ by $TL$ we have $M[G]\models \varphi$. $\square$

In conclusion we notice that for two $col(k,J)$-generics, $G$ and $H$ and the respective least elements $l_G$ and $l_H$, we have $M[G]=M[H]$ iff $l_G=l_H$.

Those elements for $col(k,J)$ simply are what we denote with $f_G:={\bigcup }_G=l_G$ and their prove of both existence and uniqueness are far more trivial if done in the classical sense. My theorem could be a generalisation but it is probably even simpler to just prove it by imagining how a filter looks like instead of going through this harder process.

If we think about $\mathbb{P}:=Fn(I,J)$, we could notice that all generics can be identified with complete functions and therefore we could simply take any complete function and consider them to be those that generate the $M[G]$ since they force the set of all (and only those by $TL$) propositions that are true in $M[G]$.

Check Exam

Hazel Mail

Now regarding the content of the exam. The focus will be on understanding of the concepts in the course and general structure of the arguments. Thus I will mostly be asking only for sketch proofs - you do not need to learn any proofs given in the lectures in detail (I may ask for an easy, short proof to demonstrate understanding of some concepts/definitions, but that is something you should be able to do on the spot).  

I will ask you to give at least one explicit definition, such as inaccessible cardinal, (in)compatibility, dense set, filter, generic filter, ccc, <\kappa-closed, p forces phi… You do NOT need to know the definition of the forcing* relation (the one defined recurcively), but you should know the role of this definition in the proof of the Truth and Definability lemmas - i.e. that it is definable within M and we can prove that p forces* phi iff p forces phi (you don’t need to know anything about the proof of this equivalence). You should know the statements of the Truth and Definability lemmas, and be able to give an informal description of the Downward-Löwenheim-Skolem Theorem, Mostovski-Shepherdson Collapse, and Montague-Levy Reflection (these latter three are a bit technical to state correctly, so I won’t ask for a precise statement). Importantly, you should know the role of these results in the proof of the independence of CH from the existence of an inaccessible cardinal, as we discussed in the last lecture.   

I will set a few exercises (computation or simple proofs), such as relativising a formula to a set, showing a formula is absolute for transitive sets, showing a set is dense, giving the valuation of a name etc. I will also ask for at least one sketch proof, such as using forcing to produce a model of not-CH from a ctm of CH or vice-versa. You should then give the relevant definitions and main lemmas/theorems (such as on preserving cardinals) and how they fit together.

Question to myself

Definitions

Question 1. Define inaccessible cardinal

• inacc. from smaller cardinals trough: $+/\cup$, $\cdot /\times$, $func$.

• strongly inacc. if (i) $k\ge {\aleph }_0$, (ii) is inacc. (iii) $\alpha <k\to 2^{\alpha }<k$.

• For an inacc. cardinal $k$, $(V_k,\in )\models ZFC$.

• from K: weakly inacc. if $k$ is a regular limit cardinal

• strongly inacc. if $k>\omega$, $k$ is reg., ${\forall }_{\lambda <k}{2}^{\lambda }<k$.

• if $\beta$ is a successor, then $cf(\beta )=1$

• reg. if $\beta$ is a lim. ord and $cf(\beta )=\beta$.

• $GCH:={\forall }_{\alpha }{2}^{{\omega }_{\alpha }}={\omega }_{\alpha +1}$.

Question 2. Define (in)compatibility

• Def. $\mathbb{P}$

• if ${\exists }_{r\in \mathbb{P}}r\le p\wedge r\le q$ then $p\perp q$.

• Atom, Atomless definitions and examples, [[Advanced Set Theory (Lecture)#5th Lecture#Definitions]]

Question 3. Define a dense set

• iff ${\forall }_{p\in \mathbb{P}}{\exists }_{q\in D}q\le p$.

• $D_i:=\{p\in \mathbb{P}|i\in dom(P)\}$ is a dense set in $Fn(I,J)$ for $I$ infinite.

• goto: filter, gen. filter

Question 4. Define a filter

• (i) ${\forall }_{p,q\in G}{\exists }_{r\in G}r\le q\wedge r\le p$, (ii) ${\forall }_{p\in G}{\forall }_{q\in \mathbb{P}}q\le p\to q\in G$.

• $p,q\in G$ then $p$ and $q$ agree on $dom(p)\cap dom(q)$.

Question 5. Define a generic filter

• ${\forall }_{D\subset \mathbb{P}\wedge D\text{ dense}}D\in M\to G\cap D\ne 0$.

• Existence Lemma + Proof.

Question 6. Define the $ccc$ property

• def. antichain, all antichains are countable, examples

• $|J|\le \omega \to Fn(I,J)$ has $ccc$.

• if $\mathbb{P}\in M$ and $(\mathbb{P}$ has $ccc{)}^M$, then $\mathbb{P}$ preserves cofinalities and hence cardinals

Question 7. Define the $<k$-closed property

• iff all sequence in $\mathbb{P}$, are $⟨p_{\gamma }|\gamma <\alpha ⟩$ of length $\alpha <k$ s.t. $\gamma \le \delta <\alpha$, $p_{\delta }\le p_{\gamma }$ has a lower bound, i.e. ${\exists }_{p\in \mathbb{P}}{\forall }_{\gamma <\alpha }p\le p_{\gamma }$.

• If $k$ is regular $col(k,J)$ is $<k$-closed.

Question 8. Define $\mathbb{P}$-names

• $\tau$ is a $\mathbb{P}$-name iff $\tau$ is a relation s.t. ${\forall }_{(\sigma ,p)\in \tau }\sigma$ is a $\mathbb{P}$-name $\wedge p\in \mathbb{P}$.

• Define $V^{\mathbb{P}}$ and $M^{\mathbb{P}}$.

Question 9. Define $p⊩\varphi$

• so $p{⊩}_{\mathbb{P},M}\varphi ({\tau }_1,...,{\tau }_n)$ iff ${\forall }_{G\mathbb{P}\text{-gen. }\wedge p\in G}{\varphi }^{M[G]}(val({\tau }_1,G),...,val({\tau }_n,G))$

• If $p⊩\varphi$ and $q\le p$ then $q⊩\varphi$ & proof

• goto: TL

Question 10. Define $M[G]$.

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

For $M[G]$ it holds:

1. $M\subset M[G]$

2. $G\in M[G]$

3. $M[G]$ is countable and transitive

4. $M[G]\models ZFC$

5. $M[G]$ is minimal (for any set $N$ with the above features we have $M[G]\subset N$)

General questions

Question 1. What is the role of $p{⊩}^{\ast }\varphi$ in DL and TL, give an approximate definition

• $M[G]\models \psi$ there is a $p\in G$ s.t. $p⊩\psi$

• $\Rightarrow$ is ez from def of "$⊩$". 

• $\{(p,\mathbb{P},\le ,1,{\theta }_1,...,{\theta }_n)|(\mathbb{P},\le ,1)\text{ is a forcing poset }\wedge p\in \mathbb{P}\wedge {\theta }_1,...,{\theta }_n\in M^{\mathbb{P}}\wedge p{⊩}_{M,\mathbb{P}}\varphi ({\theta }_1,...,{\theta }_n)\}$is definable without parameters in $M$.

We need ${⊩}^{\ast }$ in order to define within $M$ the forcing relation, it would otherwise require knowledge of every generic.

Question 2. Give the context of the equivalence $p⊩\varphi \iff p{⊩}^{\ast }\varphi$, no proof required

We showed:

• if $p\in G$ and $p{⊩}^{\ast }\varphi$ then $M[G]\models \varphi$

• if $M[G]\models \varphi$ then there is some $p\in G$ s.t. $p{⊩}^{\ast }\varphi$ 

and hence the equivalence follows

Question 3. State and give context to both TL and DL, what are they for?

• $M[G]\models \psi$ there is a $p\in G$ s.t. $p⊩\psi$, defines truth of forcing from a given $p$.

• The DL states then that every forcing relation can be defined without parameters in $M$.

Question 4. State and give context to the Downward Löwenheim-Skolem Theorem

• for inf. $\mathcal{M}$ and inf. $|M|\ge k\ge |\mathcal{L}|$ then exists $\mathcal{N}$ s.t. $|N|=k$, $\mathcal{N}\subseteq M$.

• Proof in 3 steps

• we need this theorem to find a $M$ s.t. it gives us all $\varphi$ are absolute in $M$. This is hence a model of any finite subset of $ZFC$, though some defs are not absolute, like infinity.

Question 5. State and give context to the Mostowski Collapse Theorem

• an extensional relation is $R$ s.t. ${\forall }_{x,y\in A}{\forall }_{z\in A}(zRx\leftrightarrow zRy)\to x=y$

• For $W$, a rel. $R$ on $W$ ext., exists a unique tran. set $M$ and an isom. $\pi :(W,R)\cong (M,ϵ)$.

Question 6. State and give context to the Montague Reflection Theorem

• $ZF⊢{\forall }_{\alpha }{\exists }_{\beta >\alpha }({\varphi }_1,...,{\varphi }_n$ are absolute for $V_{\beta })$.

• Tarski Vaught Test: ${\forall }_{y_1,...,y_l\in M}({\exists }_{x\in N}{\varphi }_j^N(x,y_1,...,y_l)\to {\exists }_{x\in M}{\varphi }_j^N(x,y_1,...,y_l))$

Question 7. State approximately the procedure from the existence of an inacc. cardinal to CH

Pars $I$

1. Define $Fn(I,J)$, $|I|\ge \omega$, $J\ne \varnothing$.

2. $...\to dom({\bigcup }_G)=I\wedge ran({\bigcup }_G)=J$

3. Set $\mathbb{P}=Fn(k\times \omega ,2)$, ${\bigcup }_G:k\times \omega \to 2$, $f_{\alpha }(n):={\bigcup }_G(\alpha ,n)$

4. $\{f_{\alpha }|\alpha <k\}\in M[G]$ by abs.

5. $D_{\alpha ,\beta }$ is dense

6. $G\cap D_{\alpha ,\beta }\ne \varnothing$, hence $f_{\alpha }\ne f_{\beta }$ 

7. Then we have $(2^{\omega }\ge |k|{)}^{M[G]}$

Pars $II$

1. Define $ccc$ 

2. $|J|\le \omega \to F(I,J)$ has $ccc$

3. Def. preserves cardinals

4. Def. preserves cofinalities

5. cof $\to$ card

6. $...\to$ cof

7. $(\mathbb{P}$ has $ccc{)}^M$ pres. cof and card

Pars $III$

$\mathbb{P}:=({\omega }_2^M\times \omega ,2)$ has $ccc$, hence ${\omega }_2^M={\omega }_2^{M[G]}$, hence $(2^{\omega }\ge {\omega }_2{)}^{M[G]}$, hence $M[G]\models \neg CH$.

Question 8. When do we say that we preserve cardinals?

see. 2. ibid

Exercises

Question 1. Show some $\varphi$ relativized to some set $M$.

Care about existentials and forall only, the rest is the same

Question 2. Show some $\varphi$ absolute for any transitive set

Remember the definition of ${\Delta }_0$, if $FV(\varphi )=\varnothing$, then it is absolute for transitive sets. Else, for $FV(\varphi )=x_1,...,x_n$ you need to compute ${\varphi }^M$ and then show that ${\forall }_{x_1,...,x_n}{\varphi }^M\leftrightarrow \varphi$.

Question 3. Show some set $x$ to be dense.

Simply that ${\forall }_{p\in \mathbb{P}}{\exists }_{d\in x}d\le p$, with $Fn(I,J)$ think about the extensions of functions

Question 4. Give the valuation to some name $\tau$

Remember that $p\in G\to \{(\sigma ,p){\}}_G=\sigma$ and $p\notin G\to \{(\sigma ,p){\}}_G=\varnothing$.

Question 5. Use forcing to produce a model of $\neg CH$ from a ctm of $CH$ and reverse

Let $M$ be a ctm of $ZFC$, $(\lambda =2^{{\aleph }_0}{)}_M$, $(\mathbb{P}=col({\omega }_1,\lambda ){)}_M$ and $G$ a $\mathbb{P}$-generic over $M$, then $M[G]\models CH$. This theorem brings us from a model of $\neg CH$ ($M$) to a model where $CH$ holds ($M[G]$). The reverse direction, namely from a model of $CH$ to one of $\neg CH$ can be done as preaviously shown by $Fn(\omega \times {\omega }_2,2)$.