Similarities between Post's Problem and Cohen's Forcing

Question

Remark: I have since learned that G.H. Moore addresses this question in the third reference listed at the end of this post, beginning on p. 157 in which he cites a letter from Kreisel to Gödel dated 4/15/63, followed by the parenthetical note: Thus Kreisel saw an analogy between forcing and Friedberg's [1957] priority argument. The following page suggests other logicians agree that forcing was implicit in priority arguments from recursion theory (p. 158) and mentions Kunen (who is cited in one of the answers here). On the same page, it is mentioned that Kreisel claimed he had a form of forcing in his interpretation of intuitionism in the 1961 paper "Set-theoretic problems suggested by the notion of potential infinity." However, Moore contends that Cohen was the first to use forcing and related ideas in Set Theory. Nevertheless, I am grateful for the responses thus far, and would warmly welcome further clarification regarding my question below from other experts in the area of Set Theory and/or Mathematical Logic.

---

Background: Paul Cohen began to think deeply about the Continuum Hypothesis in 1962, and published his proof of its independence (in two parts) by the following year. Of course, there were earlier mathematical moments that led to his "discovery of forcing," including his familiarity with Skolem's work (in particular, the Löwenheim–Skolem theorem) and a desire to think in terms of "decision procedures." I will include a few relevant references at the end of this question, including a retrospective/introspective piece by Cohen himself.

My question concerns an occurrence in 1957, when Richard Friedberg provided a solution to Post's Problem. First, allow me to transcribe an excerpt from Cohen's talk at the 2006 Gödel centennial:

At that time there was great interest among Raymond [Smullyan] and some other people about the Post Problem. And that’s a problem which could have interested me; it had a mathematical flavor to it. But I never thought about it, and occasionally we’d have coffee and I’d hear these people talk about it. But one day, someone came to my office and said, “This problem’s been solved.” And I said, “Really?” “Yes, here’s the letter. I can’t believe it’s true!” And he gave it to me and I read it. I went to the blackboard, took some chalk, and I said, “Well, it seems right.” This is the proof by Friedberg – and so that was my only contact with logic at that point. But I still never lost this idea of somehow thinking about the foundations of mathematics: trying to find some kind of inductive technique for simplifying propositions; perhaps leading to a decision procedure, when impossible.

This talk is summed up in the introduction to a re-printing of "Set Theory and the Continuum Hypothesis" (Cohen, 2008) in which the remarks corresponding to the above excerpt are:

A small group of students were very interested in Emil Post's problem about maximal degree of unsolvability. I did dally with the thought of working on it, but in the end did not. Suddenly, one day a letter arrived containing a sketch of the solution by Richard Friedberg (Friedberg, 1957), and it was brought to my office. Amidst a certain degree of skepticism, I checked the proof and could find nothing wrong. It was exactly the kind of thing I would like to have done. I mentally resolved that I would not let an opportunity like that pass me again.

I find the last sentence of this latter quotation rather interesting, particularly since it concerns a time five years before Cohen's work on ~CH officially commenced. A quick check of Wikipedia gives a problem statement and solution (i.e., the priority method) that sound remarkably similar, at least on the superficial level, to Cohen's subsequent work with forcing. Unfortunately, work on Turing degrees falls well outside of my bailiwick.

Question: Can someone who specializes in Set Theory or Mathematical Logic comment on the similarities between Post's problem/the priority method and ~CH/Cohen's forcing? In particular, is there reason to believe that what was Cohen's "only contact with logic" by 1957 would have contributed in a meaningful (mathematical) way to his work half a decade later?

---

References:

Cohen, P. (2002). The discovery of forcing. Rocky Mountain Journal of Mathematics, 32(4).

Kanamori, A. (2008). Cohen and set theory. The Bulletin of Symbolic Logic, 351-378.

Moore, G. H. (1988). The origins of forcing, Logic Colloquium ’86. Studies in Logic and the Foundations of Mathematics, North-Holland, Amsterdam, 143-173.

Answer 1

In this edit, a historical note is added at the end.

The quote below from Kunen's classic text Set Theory maybe of interest to you. Note that Kunen is pointing out that certain classical constructions in recursion theory can be viewed as precursors to forcing; but he does not claim that priority arguments fall under this category (on the other hand, there have been attempts to couch priority arguments as forcing arguments, e.g., by Nerode and Remmel in the mid-1980s).

"There are two important precursors to the modern theory of forcing: one in recursion theory and one in model theory. In recursion theory, many classical results may be viewed, in hindsight, as forcing arguments. Consider, for example, the Kleene- Post theorem that there are incomparable Turing degrees. Let $\Bbb{P}$ = Fn $(2$ x $\omega, 2)$, let $G$ be $\Bbb{P}$-generic over $M$, and think of $G$ as coding $f_0$ and $f_1\in2^{\omega}$, where $f_i(n) =\cup G(i,n)$. Furthermore, to conclude recursively incomparability of $f_0$ and $f_1$ it is not necessary that $G$ be generic over all of $M$; it is sufficient that $G$ intersect only a few of the arithmetically defined dense sets of $M$; so few that in fact $G$, and hence also $f_0$ and $f_1$ may be taken to be recursive in $0'$. This forcing argument for producing incomparable degrees below $0'$ is in fact precisely the original Kleene-Post argument, with a slight change in notation. See [Sacks 1971] for some deeper applications of forcing to recursion theory and a comparison of these methods with earlier (pre-forcing) techniques". [From Set Theory, by Kenneth Kunen, p.236]

