1

Suppose \(\kappa\) is an infinite cardinal. Let \({\mathbb{P}}= \operatorname{Fn}(\kappa,\omega)\). Show that every antichain in \({\mathbb{P}}\) is countable.

Let \(A\subseteq {\mathbb{P}}\) be an uncountable antichain, we derive a contradiction as follows. Note that for any antichain \(A\) we have, for all \(f,g\in A\), \[ \left(\exists \alpha\in\operatorname{dom}(f)\cap\operatorname{dom}(g)\right)\left(f(\alpha) \ne g(\alpha)\right). \] Consider the domains of the partial functions \(D = \left\{\operatorname{dom}(f): f\in A\right\}\). Note that \(D\) cannot be countable, otherwise \(A\) will be a countable union of countable sets. Now without loss of generality refine \(A\) such that \(D\) is a \(\Delta\)-system. Using choice, we can refine \(A\) again such that for each \(x\in D\), there is exactly one \(f\in A\) with \(\operatorname{dom}(f) = x\). Note that \(A\) is still an uncountable antichain.

Let \(r\in \left[\kappa\right]^{<\omega}\) be the root of \(D\), and being the root, every function in \(A\) is total on \(r\). We claim that \(r \ne 0\) and every function \(f\in A\) is determined completely by its values on \(r\). Let \(f,g\in A\) with \(f\ne g\) and since \(D\) is a sunflower, \(\operatorname{dom}(f)\cap \operatorname{dom}(g) = r\). Nonemptiness arises from the existence of a witness from \(\operatorname{dom}(f)\cap\operatorname{dom}(g)\). Also if \(f\upharpoonright r = g\upharpoonright r\), then they would have a common extension which cannot happen. This means that \(\left\lvert A\right\rvert \leq \omega^\left\lvert r\right\rvert = \omega\).

2

Suppose \(\mathbf{M}\) is a ctm of ZFC, \({\mathbb{P}}\) is a poset in \(\mathbf{M}\), \(G\subseteq {\mathbb{P}}\) and \(1_{\mathbb{P}}\in G\).

1. Show that \(\mathbf{M}[G]\) is transitive and hence it satisfies the axiom of extensionality.

We have \(\mathbf{M}[G] = \left\{\tau[G]: \tau\in\mathbf{M}^{\mathbb{P}}\right\}\). Let \(\tau\in\mathbf{M}^{\mathbb{P}}\) such that \(\tau[G]\in \mathbf{M}[G]\), we want \(\tau[G] \subseteq \mathbf{M}[G]\). Let \(x\in \tau[G]\) and from the definition there exists \(p\in {\mathbb{P}}, \sigma\in\mathbf{V}^{\mathbb{P}}\) such that \((\sigma, p)\in\tau\) and \(x = \sigma[G]\). Since \(\tau\in\mathbf{M}\) and \(\mathbf{M}\) is transitive it follows that \(\sigma\in\mathbf{M}\), so \(\sigma\in\mathbf{M}^{\mathbb{P}}\) which by definition of \(\mathbf{M}[G]\) means \(x = \sigma[G] \in \mathbf{M}[G]\).

2. Show that \(o(\mathbf{M}[G]) = o(\mathbf{M})\).

As \(\mathbf{M}\subseteq \mathbf{M}[G]\) we only need to show \(o(\mathbf{M}[G]) \leq o(\mathbf{M})\). We show that for any \(\tau[G] \in \mathbf{M}[G]\), \(\operatorname{rank}(\tau[G]) \leq \operatorname{rank}(\tau)\), the height bound will follow from this result.

Let \(\tau\in \mathbf{M}^{\mathbb{P}}\), then \(\tau[G] = \left\{\sigma[G]: \left(\exists p\in G\right)\left((\sigma,p)\in\tau\right)\right\}\) and by computing rank we have \[\operatorname{rank}(\tau[G]) = \sup\left\{\operatorname{rank}(\sigma[G])+1: \left(\exists p\in G\right)\left((\sigma,p)\in\tau\right)\right\} \] by induction whenever \((\sigma,p)\in\tau\), we have \(\operatorname{rank}(\sigma[G]) \leq \operatorname{rank}(\sigma) < \operatorname{rank}(\tau)\) and the resultant bound follows.

