# Forcing as a replacement of induction and diagonal arguments

Let me give some examples motivating the question.

The use of forcing instead of induction: For this consider Cantor's theorem:

Theorem 1. Any two countable dense linear orders $I, J$ without end points are order isomorphic.

Proof. Let $\mathbb{P}$ be the partial order consisting of partial finite order preserving maps from $I$ to $J$. For $i\in I, j\in J$ the sets $D_i=\{ p: i\in dom(p)\}$ and $R_j=\{p: j\in range(p) \}$ are dense, and since we have only countably many dense sets, we can get a filter $G$ which meets all of these dense sets. Then $\bigcup G: I \to J$ is the required isomorphism.

The use of forcing instead of diagonal arguments: This time let's consider another result of Cantor:

Theorem 2. For any regular cardinal $\kappa, 2^\kappa > \kappa.$

Proof. Let $F$ be a family of functions from $\kappa\to 2$ of size $\kappa.$ Let $Add(\kappa, 1)$ be the Cohen forcing for adding a new subset of $\kappa,$ and for $f\in F,$ let $D_f=\{p: p\neq f \}.$ Each $D_f$ is easily seen to be dense in $Add(\kappa, 1)$, and since the forcing is $\kappa-$closed, there is an $F-$generic filter $G$ over $Add(\kappa, 1).$ Then $\bigcup G: \kappa \to 2$ is different from all $f\in G.$

Theorem 3. If $\lambda=cf(\kappa) < \kappa,$ then $\kappa^\lambda > \kappa.$

Proof. Let $F$ be family of size $\kappa$ of functions from $\lambda\to \kappa.$ Let $\mathbb{P}=\{p:p$ is a partial function of size $<\lambda$ from $\lambda\to \kappa \}.$ It is $\lambda-$closed. Let $(\kappa_\alpha: \alpha<\lambda)$ be increasing cofinal in $\kappa,$ let $F_0 \subseteq F_1 \subseteq ... (\alpha<\lambda)$ with $|F_\alpha|=\kappa_\alpha$ and $F=\bigcup_\alpha F_\alpha.$ Now consider dense sets $D_\alpha=\{p: \forall f\in F_\alpha, p\neq f \}.$ If a filter $G$ meets all $D_\alpha$'s, then $\bigcup G$ is different from all elements of $F$.

Below are a few more examples of the results that can be proved in a similar way:

(A) If $\mathcal{A}$ and $\mathcal{B}$ are countable families of subsets of $\mathbb{N}$ such that $A \cap B$ is finite for each $A\in \mathcal{A}$ and $B\in \mathcal{B}$, then there is a $C$ such that $A \subseteq^* C$ for every $A\in \mathcal{A}$ and $B\cap C$ is finite for every $B\in \mathcal{B}.$

(B) There exists a continuous, nowhere dieffrentiable function on $[0,1].$

(C) Let's call a set $A$ of natural numbers (not including 0) is small, if $\Sigma_{n\in A}1/n < \infty.$ Given a countable family $\mathcal{F}$ of small sets, there exists a small set $J$ such that $I\subseteq^* J,$ for all $I\in \mathcal{F}.$

(ِِD) All consequences of $MA(\aleph_0),$ in particular the Baire category theorem,....

Question. Are there any more non-trivial results which are proved using forcing in the following way: we produce a forcing notion $\mathbb{P}$ and a family $\mathcal{D}$ of dense subsets of it. Then we argue that there must be a $\mathcal{D}-$generic filter $G$ over $\mathbb{P},$ and use $G$ to conclude our required result.

