# Question about an example of forcing where we adjoin a new set of natural numbers

Forcing is quite new to me and there is a basic example in Jech that I don't understand. Let $P$ be the following notion of forcing: the forcing conditions are 0-1 sequences and $p$ is stronger than $q$ is $p$ extends $q$. If $M$ is a ground model, let $G\subset P$ be generic over $M$. Then let $f=\cup G$. Since $G$ is a filter then $f$ is a function.

My question is why does $G$ being a filter entails that $f$ is a function?

Since $G$ is a generic set, it has to meet all dense sets in $P$ which are in $M$ (so we can guarantee that the generic set exists). So $G$ contains some 0-1 sequences, and so $f$ is a bunch of 0-1 sequences.

But why is this guaranteed by $G$ being a filter? And what kind of function is $f$, more explicitly? Is $f$ a function taking natural numbers (maybe the length of the sequences) and have the sequences $p$ in its range?

Also: why do generic sets exist only if the ground model is countable. Does it have to do something with the dense sets?

Thanks

-

Your example is known as Cohen forcing; this was the very first notion of forcing ever used!

You're correct, the generic $G$ is not itself a function, it consists of a bunch of finite binary sequences. However, the fact that $G$ is a filter ensures that any two elements of $G$ agree on their common domain. Therefore, $g = \bigcup G$ is a (possibly partial) function $g:\omega\to2$ which extends all elements of $G$. In fact, $g$ must be a total function since each of the sets $D_n = \{p : n \in \mathrm{dom}(p)\}$ is open dense.

It is not true that generic sets exist only over countable model. What is true is that generic sets always exist over countable models (whatever the forcing may be). For example, Cohen generics exist over any model with size less than the cardinal $\mathrm{cov}(\mathcal{M})$. This cardinal can be strictly larger than $\aleph_1$, in which case Cohen generics exist over models of size $\aleph_1$. In fact, the canonical way to force $\mathrm{cov}(\mathcal{M}) > \aleph_1$ is to add $\aleph_2$ (or more) Cohen reals over the ground model!

-
So now the set $A$ of natural numbers defined by the function $f$ is not in the ground model because if you try to make $f$ equal some $g$ in $M$, any set $D_g$ that contains all $p$ included in $g$ (i.e $g$ is like $f$, it extends elements of the generic set $G$) won't be dense in $P$. By the way my $f$ if your $g$ and my $g$ is some function in the ground model. –  Carlo Von Schnitzel Apr 15 '10 at 2:41
It's not that your set $D_g$ of all $p \subseteq g$ is not dense, it's that the complement of $D_g$ is open dense and therefore must be met by the generic. (The function $\bigcup G$ is called the Cohen generic real, and it's standard to call it g for generic, but that's just tradition.) –  François G. Dorais Apr 15 '10 at 2:48
$g$ can't be as "big" as the Cohen generic real? The complement of $D_g$ for any $g$ inside $M$ has to be open dense because for any $p$ in $P$ there exists a $q$ in $D_g$ such that $q$ is stronger than $p$ and that is exactly the set of things of which $g$ is not stronger. I have the feeling I've got the logic of the statement completely wrong :) –  Carlo Von Schnitzel Apr 15 '10 at 3:04
oh I see, my confusion might be coming from the use of "stronger than" vs "inclusion of finite binary strings" –  Carlo Von Schnitzel Apr 15 '10 at 3:07
About the downwards vs. upwards order in forcing, see this question: mathoverflow.net/questions/17892/… –  Joel David Hamkins Apr 15 '10 at 3:21

Yes, the union of a filter in this case is a function.

The reason is that the conditions in your poset are themselves (I think you probably mean finite) functions, and the order ensures that compatible conditions agree on their common domain. The filter G is therefore a bunch of finite functions that each agree on their common domain. Thus, the union of the filter is a function on the union of the domains of the conditions appearing in it.

You asked what kind of function is f, the union of G. The function f in this case will be an infinite binary sequence, that is, a function from ω to 2. The function f has the common values of the conditions appearing in G, so that f(n) = p(n) for any p appearing in G for which n is in dom(p).

Perhaps the confusion results from using the terms string or sequence to mean a function on the natural numbers. In this set-theoretic conctext, a finite binary string means a function from the set {0,1,...,n-1} to {0,1}, that is, a function from n to 2. So the partial order here is 2, the set of finite binary sequences.

-
Again nearly tied! –  François G. Dorais Apr 15 '10 at 1:58
Thank you to both of you. Your answers cleared things up a lot. –  Carlo Von Schnitzel Apr 15 '10 at 2:15
Since you mention partial orders, can one do forcing with say an Aronszajn tree or a Kurepa tree as the notion of forcing? It seems like it is the choice of the partial ordering that is going to influence what you can add or can't add in your ground model. –  Carlo Von Schnitzel Apr 15 '10 at 2:30
Forcing with a Souslin tree is particularly interesting, since it will have the c.c.c. (Of course, one turns the trees upside down before forcing.) This will add a branch through the tree, while preserving cardinals, thus killing the tree as a Sousline tree. Iterating this forcing kills all Souslin trees, and shows the relative consistency of the statement that there are no Souslin trees. This result is due to Solovay and Tennenbaum, and is how iterated forcing was invented. Martin observed that the same idea can be used when iterating any c.c.c. forcing, leading to Martin's Axiom. –  Joel David Hamkins Apr 15 '10 at 2:36
Yes, you can force with any poset. In the case of an Aronszajn tree (turned up side down) you add an new $\omega_1$-branch through the tree, thereby destroying its Aronszajn-ness in the extension. However, you may also collapse $\aleph_1$ to $\aleph_0$ in the process, unless you forced with a Suslin tree in which case $\aleph_1$ is preserved. –  François G. Dorais Apr 15 '10 at 2:36