3. Show that \(\mathbf{M}[G]\) satisfies the axioms of pairing, union and foundation.

For pairing, let \(\sigma[G], \tau[G]\in\mathbf{M}[G]\). Let \(\pi = \left\{(\sigma, 1_{\mathbb{P}}), (\tau, 1_{\mathbb{P}})\right\}\) which is clearly a \({\mathbb{P}}\)-name. Note that \(\pi\in\mathbf{M}^{\mathbb{P}}\) too as pairing holds in \(\mathbf{M}\). It then follows from definitions and fact that \(1_{\mathbb{P}}\in G\) that \(\pi[G] = \left\{\sigma[G], \tau[G]\right\}\).

For union, let \(\tau[G]\in\mathbf{M}[G]\). Define \[ \pi = \bigcup\left\{\sigma:\left(\exists p\in G\right)\left((\sigma,p)\in\tau\right)\right\} \] and since Union holds in \(\mathbf{M}\), \(\pi\in\mathbf{M}^{\mathbb{P}}\). Evaluating \(\pi[G]\) we have \[ \pi[G] = \left\{\sigma_0[G]: \left(\exists p_0\in G\right)\left((\sigma_0,p_0)\in\pi\right)\right\} \] expanding gives \[ \pi[G] = \left\{\sigma_0[G]: \left(\exists p_0\in G, p\in G, \sigma\right)\left((\sigma_0,p_0)\in\sigma \land (\sigma, p)\in\tau\right)\right\}.\] We now inspect \(\bigcup\tau[G]\), \[\bigcup\tau[G] = \left\{x: \left(\exists y\in\tau[G]\right)\left(x\in y\right) \right\}\] unrolling what it means for \(y\in\tau[G]\) we rewrite as \[\bigcup\tau[G] = \left\{x: \left(\exists p\in G, \sigma\right)\left((\sigma, p)\in\tau\land x\in \sigma[G]\right) \right\}\] and unfolding the definition of \(x\in \sigma[G]\) will make clear the fact that \(\bigcup\tau[G] = \pi[G] \in\mathbf{M}[G]\).

Foundation holds in any transitive class.

3

Suppose \(\mathbf{M}\) is a ctm of ZFC and \({\mathbb{P}}\) is a poset in \(\mathbf{M}\). Assume that every condition in \({\mathbb{P}}\) has two incompatible extensions. Show that there exists a filter \(G\) on \({\mathbb{P}}\) such that \(\mathbf{M}[G]\) is not a model of ZFC.

