Shelah's universal-meagre forcing

Work in ZF with the usual cylinder topology on Cantor space $2^{\omega }$. For a finite word $s$, its cylinder consists of all infinite binary extensions of $s$. The universal-meagre forcing $\mathrm{U}\mathrm{M}$ has a distinguished weakest condition $1_{\mathrm{U}\mathrm{M}}$ and the following nontrivial conditions. A nontrivial condition is a pair $(t,T)$ where $T\subseteq 2^{<\omega }$ is a nonempty subtree in the sense of Trees and their bodies that is perfect — every node of $T$ has two incomparable extensions in $T$ — and whose body $[T]$ is nowhere dense in the sense of Nowhere dense, meagre, residual, and comeagre subsets of a topological space; and $t=T\cap 2^{\le n}$ is its finite initial tree through some height $n<\omega$. Because $T$ is nonempty, downward closed and perfect, it contains the empty node and has a node at every level. Thus $n$ is recovered from $t$ as $\mathrm{ht}(t):=\max \{\mathrm{\mid }s\mathrm{\mid }:s\in t\}$; this is the meaning of the height of a recorded tree below. In the library order of Forcing preorders, compatibility and filters, Dense open sets and generic filters over a model, every condition is below $1_{\mathrm{U}\mathrm{M}}$, and the order between nontrivial conditions is

$(t_2,T_2)\le (t_1,T_1)⟺T_1\subseteq T_2\text{ and }{t}_1=t_2\cap 2^{\le \mathrm{ht}(t_1)}\mathrm{.}$

The symbol $1_{\mathrm{U}\mathrm{M}}$ is not represented by an empty tree. This is the separately adjoined weak condition used for zero coordinates in Shelah's canonical embeddings; excluding an empty recorded tree prevents the vacuous ``perfectness'' convention from creating a second, absorbing condition.

Thus a stronger condition enlarges the witness tree while permanently preserving the recorded finite initial tree. A condition is determined by its witness tree and its height; the recorded tree is a sub-tree of every witness tree extending it, so the extension relation is reflexive and transitive. $\mathrm{U}\mathrm{M}$ is nonempty: the perfect tree $T_0=\{\sigma \in 2^{<\omega }:\sigma$ contains no two consecutive $1$s$\}$ is nowhere dense, because every cylinder contains a string with two consecutive $1$s and hence no cylinder is contained in $[T_0]$.

Basic properties used below. Let $(t_1,T_1)$, $(t_2,T_2)$ be nontrivial conditions with $\mathrm{ht}(t_1)\le \mathrm{ht}(t_2)$. A common strengthening $(\tilde{t},\tilde{T})$ satisfies $\tilde{T}\supseteq T_1\cup T_2$ and $\tilde{t}\cap 2^{\le \mathrm{ht}(t_1)}=t_1$, $\tilde{t}\cap 2^{\le \mathrm{ht}(t_2)}=t_2$; hence two conditions are necessary for compatibility: $t_1=t_2\cap 2^{\le \mathrm{ht}(t_1)}$, and every node of $T_1$ of height at most $\mathrm{ht}(t_2)$ belongs to $t_2$. These two conditions are also sufficient: if $T:=T_1\cup T_2$, then $T$ is a subtree, it is perfect because every node of $T$ splits inside whichever of $T_1,T_2$ contains it, its body $[T]=[T_1]\cup [T_2]$ is nowhere dense as a finite union of closed nowhere-dense sets, and $T\cap 2^{\le \mathrm{ht}(t_2)}=t_2$, so $(t_2,T)$ is a common strengthening of $(t_1,T_1)$ and $(t_2,T_2)$. The first condition alone is not sufficient: for $T_1$ the tree of strings with no two consecutive $0$s and $T_2$ the tree of strings with no two consecutive $1$s one has $\mathrm{ht}(t_1)=1$, $\mathrm{ht}(t_2)=2$, $t_1=t_2\cap 2^{\le 1}=\{\mathrm{\varnothing },0,1\}$, yet $11\in T_1\cap 2^{\le 2}$ while $11\mathrm{\notin }{t}_2$, so the two conditions have no common strengthening. In particular the conditions carrying one fixed recorded tree $t$ are pairwise compatible: their witness trees agree on $2^{\le \mathrm{ht}(t)}$, so their union is again a witness tree, it is perfect because every node splits inside one of the two trees, it is nowhere dense as a finite union of closed nowhere-dense sets, and its initial tree through height $\mathrm{ht}(t)$ is $t$. Two conditions whose recorded trees disagree on the levels common to both heights are incomparable, since a common strengthening would have to record both trees below the shorter height; distinct perfect nowhere-dense trees can disagree on such a level, so compatibility of $\mathrm{U}\mathrm{M}$ is not automatic. For a condition $(t,T)$ and a node $\sigma \in T$, the conditions below $(t,T)$ whose recorded tree contains $\sigma$ are dense in the cone below $(t,T)$, because one extends the height past $\mathrm{\mid }\sigma \mathrm{\mid }$. They need not be dense in all of $\mathrm{U}\mathrm{M}$, since conditions incompatible with $(t,T)$ have no such extension. For the generic-object assertion, compute $\mathrm{U}\mathrm{M}$ in a transitive ZF ground model $M$ and let $G$ be an $M$-generic filter as in Dense open sets and generic filters over a model. A set $D\in M$ dense below $p\in G$ is met by $G$: adjoining all conditions incompatible with $p$ makes it dense in the whole forcing, and directedness excludes those incompatible conditions from $G$. Consequently, every witness tree of a nontrivial condition in $G$ is contained in the generic tree