• Note that Theorem 2 is a corollary of Theorem 3, if you (1) allow $\lambda=\kappa$ and note that $2^\kappa=\kappa^\kappa$ for infinite cardinals. – Asaf Karagila Jan 7 '15 at 22:49
• @MohammadGolshani: I love your examples, especially the use of $Add$$($$\kappa$,$1$$)$ to produce a set that diagonalization ordinarily produces. A question: given Krpipke-Platek ($KP$)+$Infinity$+$\Sigma_n$-separation +$\Sigma_n$-collection,is there,in that theory, enough set theory to define notions of forcing that can add generic sets to its models? My idea (good, bad, or indifferent) is that using the aforementioned theory as a starting point, then see if there is a forcing axiom that can be added to it that will essentially derive Powerset (or actually something more powerful) – Thomas Benjamin Jan 14 '15 at 12:36
• A terminological question/remark: is this really forcing ur just an application of existence of generic filters? By "forcing" I understand the whole rigamarole of building models (usually of ZF). These examples seem like a very good introduction to generic filters, so students can see them first without the model-building machinery. – Andrej Bauer Jan 14 '15 at 14:08
• @ThomasBenjamin Unfortunately I almost know nothing about such theories, but I think some papers by Adrin Mathias give the almost minimal assumption we need to apply forcing. – Mohammad Golshani Jan 15 '15 at 8:26
• @AndrejBauer I think it is quite common to teach forcing in the way you suggest, by first teaching MA, which involves generic filters in just the manner of this question, without the additional burden of forcing names and model-construction. Under MA, one gets a facility with the power of $\cal D$-generic filters and how they can be used. I think most set-theorists view that as the proto-essence of forcing, and MA is usually described as a forcing axiom, even though it is about generic filters rather than building models. – Joel David Hamkins Mar 8 '15 at 14:26

Cantor's back-and-forth theorem quoted in the OP has a model-theoretic generalization.

If two $\tau$--structures $A$ and $B$ in a vocabulary $\tau$ are partially isomorphic, then there is a forcing extension in which they are isomorphic.

If $A$ and $B$ are partially isomorphic countable $\tau$--structures in a countable vocabulary $\tau$, then $A \simeq B$.

In particular, if $A$ and $B$ are $L_{\infty \omega}$--equivalent and countable, then $A \simeq B$.

Several interesting results first proved by forcing are also listed in the answers to the question: https://mathoverflow.net/a/53887/57583

I found the following proof of Ramsey's theorem:

Theorem. If $f: [\omega]^2 \rightarrow 2,$ then there are an infinite $A \subseteq \omega$ and $i<2$ such that for all $\{m,n\}\in [A]^2, f(m,n)=i.$

Let $\mathbb{P}$ be the set of all triples $p=(i_p, m_p, H_p)$, such that:

1) $i_p<2$,

2) $m_p\in \omega,$

3) $H_p \subseteq \omega$ is infinite, $m_p\notin H_p,$

4) For all $n\in H_p, f(m_p,n)=i_p.$

Given $p, q\in \mathbb{P},$ let $p < q$ iff $H_p \supseteq H_q\cup \{m_q\}.$

For each $n<\omega,$ set $D_n=\{p\in \mathbb{P}:m_p > n \}.$

Claim. Each $D_n$ is a dense subset of $\mathbb{P}.$

Proof. Let $p\in \mathbb{P}.$ We may suppose that $m_p\leq n,$ as otherwise we are done. Let $k\in H_p, k>n$, and let $X=\{\{k,m\}:m\in H_p \}.$ Then $X$ is infinite, and hence for some $i<2,$ the set $X_i=\{ \{k,m\}\in X: f(k,m)=i \}$ is infinite. Thus $H=\{ m: \{k,m\}\in X_i \}$ is also infinite. Let $q=(i, k, H).$ Then $q\in \mathbb{P}, q\leq p,$ and $m_q=k>n,$ so $q\in D_n.$ $\Box$

Let $p_o > p_1 > \dots > p_n > \dots$ be a decreasing sequence of conditions in $\mathbb{P}$, with $p_n\in D_n$ and let $i<2$ be such that $B=\{n<\omega: i_{p_n}=i \}$ is infinite. Set $A=\{m_{p_n}: n\in B \}.$ We show that $A$ and $i$ are as required.

Clearly $A$ is infinite. Now suppose that $n_1 < n_2$ are in $B$. Then $p_{n_2} < p_{n_1},$ so $m_{p_{n_1}}\in H_{p_{n_2}},$ hence $f(m_{p_{n_1}}, m_{p_{n_2}})=i_{p_{n_2}}=i.$