Fix a well-order on \({\mathbb{P}}\), and by recursion on \(2^*\) define a labelling of some elements of \({\mathbb{P}}\) as follows, \(p_{\varepsilon} = 1_{\mathbb{P}}\) and when \(w\in 2^*\), let \(q,r\in{\mathbb{P}}\) with \(q\ne r\), \(q,r\leq p_w\) and \(q\perp r\), then \(p_{w0} = \min\left\{q,r\right\}\) and \(p_{w1} = \max\left\{q,r\right\}\), where \(\varepsilon\) denotes the empty string and \(2^*\) denotes all finite sequences over \(2\). Let \(R\) denote the set of all labelled elements in \({\mathbb{P}}\) and for each \(\omega\)-sequence \(s\in 2^\omega\), it is natural to associate \(s\) with a filter in \({\mathbb{P}}\), specifically let \(f(s)\) be the upward closure of \(\left\{p_{s\upharpoonright n}: n\in\omega\right\}\). Let \(s\in 2^\omega\) be arbitrary and we show that \(f(s)\) is a filter. We have \(1_{\mathbb{P}}= p_{s\upharpoonright 0} \in f(s)\). Given \(n,n'\in\omega\), by our labelling it follows that \(p_{s\upharpoonright \max(n,n')} \in f(s)\) extends both \(p_n, p_{n'}\). The last condition is free because we took upward closure.

Let \(\gamma = o(\mathbf{M})\) and let \(X\subseteq \omega^2\) be a well order of \(\omega\) with \(\operatorname{type}(\omega,X) > \gamma\). Let \(\pi: \omega^2\to\omega\) denote the Cantor pairing function which is primitive recursive. Let \(g\) be the composition \[ \mathcal{P}(\omega^2) \xrightarrow{\operatorname{Im}_\pi} \mathcal{P}(\omega) \xrightarrow{\chi} 2^\omega \xrightarrow{f} \mathcal{P}({\mathbb{P}}) \] where \(\chi\) denotes the characteristic function. Let \(G = g(X)\) which is a filter on \({\mathbb{P}}\), then \(G\in \mathbf{M}[G]\).

Suppose for a contradiction \(\mathbf{M}[G]\) is a model of ZFC, then \(f^{-1}(G) \in \mathbf{M}[G]\) (note that \(f\) is one-one). This is due to \(\mathbf{M}\subseteq \mathbf{M}[G]\) already containing the labelling map \(w\mapsto p_w\) which is also one-one, then applying the inverse of labelling to \(G\cap R\) gives us a subset of \(2^*\) where for every pair of strings, the shorter one is an initial segment of the longer one. Taking its union will uniquely identify an \(\omega\)-sequence, which can be checked to be \(f^{-1}(G)\). We can also reverse \(\chi\), given an \(\omega\)-sequence we just look at \(\left\{n: (n,1)\in s\right\}\). Taking image of \(\pi\) is reversible too as \(\pi\) is primitive recursive and hence definable. This means \(g^{-1}(G) = X \in \mathbf{M}[G]\), then as \(\omega\in\mathbf{M}[G]\) it follows that \(\operatorname{type}(\omega,X) \in \mathbf{M}[G]\) which contradicts part (b) of question 2.

4

Suppose \(\mathbf{M}\) is a ctm of ZFC and \({\mathbb{P}}\) is a poset in \(\mathbf{M}\). Let \(G\) be a filter on \({\mathbb{P}}\). Prove that \(G\) is \({\mathbb{P}}\)-generic over \(\mathbf{M}\) iff for every maximal antichain \(A\subseteq{\mathbb{P}}\), if \(A\in\mathbf{M}\), then \(G\cap A\ne 0\).

Let \(G\) be \({\mathbb{P}}\)-generic over \(\mathbf{M}\) and let \(A\in\mathbf{M}\) be a maximal antichain of \({\mathbb{P}}\). Let \(D = \left\{p:\left(\exists a\in A\right)\left(p\leq a\right)\right\}\) and note that \(D\in\mathbf{M}\) and is dense. As \(G\) is generic \(G\cap D \ne 0\), then by upward closure of \(G\) we have \(G\cap A\ne 0\).

Conversely suppose for every maximal antichain \(A\subseteq{\mathbb{P}}\), if \(A\in \mathbf{M}\) then \(G\cap A \ne 0\). Let \(D\subseteq {\mathbb{P}}\) be dense and assume \(D\in \mathbf{M}\). By choice let \(A\in \mathbf{M}\) be a maximal antichain of \(D\), the result will follow if \(A\) is also a maximal antichain of \({\mathbb{P}}\).

By being a maximal antichain in \(D\), it holds that \[\left(\forall p'\in D\right)\left(p'\in A \lor \left(\exists q\in A,r\in D\right)\left(r\leq p'\land r\leq q\right)\right), \] and we want to show that \(A\) is a maximal antichain in \({\mathbb{P}}\), that is \[\left(\forall p\in {\mathbb{P}}\right)\left(p\in A \lor \left(\exists q\in A,r\in {\mathbb{P}}\right)\left(r\leq p\land r\leq q\right)\right). \] Let \(p\in{\mathbb{P}}\), if \(p\in A\) we are done. In the other case as \(D\) is dense let \(p'\in D\) such that \(p' \leq p\). Case \(p' \in A\), then we satisfy the condition with witnesses \(q,r\) both set to \(p'\). In the only remaining case there exists \(q\in A, r\in D\) such that \(r\) is a common extension of \(p'\) and \(q\), then \(r\leq p\) too and the result follows.