Rapid filters and the Raisonnier family

Work in ZF. Here increasing means nondecreasing unless strictly increasing is written, and $f(n)$ denotes the finite ordinal $\{0,\dots ,f(n)-1\}$. A filter $F$ on $\omega$ in the sense of Filter on a set extends the Fréchet filter when it contains every cofinite set. A filter extending the Fréchet filter is rapid when for every increasing $f:\omega \to \omega$ there is $a\in F$ with

$\mathrm{\mid }a\cap f(n)\mathrm{\mid }\le n\text{for every }n<\omega \mathrm{.}$

Uniform-bounding form. The rapidity condition is equivalent to the following one, whose uniformity is what later estimates use: there is a single strictly increasing $g:\omega \to \omega$ such that for every increasing $f:\omega \to \omega$ there is $a\in F$ with $\mathrm{\mid }a\cap f(n)\mathrm{\mid }\le g(n)$ for all $n$. The forward direction takes $g(n)=n$. For the converse, given $g$ and an increasing $f$, apply the hypothesis to $f^{\ast }(n)=f(g(n+1))$ to obtain $a\in F$ with $\mathrm{\mid }a\cap f(g(n+1))\mathrm{\mid }\le g(n)$ for all $n$; then for $k\in [g(n),g(n+1))$ the monotonicity of $f$ gives $\mathrm{\mid }a\cap f(k)\mathrm{\mid }\le \mathrm{\mid }a\cap f(g(n+1))\mathrm{\mid }\le g(n)\le k$, and replacing $a$ by $a^{\ast }=a\setminus f(g(0))$, which preserves membership in $F$ because the Fréchet filter is contained in $F$, gives the exact inequality $\mathrm{\mid }{a}^{\ast }\cap f(k)\mathrm{\mid }\le k$ for all $k$ (the values below $g(0)$ being empty). Rapidity is thus witnessed by a single bounding function.

First differing prefix lengths and the Raisonnier family. For distinct $u,v\in 2^{\omega }$ let $h(u,v)=\min \{n:u\upharpoonright n\mathrm{\ne }v\upharpoonright n\}$ be their first differing prefix length. If the first differing coordinate is $k$, this length is $k+1$, because restriction to $n$ uses the coordinates strictly below $n$. Thus $h(u,v)\ge 1$. We retain this prefix-length convention from Ishii Definition 3.3 throughout $H$ and $F(x)$. For $X\subseteq 2^{\omega }$ put

$H(X)=\{h(u,v):u,v\in X,u\mathrm{\ne }v\}\mathrm{.}$

The closure of a set does not change $H$: if $u,v\in \bar{X}$ are distinct and $m=h(u,v)$, the length-$m$ cylinders about $u,v$ each meet $X$. Choose $u^{\mathrm{\prime }},v^{\mathrm{\prime }}$ in these two intersections. Their prefixes agree below $m-1$ and differ at $m-1$, so $h(u^{\mathrm{\prime }},v^{\mathrm{\prime }})=m$. This proves $H(\bar{X})\subseteq H(X)$; the reverse inclusion follows from $X\subseteq \bar{X}$. Only two existential witnesses are used, not a sequence of choices.

For precision, if $x\in {\omega }^{\omega }$ is a real, use its graph as a set predicate in the relativized constructible hierarchy. For nonempty $A$, ${\mathrm{Def}}_x(A)$ consists of subsets of $A$ definable with finitely many parameters in $(A,\in ,x\cap A)$; set ${\mathrm{Def}}_x(\mathrm{\varnothing })=\{\mathrm{\varnothing }\}$. This is the predicate version of Definable subsets of a membership structure: uniform set satisfaction for the membership relation and one unary predicate is supplied by Existence and uniqueness of set satisfaction, and Separation and Replacement collect the subsets defined by the set of formula codes and finite tuples. Define $L_0[x]=\mathrm{\varnothing }$, $L_{\alpha +1}[x]={\mathrm{Def}}_x(L_{\alpha }[x])$ and take unions at nonzero limits. Transfinite recursion constructs each set-length segment uniquely; uniqueness makes the segments agree, just as in The constructible hierarchy and constructible rank. Write $y\in L[x]$ for existence of an ordinal stage containing $y$, a class predicate rather than a set union over all ordinals. With $L[x]\cap 2^{\omega }$ viewed in Cantor sequence space, the Raisonnier family $F(x)\subseteq \mathcal{P}(\omega )$ is defined, for $a\subseteq \omega$, by

$a\in F(x)⟺\text{there is a countable cover }⟨F_n:n<\omega ⟩\text{ of }L[x]\cap 2^{\omega }\text{ with }{\bigcup }_{n<\omega }H(F_n)\subseteq a\mathrm{.}$

The cover members range over subsets of $2^{\omega }$; replacing them by their closures does not change the union of the $H(F_n)$, so the witnessing covers may always be taken to consist of closed sets. Replacement forms the sequence of closures directly. The definition uses no choice; the later filter and rapidity assertions about $F(x)$ are proved separately from it.