• very nice example! – Rahman. M Apr 6 '15 at 6:29

There is a forcing proof of Sierpinski's theorem that $\mathbb{Q}$ with its usual topology is the unique countable, metrizable space without isolated points. The argument is analogous to the proof of Cantor's theorem given in the OP. In both cases, one uses a forcing poset to mimic a back-and-forth construction.

Theorem (Sierpinski). If $X$ and $Y$ are countable, metrizable spaces without isolated points, then $X$ is homeomorphic to $Y$.

Proof. Fix metrics for $X$ and $Y$. Since these spaces are countable, most of their closed balls are also open. Hence we may fix a base of clopen sets $\langle O_i: i \in \omega \rangle$ for $X$ and similarly $\langle N_j: j \in \omega \rangle$ for $Y$. The idea is to define a poset whose conditions approximate some bijection $h: X \rightarrow Y$, and arranges that $h[O_i]$ will be open in $Y$ and $h^{-1}[N_j]$ will be open in $X$ for every $i,j$.

Let $\mathbb{P}$ be the poset with conditions of the form $(f, m, P, Q)$, where

• $P$ is a finite partition of $X$ into clopen sets,
• $Q$ is a finite partition of $Y$ into clopen sets with $|Q| = |P|$,
• $m$ is a bijection of $P$ with $Q$,
• $f$ is a finite partial injection from $X$ into $Y$ that respects the matching $m$ (i.e. if $x \in$ dom($f$) and $p$ is the unique piece of the partition $P$ containing $x$, then $f(x)$ is in $m(p)$).

A condition $(f', m', P', Q')$ extends $(f, m, P, Q)$ if $P'$ refines $P$, $Q'$ refines $Q$, $m'$ refines $m$ (in the obvious sense), and $f'$ extends $f$.

I claim that for every $x \in X$, $y \in Y$, and $i, j \in \omega$, the set of conditions $D_{x, y, i, j} = \{(f, m, P, Q)$: $x \in$ dom($f$), $y \in$ ran($f$), $O_i$ is a union of pieces in $P$, $N_j$ is a union of pieces in $Q\}$, is dense in $\mathbb{P}$. To see this, fix a condition $(f, m, P, Q)$. Given $x \not \in$ dom($f$), there is a unique piece $p_x$ in $P$ containing $x$. Since $Y$ is without isolated points, $m(p_x)$ is infinite. Pick $z \in m(p_x)$ not already in ran($f$). Similarly, given $y \not \in$ ran($f$), we may find $w \in m^{-1}(q_y)$ not already in the dom($f$), where $q_y$ is the unique piece of $Q$ containing $y$. Then $f' = f \cup \{(x, z), (w, z)\}$ extends $f$ and still respects $m$.

Now, any fixed $O_i$ splits every partition piece $p$ into two clopen sets, $p_1 = O_i \cap p$ and $p_2 = (X \setminus O_i) \cap p$. Let $P'$ be the partition consisting of all sets of this form (ignoring those intersections which are empty). Then $P'$ refines $P$ and $O_i$ is a union of elements in $P'$. We must find a matching refinement of $Q$. Given $q \in Q$ we have $q = m(p)$ for some $p \in P$. We split $q$ into two pieces $q_1$ and $q_2$ as follows. If $p_1 = p$ and $p_2 = \emptyset$, let $q_1 = q$ and $q_2 = \emptyset$. And vice versa. Now suppose both $p_1$ and $p_2$ are nonempty. If dom($f'$) $\cap \, p_1$ is empty, then let $q_1$ be a clopen ball strictly contained in $q$ that does not intersect ran($f'$). Let $q_2 = q \setminus q_1$. If instead dom($f'$) $\cap \, p_1$ is nonempty, for every $x \in$ dom($f'$) $\cap \, p_1$ pick a clopen ball around $f(x)$ that is strictly contained in $q$ and contains no other points in ran($f'$). Let $q_1$ be the union of these balls, and $q_2 = q \setminus q_1$. Let $Q'$ be the collection of the $q_i$ (again ignoring any empty sets), and $m'$ be the function that sends $p_i$ to $q_i$ for every $p$, $i$. Then $Q'$ refines $Q$ and $m'$ (which refines $m$) is a matching of $P'$ with $Q'$ that respects $f'$.

