# Forcing, constructibility, and random functions

This question is in some ways an offshoot of my recent question about trying to explain forcing to someone (such as Scott Aaronson, whose questions have prompted my questions) encountering it for the first time. Actually, I have two questions.

In Cohen's book Set Theory and the Continuum Hypothesis, he begins not with an arbitrary countable transitive model of $$\mathsf{ZFC}$$, but with the minimal model. That is, Cohen assumes that there exists a set model for $$\mathsf{ZFC}$$ where the $$\in$$ relation is the standard one, and $$M = L(\alpha)$$ for the smallest $$\alpha$$ such that $$M$$ is a model of $$\mathsf{ZFC}$$ (here $$L(\alpha)$$ denotes the constructible sets with rank less than $$\alpha$$). In this case, the generic extension $$M[G]$$ can also be described as $$L(\alpha,G)$$, where $$L(\alpha,G)$$ is defined in terms of the definable power set operation $$\mathscr{D}$$: \eqalign{ L(0,G) &:= \lbrace G \rbrace \cup \mathrm{tr\, cl}(G) \cr L(\gamma+1,G) &:= \mathscr{D}\bigl(L(\gamma,G)\bigr)\cr L(\gamma,G) &:= \bigcup_{\beta<\gamma} L(\beta,G) \quad \mbox{if \gamma is a limit}\cr} Now in general, for any countable transitive model $$M$$ of $$\mathsf{ZFC}$$, it is a theorem that $$M[G]$$ is the smallest transitive model of $$\mathsf{ZFC}$$ containing both $$M$$ and $$G$$. This brings me to my first question.

For an arbitrary countable transitive model $$M$$, can $$M[G]$$ always be described in terms of the definable power set operation?

Suppose now that we are trying to create a model that violates $$\mathsf{V}=\mathsf{L}$$. We can take our poset $$P$$ to be the poset of finite partial functions from $$\omega$$ to $$\lbrace 0,1\rbrace$$. The standard thing to do now is to take a generic filter $$G$$ in $$P$$. Scott wondered whether we could instead take a random function $$f$$ from $$\omega$$ to $$\{0,1\}$$. That is, for each natural number $$n$$, we flip a fair coin and set $$f(n)=0$$ or $$f(n)=1$$ accordingly. Given $$f$$, we can define $$G$$ to be the set of all restrictions of $$f$$ to a finite domain; then $$G$$ is a filter by construction, but $$G$$ might not be generic. Now comes the second question.

Will $$G$$ be $$P$$-generic over $$M$$ with positive probability?

At first I thought the answer would be yes, but when I tried to prove it, I realized that I was bumping up against the distinction between measure and category. It seems that the answer to this question might depend on $$M$$. Perhaps for the minimal model $$M$$ the answer might be yes, and for some other model the answer might be no?