Historical Note: Cohen did not develop forcing in terms of general partial orders. His forcing machinery was developed (1) only over models of set theory satisfying Gödel's axiom of constructibility (V=L), and (2) and for certain partially order sets [namely those of the form Fn($\kappa, 2$) in modern terminology]. The machinery of forcing over arbitrary models was first developed by Solovay and Scott in the guise of Boolean valued models. Their approach was later simplified by Shoenfield to yield the current textbook formulations in terms of arbitrary partial orders.

Therefore, even though priority arguments can be viewed as forcing arguments (as developed by Nerode and Remmel, and described in the answer of Noah S.) Cohen's work on forcing, only when extended by new ideas of Solovay, Scott, and Shoenfield (and perhaps others, e.g., Rowbottom) led to a suffciently powerful technology that subsumes (at least formally) priority arguments.

Answer 2

The primary difference between forcing arguments in set theory and priority constructions is that the latter care about the complexity of the generic filter in a way the former do not. In particular, forcing in set theory involves hitting every dense set in a given model, and so the generic cannot possibly be a member of that model (unless the poset is trivial), whereas if you frame priority constructions as forcing arguments the goal is to hit a fixed countable set of dense sets with a generic which is computable (or close to that) as a set of conditions (the set coded by the generic, on the other hand, won't be computable).

(Let me write this out explicitly, in the case of Friedberg-Muchnik: the poset in question is the set of pairs $(p, \rho)$, where $p$ is the set built so far (i.e., $p\in 2^{<\omega}$) and $\rho$ is the collection of restraints imposed so far (so $\rho$ is a finite subset of $\omega\times(\omega\cup\lbrace -1\rbrace$) with each element of $\omega$ occurring as the left component of at most one element of $\rho$). The poset is ordered in the following way: $(p, \rho)\le(q, \pi)$ if

1. $\vert p\vert\ge\vert q\vert$ and $\forall n<\vert q\vert, q(n)\le p(n)$ (this is the c.e. condition - we're not allowed to remove elements from the set we're building);

2. for all $(n, m)\in\pi$ with $m>-1$, either $p\upharpoonright m+1=q\upharpoonright m+1$ or for some $k<n$ and $j>-1$ we have $(k, j)\in \rho-\pi$ (this is the missing condition Francois pointed out, which stipulates that restraints can only be violated by the actions of higher-priority requirements); and

3. $$ \forall n\in dom(\rho), \rho(n)\not=\pi(n)\implies \exists m < n[(\rho(m)=-1\vee m\not\in dom(\rho))\wedge \pi(m)\downarrow>-1).$$ (This just says that $\rho$ "could occur from $\pi$ by injury.")

Note that conditions in this poset can be coded by natural numbers, so it makes sense to talk about a set of conditions - i.e., a filter - being computable. Now the requirements in the Friedberg-Muchnik argument can be represented by dense sets (which are not computable) in this poset, two for each $\Phi_e$, and the theorem turns into "there is a computable filter through this poset generic for this collection of dense sets." In fact, I believe the poset described above is "universal" for finite injury arguments, in the sense that each finite injury argument can be dealt with by coming up with an appropriate list of dense subsets of this poset and then arguing that there is a computable filter which is generic for that collection of sets, but I'm not sure about that.)

A possible stronger analogy: priority arguments are like forcing axioms. Forcing axioms say "for such-and-such a poset and collection of dense sets, there is a generic filter already in the model." For example, Martin's Axiom says that for any poset $\mathbb{P}$ with the c.c.c. and any collection $\mathcal{D}$ of $< 2^{\aleph_0}$-many dense sets, there is already a $\mathcal{D}$-generic filter. By analogy, the punchline of a priority argument is often "for this particular poset and these dense sets, there is a computable generic filter." In both cases, we start with the Rasiowa-Sikorski Theorem ("we can hit countably many dense sets") and try to strengthen it: in the set-theoretic case, by enlarging the class of dense sets, and in the computability-theoretic case, by restricting the collection of filters we consider. In fact, this is an analogy I've spent a lot of time thinking about over the course of the last year; it hasn't helped me understand priority arguments, but it has helped me understand forcing axioms.

That said, I do think of priority constructions as a type of forcing; I just realize that this isn't necessarily convincing.

---

Now let me briefly address the question of what role, if any, Friedberg/Muchnik (or related earlier work by Kleene/Post) played in Cohen's development of forcing. On the one hand, in his paper "The Discovery of Forcing" (which you cite), Cohen describes his process as mostly self-contained, but at one key juncture bolstered by reading Goedel's monograph on $L$. No reference is made to computability theory, and indeed the words "Friedberg," "Muchnik," "Post," "priority," and "recursion" appear nowhere in the article. ("Kleene" appears once, but only in reference to the fact that Kleene's tome on mathematical logic did not include anything especially relevant to Cohen's project.) On the other hand, I seem to recall an article in which Cohen described his picture of forcing as involving an adapting oracle, which he connected to computability theory - which would suggest a real influence. But I can't track down that citation at present; all I can find is a comment by Chad Groft on Terry Tao's blogpost http://terrytao.wordpress.com/2010/03/19/a-computational-perspective-on-set-theory/ that says Cohen explained forcing in this way in his later years. But Cohen may have changed his intuition about forcing over time, so that it is quite possible that Cohen came to view his forcing arguments as related in spirit to recursion theory, while not actually having drawn any inspiration from the subject originally.