$U_G=\bigcup \{t:\text{some }(t,T)\in G\}=\bigcup \{T:(t,T)\in G\},$

This union is nonempty because nontrivial conditions are dense. It is a tree, and each of its nodes lies in a witness tree contained in the union; that witness supplies two incomparable extensions, proving perfection. Its body is closed: a real outside the body has a finite prefix absent from the tree and the corresponding cylinder misses the body.

Nowhere density needs a separate dense-set argument. Given any finite word $s$ and nontrivial condition $(t,T)$, the closed nowhere-dense body $[T]$ has a cylinder $[v]\subseteq [s]$ disjoint from it. Here $v\mathrm{\notin }T$: every node of the pruned binary tree $T$ lies on a branch, obtained by recursively taking the least available child. Increase the recorded height to at least $\mathrm{\mid }v\mathrm{\mid }$, keeping $T$ unchanged. All stronger conditions now omit $v$ from their witness trees. Thus the conditions recording such a missing extension of $s$ form a ground-model dense set (also below $1_{\mathrm{U}\mathrm{M}}$). Genericity meets it, and filter directedness ensures that $v$ belongs to no witness tree from $G$. Every cylinder therefore contains a cylinder disjoint from $[U_G]$, proving that $[U_G]$ is nowhere dense. These arguments use finite binary recursion, not a choice principle.

The finite-prefix rearrangements are precisely the maps ${\pi }_{\rho }(s⌢x)=\rho (s)⌢x$, for $s\in 2^n$, $x\in 2^{\omega }$, and a permutation $\rho$ of the finite set $2^n$, for some $n<\omega$. Each map is a homeomorphism preserving the tail after coordinate $n$. There are countably many such maps, since these permutations have finite codes. A partial bijection on $2^n$ extends to one by matching unused domain and range words in lexicographic order; it is this full permutation, not an arbitrary homeomorphic extension, that defines the rearrangement.

The forcing is ccc, since it is the union of countably many directed sets: the singleton $\{1_{\mathrm{U}\mathrm{M}}\}$ is one such set, and for each finite tree $t$ the class of conditions of $\mathrm{U}\mathrm{M}$ carrying the recorded tree $t$ is directed by the paragraph above, and there are only countably many finite trees $t$. Hence $\mathrm{U}\mathrm{M}$ is a countable union of directed sets, and an antichain meets each directed class in at most one element because any two members of one class are compatible. Assigning each antichain member the least code of a class containing it gives an injection into $\omega$, including for the empty antichain. This proves ccc without choice.

The point of the forcing is not that the generic tree contains an arbitrary old nowhere-dense tree: the old sets are absorbed at the next stage, by the countable union of finite-prefix rearrangements of $[U_G]$ constructed in A universal-meagre generic absorbs old nowhere-dense sets, and the assertion $[S]\subseteq [U_G]$ for an arbitrary old tree $S$ is never used.