• A randomly generated real will almost surely be $M$-generic for random real forcing (if $M$ is countable), and therefore the probability that it will be generic for Cohen forcing is zero (see Jech's Set Theory, Lemma 15.30). – Gabe Goldberg Aug 26 '20 at 18:48
• I don't have my copy of Jech's book handy; I apologize if I'm just duplicating Gabe's comment. A Cohen-generic real $g:\omega\to2$ (over any $M$) has the following property: There are infinitely many $n\in\omega$ such that $g$ is identically $0$ on the interval $[n,n!!!]$. (Proof: The conditions that have such a run of $0$'s are dense in the Cohen forcing poset.) In contrast, random reals satisfy the strong law of large numbers. – Andreas Blass Aug 26 '20 at 18:59
• What is a description in terms of the definable powerset operation? E.g. we will have $$M[G]=\bigcup_{m\in M}L_{M\cap Ord}(m, G),$$ does that count? – Noah Schweber Aug 27 '20 at 0:08
• Also, the notation "$L(\alpha, X)$" is rather old-fashioned; more common is "$L_\alpha(X)$." This is helpful when we want to consider looking at the set of things constructible from multiple parameters (e.g. as in my previous comment). – Noah Schweber Aug 27 '20 at 0:09
• @TimothyChow For $x\in M[G]$, fix a name $\nu\in M$ with $\nu[G]=x$. Then from $\nu$ and $G$ we can recover $\nu[G]$ by iterating the definable powerset more-or-less $rank(\nu)$-many times; this means, since $M\cap Ord$ is an upper bound on that rank, that $x\in L_{M\cap Ord}(\nu,G)$. Conversely, for any transitive $N\models\mathsf{ZF}$ and any $y\in N$ we have $L_{N\cap Ord}(y)\subseteq N$, so apply this with $y=(\nu,G)$ and note that $M\cap Ord\le M[G]\cap Ord$ (indeed they're equal). (I can add this as an answer if you'd like.) – Noah Schweber Aug 27 '20 at 4:39

Tim, here are my answers (low on technical but hopefully high on intuition):

1. The answer to the first question is YES, with one provision. You need to update the $$L(\alpha,G)$$ with $$L(\alpha,G\cup M)$$. Here is the core idea: the minimal model is the constructible universe truncated at $$\alpha$$, where $$\alpha$$ is defined by you above. That means that $$M$$ is made of all constructibe sets from the empty set.

Now, if you throw in G, what do you do? You attempt to build the constructible sets from G (think of the similar notion of relative recursibility. It is , mutatis mutandis, just the same: constructibility is a closure operator on sets).

Onto your question: if you start from $$M_0$$, a transitive model which is not the minimal one, and you add G, you must add all the constructible sets from G AND M. As it turns out, that set is precisely $$M_0[G]$$.

1. Scott's idea is quite brilliant, basically it can be summed up as generic=random. The comments above are related to it, but not entirely: they talk about a special type of forcing, the so called random forcing, whereas Scott's (and yours ) idea is broader:

is all forcing nothing but some kind of randomness in disguise?

I think the answer is yes and no, it needs to be made precise: what does it mean to "toss a coin"?

One needs to relativise this basic construct to M (remember the story of Cohen entering M? Let us do it too).

Inside M, we can define formally law-like sequences of zeros and 1s, and therefore stipulate that a sequence is random if there is no law-like description of it in M. In this sense, to be made precise, I believe Scott's intuition is correct:

the function which corresponds to the ultrafilter is always M-random.

ADDENDUM: as per Andreas comment below, I think I overstated my claim. Genericity is definitely stronger than just being random. However, I still think that the other direction, namely that every generic is M-random, still holds.

• The proposed notion of randomness, that "there is no law-like description of it in $M$," is too weak to capture genericity. For example, if $M$ is a countable transitive model of ZFC, then there exists (outside $M$) a well-ordering of $\omega$ whose order-type equals that of the ordinals of $M$. A subset of $\omega$ coding such a well-ordering cannot be definable in $M$ but is also not $M$-generic for any notion of forcing $P\in M$. – Andreas Blass Aug 27 '20 at 15:12
• OK Andreas I hear you. M-random does not imply generic, too weak. Deal. But what about the other side, namely if something is generic, then it is necessarily M-random? It seems to me that this still holds. – Mirco A. Mannucci Aug 27 '20 at 15:37
• The converse is correct as long as the forcing notion is non-trivial, i.e., produces a model strictly including the ground model. The reason is that, if a subset of $\omega$ is definable in $M$ (i.e., is not "random" in your sense), then it is in $M$ because $M$ satisfies the axiom schema of separation. – Andreas Blass Aug 27 '20 at 16:00
• Precisely. Any attempt to make the sequence law-like from inside would automatically make G M-constructible, so end of game. Ok Andreas, then let us move it up a notch: you convinced me that generic > random. Assume for a moment that Scott 's intuition is correct, that means that random + X = generic, where X is something else. How about we try to find it? – Mirco A. Mannucci Aug 27 '20 at 16:05
• in other words, you subset A (for Andreas) which codes the ordinals is definitely M-random, but as you pointed out is not generic. Then, what is the difference between these two remaining in the real of randomness? Is there a way to say that G is "minimally" random whereas A is not? – Mirco A. Mannucci Aug 27 '20 at 16:07