Forcing as a tool to prove theorems

It is often mentioned the main use of forcing is to prove independence facts, but it also seems a way to prove theorems. For instance how would one try to prove Erdös-Rado, $\beth_n^{+} \to (\aleph_1)_{\aleph_0}^{n+1}$ (or in particular that $(2^{\aleph_0})^+ \to (\aleph_1)_{\aleph_0}^2$) by using forcing? Is it simpler than the combinatorial proof? Which partial order would one use?

Or can one try to show that forcing the negation of the Erdös-Rado is impossible or inconsistent?

-

8 Answers

I never heard anyone claim the existence of a forcing proof of the Erdős-Rado theorem. On the other hand, yes, there are several proofs of nonindependence statements that use forcing. One is Shelah's proof for the existence of a finite K4-free graph which, when the edges colored by 2 colors, always contains a monocolored triangle (a problem of Erdős and Hajnal). Here is the argument. He constructs a forcing extension which adds a graph X with the same property but with ℵ0 colors (this is not easy). Obviously, X has the edge-coloring property for 2 colors, as well. X must contain a finite subgraph Y with the same property. This is compactness, or, any proof for the Erdős-de Bruijn theorem gives it. As forcing cannot create new finite graphs, Y is already present in the underlying model. That is, there is a finite graph as required in any countable, transitive model of a sufficiently large part of ZFC. By Gödel, this is only possible, if ZFC proves that there is such a graph.

Another example is the original proof of the Baumgartner-Hajnal theorem: ω1→(α)2k if α<ω1, k<ω. They first deduced it from Martin's axiom, then a specific argument gives that if it holds in a cardinal preserving extension, then it holds in the original model. Therefore, it holds in every countable, transitive model of a sufficiently large fragment of ZFC, and we can finish as above.

-
+1. Shelah's argument sounds magical: construction of a finite combinatorial object using forcing. Where can one find the proof? –  T.. Jun 29 '10 at 19:40
Well, he constructs an infinite objects which must contain a finite one. S. Shelah: Consistency of positive partition theorems for graphs and models, Set theory and its applications (Toronto, 1987), Lecture Notes in Math., 1401, Springer, Berlin, 1989.167-193. –  Péter Komjáth Jun 29 '10 at 19:55
Thank you! Are there any other examples, where "significantly infinite" constructions are used to construct individual finite objects? By significant I mean more than existence of an infinite set, the real number system, compactness principles, or nonstandard analysis. Here the forcing argument uses a model of set theory as an input (or the syntactic assumption of consistency of that theory, which is not essentially different from assuming a model). –  T.. Jun 29 '10 at 20:30
sorry, i almost read that as: forcing a proof ;-) –  Suvrit Nov 17 '10 at 17:37

The situation isn't that any given theorem off the shelf might have a forcing proof, but rather that it is a fascinating situation when one can use forcing to prove a theorem purely about the ground model. For such proofs, one makes a conclusion about the set-theoretic universe $V$ by first going to another universe $V[G]$, and then by analyzing the relationship between $V$ and $V[G]$, making a conclusion purely about $V$.

Let me illustrate with a few concrete examples.

• There are incomparable Turing degrees. This theorem is usually proved by a combinatorial constructive argument, meeting infinitely many requirements in sequence. However, there is also a soft forcing proof: add two mutually generic Cohen reals $c$ and $d$. By genericity, neither is computable from the other, and so the assertion is true in $V[c][d]$. But the assertion there are incomparable degrees has complexity $\Sigma^1_1$, and hence is absolute to $V$. So the statement is true in $V$, as desired.

• A similar argument produces an infinite antichain this way, with the further property that any real computable from two of them is outright computable with no oracle. Similarly, one can make conclusions about hyperarithmetic incomparability this way, with a very soft argument essentially without any hyperarithmetic details.

• Indeed, many constructions in computability theory can be viewed as forcing arguments in this way. Rather than describing a detailed construction meeting certain requirements at certain stages, one shows that the requirements correspond to dense sets in a certain partial order and then appeals to genericity. One could use actual genericity and then absoluteness to claim that the desired objects already exist in the ground model, as I did above, or alternatively just note that there were only countably many dense sets to meet and thus the objects exist by the usual diagonalization.

• Another example arises in Borel equivalence relation theory, in the result that there is no Borel reduction of $E_0$, the relation of almost-equality on binary sequences, to equality. The classical proof uses ergodic theory, but there is a quick forcing argument. Suppose it did reduce; this fact is absolute to the forcing $V[c]$ adding a Cohen real. Since any finite change in $c$ is still generic, the particular real $w$ that $c$ maps to under the reduction does not depend on $c$, and hence is in the ground model $V$. But the assertion that some real maps to $w$ is absolute, and so $c$ differs finitely from a ground model real, contradiction.

• Similar forcing arguments yield other non-reductions in Borel equivalence relation theory. For exmple, the relation $E_{set}$ can be treated by the forcing $Coll(\omega,\mathbb{R})$, since any two generic reals for this partial order enumerate the same set, the set of ground model reals.

I think there are numerous examples of ZFC theorems proved via forcing, and I would encourage you to edit your question to explicitly encourage people to post such answers, as I would be very interested to see additional such examples. In this case, the big-list tag might be appropriate.