Similarly, given any $N_j$ we may refine $P'$ to $P''$, $Q'$ to $Q''$ and $m'$ to $m''$ so that $N_j$ is a union of elements in $Q''$ and $m''$ still respects $f'$. Then $(f', m'', P'', Q'')$ is in $D_{x, y, i, j}$ and extends $(f, m, P, Q)$, as desired.

Since there are only countably many $D_{x, y, i, j}$, we can find a filter $G$ meeting all of them. Taking the union over the $f$'s in $G$ yields a bijection $h: X \rightarrow Y$. This $h$ is actually a homeomorphism. For if $O_i$ is a fixed element of our base for $X$, there is a condition $(f, m, P, Q)$ in $G$ where $O_i$ is a union of pieces in $P$. These pieces are matched by $m$ to pieces in $Q$, and one may check that the union of these pieces (which is open, in fact clopen, in $Y$) is exactly $h[O_i]$. Similarly $h^{-1}[N_j]$ is open in $X$ for every $j$, so that $h$ is a homeomorphism, as claimed.

Cantor's theorem and Sierpinski's theorem have the following generalizations that are useful in certain contexts, and can be similarly proved by forcing arguments by modifying the respective posets in the evident way:

Theorem (Skolem): Fix some $k$, $1 \leq k \leq \omega$. Let $X, Y$ be countable dense, linear orders without endpoints. Fix a partition $X = \bigcup_{i < k} X_i$ such that each $X_i$ is dense in $X$, and similarly $Y=\bigcup_{i < k}Y_i$. There is an isomorphism $f: X \rightarrow Y$ such that $f[X_i]=Y_i$ for every $i < k$.

Theorem: Fix some $k$, $1 \leq k \leq \omega$. Let $X, Y$ be countable, metrizable spaces without isolated points. Fix a partition $X = \bigcup_{i < k} X_i$ such that each $X_i$ is dense in $X$, and similarly $Y=\bigcup_{i <k}Y_i$. There is a homeomorphism $f: X \rightarrow Y$ such that $f \upharpoonright X_i$ is a homeomorphism of $X_i$ with $Y_i$ for every $i<k$.

In his paper, Athanassios Tzouvaras proves the following.

Let $\mathcal{L}$ be a countable language first order language and $\mathcal{M}=(M,...)$ be an $\mathcal{L}$-structure.

Definition:

1) A set $X \subseteq M$ is said to be immune, if it is infinite and does not contain any infinite definable subset.

2) A set $X \subseteq M$ is partially immune if there is a definable set $A$ such that $A \cap X$ is immune.

3) A set $X \subseteq M$ is totally non-immune if neither $X$ nor $M\setminus X$ is partially immune.

Notation: Let $Def$, $IM$, $PIM$, $TNI$ and $Def^{\infty}$ be the classes of definable, immune, partially immune, totally non-immune subsets and infinite definable subsets of $M$, respectively.

Theorem: Assume $\mathcal{M}$ satisfies following property:

Every infinite definable set splits into two infinite definable sets.

Then $Def \subsetneq TNI$.

Sketch of Proof.

Let $\mathbb{P}=\{(p_{0}, p_{1}): p_{0}, p_{1} \in Def^{\infty} \wedge p_{o} \cap p_{1} =\varnothing \wedge M \setminus(p_{0} \cup p_{1})~$is infinite$\}$ ordered by reverse inclusion in each coordinate.

Let $S$ be a transitive set (in $ZFC$) which contains the structure $\mathcal{M}$, together with the sets $Def$, $P$ and $\omega$, and rich enough so that the predicate “$v$ is infinite” is absolutely defined in $(S, \in)$. That is, for every $x \in S$, $x$ is infinite iff there is in $S$ an injection $f : \omega \longrightarrow x$.

