What did Paul Cohen mean by saying that generic sets of natural numbers have "no asymptotic density?"

Question

In Paul Cohen's original 1963 paper on forcing, The independence of the Continuum Hypothesis, published in PNAS, he gives his general proof sketch of how he intends to create a model of ZFC that doesn't support CH:

1. Start with a countable model of ZFC.
2. Within the model, there are the model's cardinals $\aleph_0^*, \aleph_1^*, \aleph_2^*,$ etc, which are different from the cardinals in the ambient theory $\aleph_0, \aleph_1, $ etc.
3. Cohen then proceeds building an ordinal-length sequence of subsets of the true $\aleph_0$ which is of length $\aleph_2^*$, and uses this to build a new model in which CH doesn't hold.

Of these subsets, Cohen writes:

"Only those properties which are true in a "uniform" manner for "generic" subsets of $\omega$ in $\mathcal{M}$ [the first model] shall be true for the $a_\delta$ [the ordinal-length sequence of subsets] in $\mathcal{N}$ [the new model]. For example, each $a_\delta$ contains infinitely many primes, has no asymptotic density, etc."

I interpret "no asymptotic density" as meaning the natural density doesn't converge to anything as $N \to \infty$.

I am not sure what Cohen means with the language "generic," but if the most straightforward interpretation is that it means "almost all," then this doesn't seem like a true statement for "generic subsets" of $\Bbb N$, as almost all have natural density equal to 0.5. If identify any such subset with its characteristic function from $\mathbb N \to \{0, 1\}$, then you have an infinite length binary string, and it would seem that almost all of those have 50% 0's and 50% 1's, similarly to how almost all real numbers have 50% of their bits equal to 0 and 50% equal to 1 in their binary expansion.

Does anyone have clarification on this? Is this a simple error or is there a different interpretation here of a "generic" subset?

Answer 1

Perhaps it's worth collecting the comments into a community wiki answer.

When Cohen was trying to prove the independence of the continuum hypothesis from ZFC, at some point he realized that what one needed to do was to take a countable transitive model $M$ of ZFC and "adjoin" a suitable subset of $\mathbb N$ to it, much as one can "adjoin" a complex number $x$ to $\mathbb Q$ to create a larger field $\mathbb{Q}(x)$. The trouble, however, is that the ZFC axioms are a lot more complicated than the axioms for a field, and so you cannot just adjoin an arbitrary subset of $\mathbb{N}$ to $M$ and expect to always produce another model of ZFC. Counterexamples are not hard to construct. However, when Cohen was studying these counterexamples, he realized that they were all rather "delicate," using "special features" of $M$ to cause trouble. He therefore conceived the idea that perhaps the difficulties could be avoided by adjoining a "generic" subset of $\mathbb N$.

Initially, when Cohen was still groping around for the right concepts, he had no precise definition of "generic" in mind. Eventually, he developed the machinery of forcing, which is too complicated to describe in detail here. But central to the construction is a poset $P\in M$ and a filter $G$ that is $P$-generic over $M$. This definition of "generic" is precise, and can be phrased in terms of "intersecting every dense subset." Although Cohen did not originally think in topological terms, it was soon recognized that there was a very close relationship between generic sets and comeager sets. So when Cohen says that generic subsets of natural numbers have no (natural) density, he means that the set of all subsets of natural numbers with no density is comeager, and not that it has measure one. Nate Eldredge's answer gives a proof of Cohen's claim.

One may still wonder whether Cohen's initial intuition about "having no special properties" can be made precise in some other way. I have had long discussions with Scott Aaronson, who very much wants the argument to go something like this: "Attempting to adjoin certain special subsets of $\mathbb N$ to $M$ causes trouble, so let's instead adjoin a random subset of $\mathbb N$, and argue that almost surely we will avoid all the bad subsets of $\mathbb N$." For someone with Scott's background, probability theory (or measure theory) is natural, but Baire category is…weird.

