12
$\begingroup$

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?

$\endgroup$
15
  • 11
    $\begingroup$ This is not a discussion in the sense of measure, but rather in the sense of category. $\endgroup$ – Andrés E. Caicedo Jan 15 at 19:18
  • 21
    $\begingroup$ Also, you are misunderstanding what is meant with "has no asymptotic density" - he doesn't mean the density is zero, he means the density literally doesn't exist, i.e. the limit defining it doesn't exist. $\endgroup$ – Wojowu Jan 15 at 19:27
  • 6
    $\begingroup$ Just to elaborate on Andres' comment: A property of a subset of ๐œ” is called "generic" if it is true for a co-meager set of subsets of ๐œ”. To make sense of this, you need to have a topology on $\mathcal P(\omega)$, and the standard choice for this is to have basic open neighborhoods of the form $[๐ด,๐‘›] = \{ ๐‘ฅ โŠ† ๐œ” :\, xโˆฉ\{0,1,2,โ€ฆ,๐‘›โˆ’1\} = ๐ด \}$. In other words, a basic open neighborhood of $\mathcal P(\omega)$ is defined by specifying whether finitely many members of ๐œ” are or aren't in a set. This is similar to how . . . $\endgroup$ – Will Brian Jan 15 at 21:10
  • 3
    $\begingroup$ you need a probability measure on $\mathcal P(\omega)$ in order to make sense of a proposition being true for "almost all" subsets of ๐œ”. (By the way, the topology I've described on $\mathcal P(\omega)$ makes it homeomorphic to the Cantor space, so it's a "nice" and familiar topology.) Anyway, it is true that $\{ ๐‘ฅ โŠ† ๐œ” :\, ๐‘ฅ \text{ has no asymptotic density} \}$ is a co-meager subset of $\mathcal P(\omega)$, with respect to this topology. And this is what Cohen means when he calls it a "generic" property of a subset of $\omega$. $\endgroup$ – Will Brian Jan 15 at 21:12
  • 3
    $\begingroup$ @AsafKaragila I think Takeuti also noticed quite early that Cohen's notion of genericity matches what one gets from Baire category. $\endgroup$ – Andreas Blass Jan 15 at 21:24
9
$\begingroup$

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.

$\endgroup$
1
  • 2
    $\begingroup$ In the adjoining $x$ to $\Bbb Q$ analogy, I find it more instructive to talk about a ring that embeds every prime field. Now $x$ might have order $2$ and $\Bbb Q(x)$ is not even a field anymore. Now the question becomes much more real: can we guarantee that $\Bbb Q(x)$ is a field? Or alternatively, I want to define an order on the transcendental extension $\Bbb Q(x)$, so I need to decide where $x$ is sitting in that order, the forcing poset is equivalent to saying $x$ is larger than this, or smaller than that rational number. $\endgroup$ – Asaf Karagila Jan 18 at 12:40
8
$\begingroup$

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$.

$\endgroup$
6
$\begingroup$

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).

$\endgroup$
10
  • 1
    $\begingroup$ Compliment or complement? $\endgroup$ – Asaf Karagila Jan 18 at 12:44
  • $\begingroup$ This goes by the name of "Banach-Mazur game," yes? $\endgroup$ – Timothy Chow Jan 18 at 13:48
  • $\begingroup$ @TimothyChow Yes, this is exactly the Banach-Mazur game (for the subspace of $2^\omega$ consisting of those sequences with property $P$, under the assumption that that subspace is dense in $2^\omega$ anyways). $\endgroup$ – Noah Schweber Jan 18 at 18:38
  • $\begingroup$ Thanks Noah. Is being "generic" a property of individual binary sequences, or just of sets of them? That means, given some sequence, can we say if it is generic or not, or is it just various sets that either are comeager or not? $\endgroup$ – Mike Battaglia Jan 18 at 20:30
  • $\begingroup$ @MikeBattaglia Genericity is a property of individual reals, but it's really an abbreviation. In the context of forcing, "generic" is short for "generic over $M$" for some specific model $M$. This refers to a particular comeager set $C_M$: while $C_M\cap M=\emptyset$ ("there are no generic-over-$M$ reals in $M$"), $C_M$ is comeager in reality (assuming $M$ is countable of course). $\endgroup$ – Noah Schweber Jan 18 at 20:49

Your Answer

By clicking โ€œPost Your Answerโ€, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.