-
It may be worth mentioning that there is also an easy measure theory proof that incomparable degrees exist, due to Spector in 1958. Since there are only countably many degrees $\le$ a given degree, almost all pairs are incomparable by Fubini's theorem. The same applies to hyperarithmetic incomparability. –  John Stillwell Jun 30 '10 at 0:23
Another great example from Descriptive Set Theory is Harrington's proof of Silver's Theorem that a Borel or even $\Pi^1_1$ equivalence relation has either countably many classes or a perfect set of inequivalent elements. This proof, like the recursion theoretic arguments Joel mentions, can be recast as a forcing free Baire category argument in a suitable topology. Recently Ben Miller developed a beautiful "classical" framework for proving this and many other dichotomy theorems of Descriptive Set Theory. –  Dave Marker Jul 9 '10 at 14:31

One way to use forcing to prove actual ZFC results is by using absoluteness. I do not know of a forcing proof of Erdös-Rado, but there is a forcing proof of the somewhat similar Baumgartner-Hajnal theorem that $\omega_1\rightarrow(\alpha)^2_2$ for any countable ordinal $\alpha<\omega_1$. The only absoluteness fact you need for this is that if $M\subseteq N$ are transitive models of ZFC and $T$ is a tree in $M$, then $T$ is well-founded in $M$ if and only if it is well-founded in $N$.

In outline the proof of Baumgartner-Hajnal is as follows. First it is shown that Martin's Axiom (MA) implies the partition relation $\omega_1\rightarrow(\alpha)^2_2$. Now show that it holds in an arbitrary countable transitive model $M$ of ZFC. Given a coloring $\chi:[\omega_1]^2\rightarrow 2$ in $M$ we seek a $\chi$-homogeneous set of ordertype $\alpha$ in $M$. Use a ccc forcing to extend $M$ to a transitive model $N$ with the same cardinals and satisfying MA. Since $N$ satisfies MA it contains a $\chi$-homogeneous set of ordertype $\alpha$. Then define a tree (in $M$) of finite approximations to such a homogeneous set, so that a branch through the tree corresponds exactly to such a homogeneous set. Since the tree is not well-founded in $N$, it is also not well-founded in $M$ and so we get our homogeneous set in $M$.

This theorem first appeared in the paper by Baumgartner and Hajnal "A proof (involving Martin's axiom) of a partition relation" Fund. Math., 78(3):193–203, 1973 and you can get it here: http://matwbn.icm.edu.pl/ksiazki/fm/fm78/fm78121.pdf

-
Why does MA holding in $N$ ensure that $N$ contains a $\chi$-homogeneous set of size $\alpha$? Thanks for reference! –  Carlo Von Schnitzel Jun 29 '10 at 20:46
Because under MA the partition relation holds, and N contains $\chi$ and has the same $\omega_1$. That MA implies the partition relation is Theorem 2 in the paper. I don't think I have a good enough understanding of the argument to give a cogent summary. For what it's worth it seems the only consequence of MA needed is that the so-called tower number is at least $\omega_2$. (which implies the dominating number is at least $\omega_2$, which they use as well) –  Justin Palumbo Jun 30 '10 at 6:40

This is not an answer to your question about the Erdos-Rado theorem, but a remark concerning another example of a forcing proof of a ZFC result (a result which is actually quite useful and observed by several authors). For every infnite subset $L$ of $\mathbb{N}$ denote by $[L]^{\infty}$ the set of all infinite subsets of $L$.

Let $X$ be a Polish space and $A$ be a co-analytic subset of $[\mathbb{N}]^{\infty}\times X$ such that for every $L\in [\mathbb{N}]^{\infty}$ there exists $x\in X$ with $(L,x)in A$. Then there exist an infinite subset $M$ of $\mathbb{N}$ and a continuous map $f:[M]^{\infty}\to X$ such that $(N,f(N))\in A$ for every $N\in [M]^{\infty}$.

The result can be easily proved under MA. It is also easily seen to be absolute, therefore it is true in ZFC. Nevertheless, to the best of my knowledge, no "classical" proof is known.

-

There is also a theorem saying that a sequence of canonical Borel approximations of an analytic non-Borel set from inside can never be of a bounded Borel rank

-
Hello Vladimir. Welcome! –  Andres Caicedo Nov 17 '10 at 16:22
By the way, this answer should probably be added to the list in mathoverflow.net/questions/42569/… –  Andres Caicedo Nov 17 '10 at 16:23

There are also some model-theoretic examples of such proofs (in ZFC). Once you prove that for a given logic L, the notions of consistency and completeness (for theories in L) are absolute, it's possible to prove (in ZFC) the existence of some interesting models (described by an L-theory) just by showing that such models exist in some generic extension. One example is presented in a paper by Shelah called "Nonstandard uniserial module over a uniserial domain exists", the proof uses a completeness theorem for stationary logic.

-
A simple but fascinating result in this context is that two models are $L_{\infty\omega}$-equivalent (i.e., back-and-forth equivalent) if and only if there exists a generic extension $V[G]$ which thinks they are isomorphic. –  Emil Jeřábek Mar 1 '11 at 12:18

An example from elementary geometry is the very simple forcing argument to establish the non-axiomatizability (in infinitary logic) of Sperner spaces, due to Blass and Pambuccian: Blass, A.; Pambuccian, V. "Sperner spaces and first order logic." Mathematical Logic Quarterly vol. 49, no. 2 (March, 2003), 111-114. The proof uses a cardinal collapse and absoluteness.

-

Matthew Wiener once explained to me that because of the close connections between forcing and the Baire category theorem, forcing could be used to prove certain results in analysis that are more commonly proved via BCT. Unfortunately, I can't remember the details, and the closest thing I've been able to find is this article where Wiener states that there is an easy proof via forcing of the existence of continuous nowhere-differentiable functions of Hausdorff dimension one. Perhaps some other MO reader can supply the missing details.

-