Let $\mathcal{S} = (S, \in, M, Def, P)$ be the structure $(S, \in)$ augmented with $M$, $Def$, $P$ construed as unary predicates, and let $\mathcal{L}_{2} = \{\in, M(·), Def(·), P(·)\}$ be the language of the structure $\mathcal{S}$, in which $M$, $Def$, $P$ are treated as unary predicate symbols.

Let $\mathcal{D}=$ the set of all dense subsets of $P$ which are definable in $\mathcal{S}$ by formulas of $\mathcal{L}_{2}$ with parameters from $M \cup Def \cup P$.

Let $G$ be a $D$-generic subset of $\mathbb{P}$, put $G_{0}= \cup\{p_{0}: \exists p_{1} (p_{0}, p_{1}) \in G\}$ and $G_{1}= \cup\{p_{1}: \exists p_{0} (p_{0}, p_{1}) \in G\}$. then

1. $G_{0} \cap G_{1}= \varnothing$ and $G_{0} \cup G_{1}=M$

2. $G_{0}, G_{1}\notin Def$

3. $G_{0}, G_{1}\notin PIM$, hence $G_{0}, G_{1}\notin TNI$.

Years ago, Matthew Wiener sketched on USENET a proof using forcing that the graphs of most continuous real-valued functions have Hausdorff dimension 1. Here is what he said. (Originally Wiener used the term "fractal dimension" but he later said that he meant "Hausdorff dimension" so I have edited the original text accordingly.)

Did you know that there are continuous nowhere differentiable functions of Hausdorff dimension 1? Did you know that most continuous real-valued functions on [0,1]—in the sense of category—are of Hausdorff dimension 1? I believe this is original with me. What makes it interesting is that I first proved this using Cohen forcing.

The category proofs, and even various specific constructions, are trivial modifications of the usual proofs for continuous nowhere differentiable functions. Once you know this result, it should take about five minutes to take such a proof and extend it to Hausdorff dimension 1.

But that was not how I stumbled upon it. I had never heard of the result, and the impression I got from Mandelbrot and friends was that the graphs of these bad boy functions were the canonical examples of fractals. I was doodling at some physics lecture, drawing dots at random, when it occurred to me out of nowhere that the dots formed a forcing condition, whose generic "limit" is obviously continuous but nowhere differentiable. (The stronger conditions will fill the dots in a "generic" manner, avoiding any pattern, ie, zigzaggy on every scale.)

It didn't take much longer to notice that the generic "limit" had Hausdorff dimension 1 (and that "most" of its Besicovitch subdimensions were zero). (The stronger conditions squeeze in arbitrarily close to any connect-the-dots interpolation.)

A bit of careful fiddling was needed to see that the Schoenfield theorem applied, but it was very elementary. (It does not apply to the existence of nowhere differentiable functions, but it does to "uniformly" nowhere differentiable functions, ie, the necessary delta-epsilon failure can be quantified independently of abscissa.)

And since forcing is, deep down, just the Baire category theorem, the existence of this approach isn't that surprising.

What would be of real interest would be finding a $\Delta^1_3$ property of the generic "limit", since that would bring large cardinals into play.

• I'm a bit confused - how do we conclude that the generic function $f$ so produced is continuous? I'm pretty sure it is everywhere discontinuous - given any condition $p$, any real $x$, and any positive reals $\epsilon$ and $\delta$, we can always extend $p$ to a condition $q$ with some new real $y$ in its domain, within $\delta$ of $x$, such that $\vert q(x)-q(y)\vert>\epsilon$. Or are the forcing conditions more elaborate? – Noah Schweber Jan 8 '15 at 1:14
• I agree with @NoahS. There will need to be some constraints on the forcing conditions to make the generic function continuous, but the constraints are missing from this description. – Andreas Blass Jan 8 '15 at 2:42
• This matters for the notion of "most" - the topology w/r/t which the set of generics is "large" depends on the forcing notion. For example, the set of reals which are Sacks generic is not comeager. – Noah Schweber Jan 8 '15 at 3:45