Initially, I thought that Scott's idea could work. But I soon realized that measure and category don't align well when it comes to forcing. We see that in your example here; as you point out, the strong law of large numbers implies that if you flip a fair coin countably many times, then almost surely the proportion of heads will converge to 1/2. However, the set of such outcomes is meager. (By the way, the natural way to understand the random coin flips is to take the product of countably many copies of a two-element set, so I suspect that what's really bothering you is not the distinction between the topology of the Cantor set and the topology of $\mathbb R$, but rather the distinction between measure and category.)

As it turns out, the forcing machinery is so flexible and powerful that it can be used to adjoin a random subset of $\mathbb N$ to $M$; this technique is known as random forcing. But trying to prove the independence of the continuum hypothesis this way involves more technicalities than Cohen's original proof, and to prove that it all works, it seems that one needs to introduce all the standard forcing machinery anyway, so it's not clear that anything is gained. There is no known way to dispense with the usual definition of "generic" and rebuild all the tools used for independence proofs in purely probabilistic terms. Despite 60 years of effort, no alternative technique with comparable power and versatility to forcing has been found; the machinery of forcing seems to be forced upon us, for reasons that remain somewhat mysterious even a posteriori, let alone a priori.

Answer 2

Responding to Timothy Chow's comment, here's a quick proof that the set of sets having no asymptotic density is comeager. Indeed, we show that the set of sets having upper density 1 and lower density 0 is dense $G_\delta$.

Note that the usual topology on $\mathcal{P}(\omega)$, as stated in Will Brian's comment, can also be identified with the product topology on $\{0,1\}^\omega$, or with the usual topology on the Cantor set. It is compact Hausdorff (even metrizable) and in particular Baire.

Define $a_n : \mathcal{P}(\omega) \to \omega$ by $a_n(A) = |A \cap \{ 1,\dots, n\}|$. Then each $a_n$ is continuous. Now for integers $N,k$, let $$U_{N,k} := \bigcup_{n \ge N} \left\{A : \frac{a_n(A)}{n} > 1-\frac{1}{k}\right\}$$ which is clearly open, and also dense because it contains all the cofinite sets in $\mathcal{P}(\omega)$. Then $G_k = \bigcap_{N \in \omega} U_{N,k}$ is the set of all $A$ for which the upper density $\limsup_{n \to \infty} \frac{a_n(A)}{n}$ is at least $1-\frac{1}{k}$, and it is a dense $G_\delta$. Hence so is $\bigcap_{k \in \omega} G_k$ which is the set of all $A$ with upper density 1.

By a similar argument, the set of sets with asymptotic lower density 0 is also dense $G_\delta$, so the intersection of the two is yet again dense $G_\delta$.

Answer 3

To compliment the comments and Nate Eldredge's answer, here's a useful lemma for showing that a given property $P$ of infinite binary sequences is comeager:

Lemma: Consider the game $G_P$ where players $1$ and $2$ alternate playing finite binary strings for $\omega$-many moves, and then player $2$ wins iff the concatenation of those strings has property $P$. Then the following are equivalent:

• Player $2$ has a winning strategy in $G_P$.

• The set of $f$ with property $P$ is comeager in $2^\omega$.

So for example:

• The set of sequences with infinitely many $0$s is comeager: just have player $2$ always play "$0$."

• The set of sequences with arbitrarily long strings of $1$s is comeager: just have player $2$ play a length-$i$ string of $1$s on their $i$th move.

And, as desired:

• The set of sequences with undefined asymptotic density is comeager: have player $2$ alternately play "really long" strings of $0$s or of $1$s. Note that here we have to take the opponent's behavior into account in a meaningful way, since the right notion of "really long" depends on the total length of the sequence built so far, not just how many moves have been played.

In my experience it's much easier to think in terms of winning strategies than in terms of (co)meagerness per se. Note that while I've phrased the lemma for the specific context of $2^\omega$, it holds much more generally (and so we can use the same intuition when working with wildly different forcings).