Coanalytic ultrafilter bases

Abstract

We study the definability of ultrafilter bases on $\omega$ in the sense of descriptive set theory. As a main result we show that there is no coanalytic base for a Ramsey ultrafilter, while in L we can construct $\Pi ^1_1$ P-point and Q-point bases. We also show that the existence of a ${\varvec{\Delta }}^1_{n+1}$ ultrafilter is equivalent to that of a ${\varvec{\Pi }}^1_n$ ultrafilter base, for $n \in \omega$. Moreover we introduce a Borel version of the classical ultrafilter number and make some observations.

1 Introduction

This paper follows the line of many papers studying the definability, in the sense of descriptive set theory, of certain combinatorial subsets of the real line such as mad families [6, 15, 16], independent families [3, 15], maximal eventually different families [18], maximal cofinitary groups [9], maximal orthogonal families of measures [7] or maximal towers and inextendible linearly ordered towers [8]. In this paper we will study the definability of ultrafilters and more specifically ultrafilter bases. Recall that a set $X \subseteq \mathcal {F}$ is a base for a filter $\mathcal {F}$, if for every $x \in \mathcal {F}$, there is $y \in X$ with $y \subseteq x$. Filters will always live on $\omega$ and contain all cofinite sets. Thus a filter is a subset of the Polish space $\mathcal {P}(\omega )$ and we can study its definability. It is well known that an ultrafilter can neither have the Baire property nor be Lebesgue measurable (see e.g. [1, Theorem 4.1.1]). This already rules out the existence of analytic ultrafilter generating sets as the generated filter will also be analytic and thus have the Baire property. But this still leaves open the possibility of a coanalytic ultrafilter base since a priori the generated set will only be ${\varvec{\Delta }}^1_2$. The main purpose of this paper is to study which ultrafilters can have a coanalytic basis.

Recall that for $x,y \in [\omega ]^\omega$ we write $x \subseteq ^* y$ whenever $x {\setminus } y$ is finite. An ultrafilter $\mathcal {U}$ is called a P-point if for any countable $\mathcal {F} \subseteq \mathcal {U}$, there is $x \in \mathcal {U}$ so that $\forall y \in \mathcal {F} (x \subseteq ^* y)$. $\mathcal {U}$ is a Q-point if for any partition $\langle a_n : n \in \omega \rangle$ of $\omega$ into finite sets $a_n$, there is $x \in \mathcal {U}$ so that $\forall n \in \omega (\vert x \cap a_n\vert \le 1)$. A Ramsey ultrafilter is an ultrafilter that is both a P- and a Q-point. A more commonly known and equivalent definition for Ramsey ultrafilters $\mathcal {U}$ is that for any coloring $c :[\omega ]^2 \rightarrow 2$, there is $x \in \mathcal {U}$ so that c is homogeneous on x, i.e. $c \restriction [x]^2$ is constant. In fact we will show in Sect. 3 that:

Theorem 1.1

There is a $\Pi ^1_1$ base for a P-point in the constructible universe L.

Theorem 1.2

There is a $\Pi ^1_1$ base for a Q-point in the constructible universe L.

Section 2 will provide an introduction to the techniques employed in proving these results. In strong contrast we will show in Sect. 4 that:

Theorem 1.3

There is no ${\varvec{\Pi }}^1_1$ base for a Ramsey ultrafilter.

Before stating the next theorem, notice that any ultrafilter that is ${\varvec{\Sigma }}^1_n$ or ${\varvec{\Pi }}^1_n$ is already ${\varvec{\Delta }}^1_n$. Namely suppose that $\varphi$ defines an ultrafilter, then we have that $\varphi (x) \leftrightarrow \lnot \varphi (\omega {\setminus } x)$. Moreover any base for an ultrafilter that is ${\varvec{\Sigma }}^1_n$ or ${\varvec{\Pi }}^1_n$ generates a ${\varvec{\Delta }}^1_n$ or respectively a ${\varvec{\Delta }}^1_{n+1}$ ultrafilter.

In Sect. 5 we will compare the existence of ${\varvec{\Delta }}^1_{n+1}$ ultrafilters to that of ${\varvec{\Pi }}^1_n$ bases, for $n \in \omega$. As a main result we find that:

Theorem 1.4

The following are equivalent for any $r \in 2^\omega$, $n \in \omega$.

• (1) There is a $\Delta ^1_{n+1} (r)$ ultrafilter.

• (2) There is a $\Pi ^1_n(r)$ ultrafilter base.

Let us remark that we can use Theorem 1.4 to show that there is a $\Pi ^1_1$ ultrafilter base in L by simply finding a $\Delta ^1_2$ ultrafilter. This is a much easier task than constructing a $\Pi ^1_1$ base directly (see more in Sect. 2). On the other hand, Theorem 1.1 and Theorem 1.2 can not be followed in this way. As we shall see (Remark 5.2), the proof of Theorem 1.4 never yields a base for a P-point nor a Q-point. In fact, using a result of Shelah combined with Theorem 1.3, we will provide a model in which ${\varvec{\Delta }}^1_2$ P-points exist but are never generated by ${\varvec{\Pi }}^1_1$ bases (see Theorem 5.1).

In Sect. 6 we study the effects of adding reals to the definability of ultrafilters. Recall that a real $x \in [\omega ]^\omega$ is called splitting over A, if for any $y \in A \cap [\omega ]^\omega$, $x \cap y$ and $y {\setminus } x$ are infinite. We will see that classical forcing notions adding splitting reals, and as a consequence destroying ground model ultrafilters, namely Cohen, Random and Silver forcing, cannot preserve definitions for ultrafilters. This is related to a result of Brendle and Khomskii (see [4]), which shows that it is possible to destroy all ground model mad families by adding dominating reals while having a $\Pi ^1_1$ mad family in the extension.

In Sect. 7 we introduce a new cardinal invariant that is a Borel version of the classical ultrafilter number $\mathfrak {u}$ and make some observations. Similar cardinal invariants have been defined for mad families (see [16] or [4]) and maximal independent families (see [3]).

2 An introduction to Miller’s coding technique

All our constructions of coanalytic objects in $L$ will rely on a technique that was brought to wider attention by A. Miller in his fundamental paper [15]. It is originally due to Erdős, Kunen and Mauldin [5] who used it to construct a so called scale with a $\Pi ^1_1$ definition. For more information we also refer to [23]. The purpose of this section is to give an informal outline of the technique and to define the basic notions that we will use in our proofs. More details will appear in the proofs of Theorem 1.1 and 1.2 in the next section. We hope that this helps readers which are unfamilar with the method. Another good explanation can be found in [10, §3]

When we say that z codes the ordinal $\alpha$, we mean the following. To any real $z \in 2^\omega$ we associate a relation $E_z$ on $\omega$ defined by

$$\begin{aligned} E_z(n,m) \leftrightarrow z(2^n 3^m) =1. \end{aligned}$$

This relation may be a linear order and if it is a well-order and isomorphic to $\alpha$ we say that it codes $\alpha$. Such $\alpha$ is unique and we define $\Vert z \Vert := \alpha$. More generally we say that z codes M if $(\omega ,E_z)$ is isomorphic to $(M,\in )$. The set of $z \in 2^\omega$ coding an ordinal is denoted ${{\,\mathrm{WO}\,}}$. The set ${{\,\mathrm{WO}\,}}$ is tightly connected to coanalytic sets. On one hand side, ${{\,\mathrm{WO}\,}}$ is itself $\Pi ^1_1$ and on the other, for any ${\varvec{\Pi }}^1_1$ set $X \subseteq 2^\omega$, there is a continuous function $f :2^\omega \rightarrow 2^\omega$ so that $X = f^{-1}({{\,\mathrm{WO}\,}})$.

There is a canonical way of defining in $L$ various combinatorial subsets X of reals in a $\Delta ^1_2$ fashion. This goes back to Gödel who remarked in [11, p. 67] that the canonical well-order of the reals in $L$ is in fact $\Delta ^1_2$. Typically the elements are found recursively by making adequate choices which are absolute between models of the form $L_\alpha$ (e.g. taking the $<_L$ least candidate which has some simple property holding with respect to the previously chosen reals).

Then $x \in X$ can be written as

$$\begin{aligned} \underbrace{\text {}\exists M}_{\exists } \text {}[\text {}\underbrace{ M\text { is well-founded}}_{\forall }, \underbrace{\text {}x \in M}_{\Delta ^1_1} \text { and } \underbrace{M \models V = L \wedge \varphi (x)}_{\Delta ^1_1}\text {}] \end{aligned}$$

(1)

or as

$$\begin{aligned} \underbrace{\text {}\forall M \models V=L, x \in M}_{\forall + \Delta ^1_1} [\text {} \underbrace{ M\text { is not well-founded }}_{\exists } \text { or } \underbrace{M \models \varphi (x)}_{\Delta ^1_1}\text {}], \end{aligned}$$

(2)

where $\varphi (x)$ is an appropriate formula in the language of set theory that expresses that there is a sequence according to the recursive construction of which x is the last member.

Quantifying over models is shorthand for quantifying over codes in $2^\omega$ of countable models satisfying some basic set theoretic axioms. Thus e.g. (1) can be recast as “$\exists z \in 2^\omega ((\omega ,E_z) \text { is well-founded, } x \in (\omega ,E_z) \text { and } (\omega ,E_z) \models V = L \wedge \varphi (x))$”, where $x \in (\omega , E_z)$ means that $x \in M$ for M the Mostowski collapse of $(\omega ,E_z)$. It is not difficult to see that this can be expressed in a $\Delta ^1_1$ way.

As such, finding a $\Delta ^1_2$ ultrafilter base in $L$ is very simple. The major improvement in Miller’s technique is to get rid of the first existential quantifier in (1). This is done by letting x already encode a relevant well-founded model M in a Borel or even in a recursive way. Then if C is the Borel coding relation used, the definition usually looks as follows:

$$\begin{aligned} \underbrace{x \in Y}_{\forall } \text { and }\underbrace{\text {}\forall z \in 2^\omega }_{\forall } [\underbrace{\lnot C(x,z)}_{\Delta ^1_1} \text { or } \underbrace{ (\omega ,E_z) \models V=L \wedge \varphi (x)}_{\Delta ^1_1}], \end{aligned}$$

(3)

for some known coanalytic Y.

Lemma 2.1

There is a lightface Borel set $C \subseteq (2^\omega )^3$ so that whenever z codes $\alpha < \omega _1$ and $r,y \in 2^\omega$ then $(z,r,y) \in C$ iff y codes $L_\alpha [r]$.

Proof

The claim is easy to verify by noting that an adequate $E_{y}$ can be constructed by recursion on $\alpha$ following a rule that can be expressed in a $\Delta ^1_1$ way. Thus $(z,r,y) \in C$ can be defined by formulas $\exists (y_n)_{n \in \omega } \in (2^\omega )^\omega \left( \phi ((y_n)_n, r, z) \wedge y = \bigcup _{n \in \omega } y_n \right)$ and $\forall (y_n)_{n \in \omega } \in (2^\omega )^\omega \left( \phi ((y_n)_n, r, z) \rightarrow y = \bigcup _{n \in \omega } y_n \right)$, where $\phi ((y_n)_n, r, z)$ is a $\Delta ^1_1$ formula expressing that $(y_n)_{n\in \omega }$ is constructed in some canonical way by recursion on the well-order $(\omega ,E_z)$ according to the rules of the L[r] hierarchy. $\square$

Lemma 2.2

There is a recursive function $(\cdot )^{+\omega } :2^\omega \rightarrow 2^\omega$ so that whenever z codes $\alpha$, then $(z)^{+\omega }$ codes $\alpha + \omega$.

Proof

Let $(z)^{+\omega } = y$ such that $y(2^n3^m) = 1$ iff ${\left\{ \begin{array}{ll} n \text { even } \wedge m \text { even } \wedge z(2^\frac{n}{2}3^\frac{m}{2}) = 1 \\ n \text { even } \wedge m \text { odd } \\ n \text { odd } \wedge m \text { odd } \wedge n < m. \end{array}\right. }$

$\square$

3 $\varvec{\Pi }^1_1$ bases for P- and Q-points

In [8] the authors constructed, using Miller’s technique, a coanalytic tower (i.e. a set $X \subseteq [\omega ]^\omega$ well-ordered wrt $^*\supseteq$ and with no pseudointersection). A crucial property of the tower was that all its elements were split by the set of even natural numbers. In particular this meant that the tower could not generate an ultrafilter. We will construct in L a tower generating an ultrafilter and thus generating a P-point.

Before we start to construct the $\Pi ^1_1$ P-point base, we need some ingredients.

Definition 3.1

We call $\mathcal {W}^+$ the set of $x \in [\omega ]^\omega$ containing arbitrary long arithmetic progressions, i.e. $\forall k \in \omega \exists a,b \in \omega ( \{a\cdot l + b : l <k \} \subseteq x)$.

The following fact follows from Van der Waerden’s Theorem [21] and is well known.

Fact. The set $\mathcal {W} = \mathcal {P}(\omega ) {\setminus } \mathcal {W}^+$ is a proper ideal on $\omega$. It is called the Van der Waerden ideal.

Proof of Theorem 1.1

First, let us introduce some notation and repeat some basic facts that we are going to use in the construction. We will work in L throughout. Let $(y_\alpha )_{\alpha < \omega _1}$ enumerate $[\omega ]^\omega$ via the global L well-order $<_L$. The statement “y is the $\alpha$’th element according to $<_L$” is absolute between $L_\beta$’s with $y \in L_\beta$ and $\alpha \in L_\beta$ (see e.g. [14, 13.19]). Let $O :2^\omega \rightarrow 2^\omega$ be the following lightface Borel function: If $x \subseteq \omega$ we want to define a unique sequence $(i_n)_{n \in \omega }$ of subsets of $\omega$ so that $\max i_n < \min i_{n+1}$ and $i_{n+1}$ is the next maximal arithmetic progression in x of length $\ge 3$ above $\max i_{n}$ (note that any pair of natural numbers forms an arithmetic progression). Now if this sequence can be defined up to $\omega$ (in particular every $i_n$ is finite), then we define $O(x)(n) = 1$ iff $i_n$ has even length. Else we let $O(x)(n)=0$. We say that an ordinal $\delta$ projects to $\omega$, if $L_{\delta + \omega } \models \text {``} \delta \text { is countable''}$. It is not hard to see that the set of ordinals projecting to $\omega$ is unbounded in $\omega _1$ (see e.g. the proof of [22, Theorem 2.6]).

We now construct a sequence $(x_\xi , \delta _\xi )_{\xi < \omega _1}$ where $x_\xi \in [\omega ]^\omega$, $\delta _\xi < \omega _1$ for every $\xi < \omega _1$, as follows. Given $(x_\xi , \delta _\xi )_{\xi < \alpha }$ we let $\delta _\alpha$ be the least limit ordinal such that $\sup _{\xi< \alpha }{\delta _\xi } < \delta _\alpha$, $y_\alpha \in L_{\delta _\alpha }$ and $\delta _\alpha$ projects to $\omega$. We then choose $x_\alpha = x$ least in the $<_L$ well-order so that

• (a) $x \subseteq ^* x_\xi$ for every $\xi < \alpha$,

• (b) $x \in \mathcal {W}^+$

• (c) $x \subseteq y_\alpha$ or $x \subseteq \omega {\setminus } y_\alpha$.

• (d) O(x) codes $\delta _\alpha$.

Note that any sequence $(x_\xi )_{\xi < \omega _1}$ defined as above is a tower generating an ultrafilter. Namely, by (a), the sequence is decreasing with respect to $\subseteq ^*$, and if $y \in [\omega ]^\omega$ is arbitrary, say $y = y_\alpha$ for $\alpha < \omega _1$, then by (c), $x_\alpha$ is contained in either y or its complement.

Claim

$x_\alpha$ can be found in $L_{\delta _\alpha + \omega }$.

Proof

Note that the definition of $(x_\xi )_{\xi < \alpha }$ is absolute between $L_\beta$’s. In particular $(x_\xi )_{\xi < \alpha }$ can be defined over $L_{\delta _\alpha }$. As $\delta _\alpha$ projects to $\omega$, there is an enumeration $(x^n)_{n \in \omega }$ of $\{x_\xi : \xi < \alpha \}$ in $L_{\delta _\alpha + \omega }$. Given $y_\alpha$ we have that, as $\mathcal {W}$ is an ideal, that for every $\xi < \alpha$, $y_\alpha \cap x_\xi \in \mathcal {W}^+$ or $\omega {\setminus } y_\alpha \cap x_\xi \in \mathcal {W}^+$. Assume wlog that for cofinally many $x_\xi$, $y_\alpha \cap x_\xi \in \mathcal {W}^+$ is the case. This implies that for all $x_\xi$ this is the case as $(x_\xi )_{\xi < \alpha }$ forms a tower. Again as $\delta _\alpha$ projects to $\omega$, there is a real $z \in L_{\delta _\alpha + \omega } \cap 2^\omega$ coding $\delta _\alpha$. Now we define a sequence $(i_n)_{n\in \omega }$ of finite subsets of $\omega$ so that $\max i_n < \min i_{n+1}$, $i_n \subseteq y_\alpha \cap \bigcap _{k \le n} x^k$, $i_n$ consists of an arithmetic progression so that its length is $\ge n$ and it is even iff $z(n) = 1$. Moreover $\min i_n$ is chosen large enough so that $i_{n-1} \cup i_n$ cannot form an arithmetic progression. $x := \bigcup _{n \in \omega } i_n$ can be defined in $L_{\delta _\alpha + \omega }$ and satisfies (a)–(d). Thus in particular the $<_L$-least such x exists in $L_{\delta _\alpha + \omega }$. $\square$

Claim

There is a formula $\varphi (x)$ in the language of set theory so that $\varphi (x)$ iff $\exists \xi (x = x_\xi )$ and $L_{\beta } \models \varphi (x)$ for some $\beta$ implies that $\varphi (x)$ is true. Moreover $L_{\delta _\xi + \omega } \models \varphi (x_\xi )$ for every $\xi$.

Proof

$\varphi (x)$ expresses that there is an ordinal $\alpha$ and a sequence $(x_\xi , \delta _\xi )_{\xi \le \alpha }$ according to the recursive definitions given above so that $x = x_\alpha$. $\square$

Now we can check that the set $X = \{x_\xi : \xi \in \omega _1 \}$ is $\Pi ^1_1$. Let C and $(\cdot )^{+\omega }$ be as in Lemmas 2.1 and 2.2. Then $x \in X$ iff

$$\begin{aligned} O(x) \in {{\,\mathrm{WO}\,}}\text { and }\forall z [\lnot C(O(x)^{+\omega },0,z) \text { or } (\omega ,E_z) \models \varphi (x)] . \end{aligned}$$

$\square$

We will now turn to the proof of Theorem 1.2.

Definition 3.2

The ideal ${\text {Fin}}^2$ on $\omega \times \omega$ consists of $x \in \mathcal {P}(\omega \times \omega )$ so that $\forall ^\infty n \in \omega \forall ^\infty m \in \omega (\langle n,m \rangle \notin x)$. Here, $\forall ^\infty$ is an abreviation of “for all but finitely many”.

Proof of Theorem 1.2

The ultrafilter that we construct will live on $\omega \times \omega$. Let $O :({\text {Fin}}^2)^+ \rightarrow 2^\omega$ be the following Borel function. Given $x \in ({\text {Fin}}^2)^+$ let $x_0,x_1$ be the first two infinite vertical sections of x. We denote with $x_0(n)$ or $x_1(n)$ the n’th element of $x_0$ or $x_1$. Then

$$\begin{aligned} O(x)(n) = {\left\{ \begin{array}{ll} 0 \quad \text { if } x_0(n)\ge x_1(n) \\ 1 \quad \text { if } x_1(n) > x_0(n). \end{array}\right. } \end{aligned}$$

As in the proof of Theorem 1.1 we let $(y_\alpha )_{\alpha < \omega _1}$ enumerate $[\omega \times \omega ]^\omega$ and $(P_\alpha )_{\alpha < \omega _1}$ enumerate all partitions of $\omega \times \omega$ into finite sets via the well-ordering $<_L$.

Similarly to the proof of Theorem 1.1 we construct a sequence $(x_\xi , \delta _\xi )_{\xi < \omega _1}$ where $x_\xi \in ({\text {Fin}}^2)^+$, intersections of finitely many elements in $\{x_\xi : \xi < \omega _1 \}$ are in $({\text {Fin}}^2)^+$ and $\delta _\xi < \omega _1$ as follows.

Given $(x_\xi , \delta _\xi )_{\xi < \alpha }$ we let $\delta _\alpha$ be the least limit ordinal such that $\sup _{\xi< \alpha }{\delta _\xi } < \delta _\alpha$, $y_\alpha , P_\alpha \in L_{\delta _\alpha }$ and $\delta _\alpha$ projects to $\omega$. $x_\alpha = x$ is then chosen least in the $<_L$ well-order so that

• (a) $\{ x \} \cup \{x_\xi : \xi < \alpha \}$ has all finite intersections in $({\text {Fin}}^2)^+$,

• (b) $x \in ({\text {Fin}}^2)^+$,

• (c) $x \subseteq y_\alpha$ or $x \subseteq \omega {\setminus } y_\alpha$,

• (d) for every $a \in P_\alpha$, $\vert a \cap x \vert \le 1$,

• (e) O(x) codes $\delta _\alpha$.

Again we show that such an $x_\alpha$ exists and can be found in $L_{\delta _\alpha + \omega }$.

Claim

$x_\alpha$ can be found in $L_{\delta _\alpha + \omega }$.

Proof

We have that if $(x_\xi )_{\xi <\alpha }$ exists then it must be definable over $L_{\delta _\alpha }$. As $\delta _\alpha$ projects to $\omega$ there is in $L_{\delta _\alpha + \omega }$ an enumeration $(x^n)_{n\in \omega }$ of all finite intersections of elements in $\{x_\xi : \xi <\alpha \}$. We are given $y_\alpha \in L_{\delta _\alpha }$. It is not hard to see that either $y_\alpha$ or $(\omega \times \omega ) {\setminus } y_\alpha$ is in $({\text {Fin}}^2)^+$ and has $({\text {Fin}}^2)^+$ intersection with all $x^n$. Without loss of generality we assume $y_\alpha$ has this property. Let $P_\alpha = \{ a_i : i \in \omega \}$ and $z \in 2^\omega \cap L_{\delta _\alpha + \omega }$ code $\delta _\alpha$. Further let $k_0<k_1$ be first so that the $k_0$’th and $k_1$’th vertical section of $y_\alpha$ is infinite. Let $(p_j)_{j \in \omega }$ enumerate $\omega \times \omega$ in a way that every pair (n, m) appears infinitely often. Given $(p_j)_{j \in \omega }$ we define recursively a sequence $\langle m^0_i , m^1_i \rangle _{i \in \omega }$ and auxiliarily $(n_i)_{i \in \omega }$ as follows:

• for every i, $\langle m^0_i , m^1_i \rangle \in y_\alpha$, $\langle m^0_i , m^1_i \rangle \notin \bigcup _{j< i} a_{n_j}$ and $\langle m^0_i , m^1_i \rangle \in a_{n_i}$,

• if $i = 3 j$ for $j \in \omega$, then $\langle m^0_i , m^1_i \rangle$ is in the $p_j(0)$’th infinite vertical section of $y_\alpha \cap x^{p_j(1)}$ greater than $k_1$,

• if $i = 1 \mod 3$ then $m^0_i = k_0$ and $m^0_{i+1} = k_1$ and $m^1_i \ge m^1_{i+1}$ or $m^1_{i+1} > m^1_i$ depending on whether $z(i) =0$ or $z(i) =1$.

Now the set $\{\langle m_i^0,m_i^1 \rangle : i \in \omega \} \in L_{\delta _\alpha +\omega }$ satisfies (a)-(e) as can be seen from the construction. In particular $L_{\delta _\alpha + \omega }$ contains the $<_L$-least such set. $\square$

The set $\{x_\xi : \xi < \omega _1 \}$ is now a base for a Q-Point and as in the proof of Theorem 1.1 it is $\Pi ^1_1$. $\square$

4 There are no ${\varvec{\Pi }}^1_1$ Ramsey ultrafilter bases

Definition 4.1

Let $\mathcal {F}$ be a filter. Then the forcing ${\mathbb {M}}(\mathcal {F})$ consists of pairs $(a,F) \in [\omega ]^{<\omega } \times \mathcal {F}$ such that $\max a < \min F$. A condition (b, E) extends (a, F) if b is an end-extension of a, $E \subseteq F$ and $b {\setminus } a \subseteq F$.

${\mathbb {M}}(\mathcal {F})$ is the natural forcing to add a pseudointersection of $\mathcal {F}$. Namely, whenever G is ${\mathbb {M}}(\mathcal {F})$-generic over V, then $x = \bigcup \{ a \in [\omega ]^{<\omega } : \exists F \in \mathcal {F} ((a,F) \in G)\}$ is a pseudointersection of $\mathcal {F}$ and we call x the generic real added by ${\mathbb {M}}(\mathcal {F})$.

Definition 4.2

Let $\mathcal {F}$ be a filter. Then we define the game $G(\mathcal {F})$ as follows:

$$\begin{aligned}{}[Arrayh]\begin{array}{c | c c c c c c} \hbox {Player I} &{} F_0 \in \mathcal {F} &{} &{} F_1 \in \mathcal {F} &{} &{} \dots \\ \hbox {Player II} &{} &{} a_0 \in [F_0]^{<\omega } {\setminus } \{\emptyset \} &{} &{} a_0 \in [F_1]^{<\omega } {\setminus } \{\emptyset \} &{} &{} \dots \end{array} \end{aligned}$$

Player II wins iff $\bigcup _{n \in \omega } a_n \in \mathcal {F}$.

Lemma 4.1

Let $\mathcal {F}$ be a filter on $\omega$ and let $\theta \ge (2^{2^{\aleph _0}})^+$. Then TFAE:

• (i) For any countable elementary submodel $M \preccurlyeq H(\theta )$ with $\mathcal {F} \in M$, there is $x \in \mathcal {F}$, ${\mathbb {M}}(\mathcal {F})$ generic over M.

• (ii) I has no winning strategy in $G(\mathcal {F})$.

Proof

(i) implies (ii): Suppose $\sigma$ is a winning strategy for I in $G(\mathcal {F})$ and let $\sigma , \mathcal {F} \in M$. Wlog we assume that $\sigma (\langle \rangle ) = \omega$. Thus Player II is allowed to play any $a_0$ as his first move and then $\sigma$ carries on as if $a_0$ had not been played. In particular this means that any initial play $a_0$ of II is a legal move, i.e. $\langle a_0 \rangle \in {\text {dom}}(\sigma )$. Consider the dense sets $D_n := \{ (s,F) : F \subseteq \bigcap \{ \sigma (\langle s_0,\dots ,s_{n-1} \rangle ) : \langle s_0,\dots ,s_{n-1} \rangle \in {\text {dom}}( \sigma ), \bigcup _{i< k} s_i = s\} \}$ for $n \in \omega$. $D_n \in M$ for every $n \in \omega$. By (i) there is $x \in \mathcal {F}$, ${\mathbb {M}}(\mathcal {F})$ generic over M. This means that for every $n \in \omega$ there is s an initial segement of x and $F \in \mathcal {F}$ so that $(s,F) \in D_n$ and $x {\setminus } s \subseteq F$. Now using this construct a sequence $\langle s_i \rangle _{i \in \omega }$ and $\langle F_i \rangle _{i \in \omega }$ recursively so that:

• (1) $\bigcup _{i < n} s_i$ is an initial segment of x for every $n \in \omega$,

• (2) $\max s_{i} < \min s_{i+1}$ for every $i \in \omega$,

• (3) $x {\setminus } \bigcup _{i < n} s_i \subseteq F_n$ for every $n \in \omega$,

• (4) $(\bigcup _{i < n} s_i, F_n) \in D_{n}$.

We find recursively that $\langle s_i \rangle _{i < n} \in {\text {dom}}(\sigma )$, i.e. $\langle s_i \rangle _{i < n}$ is a legal move. But $\bigcup _{i \in \omega } s_i = x \in \mathcal {F}$ contradicting $\sigma$ being a winning strategy for I.

(ii) implies (i): Let $M \ni \mathcal {F}$ be countable elementary and $\langle D_n \rangle _{n \in \omega }$ enumerate all dense subsets of ${\mathbb {M}}(\mathcal {F})$ in M. We describe a strategy for Player I: I starts by playing some $F_0$ so that there is $(t_0, F_0) \in D_0$. Then Player II will play $a_0 \subseteq F_0$, i.e. $(t_0 \cup a_0, F_0) \le (t_0,F_0)$. Now I plays $F_1$ so that there is $(t_0 \cup a_0 \cup t_1, F_1) \in D_1$, $(t_0 \cup a_0 \cup t_1, F_1)\le (t_0 \cup a_0, F_0)$...

By assumption there is a winning run $\langle a_i \rangle _{i \in \omega }$ for II according to this strategy. This means that $\bigcup a_i \in \mathcal {F}$ and moreover $x = \bigcup a_i \cup \bigcup t_i \in \mathcal {F}$ where $t_i$ are as described. But x is now ${\mathbb {M}}(\mathcal {F})$ generic over M. $\square$

For ultrafilters $\mathcal {U}$, I not having a winning strategy in $G(\mathcal {U})$ is equivalent to $\mathcal {U}$ being a P-point (see e.g. [19, VI.5.7]). For sake of completeness we prove a more general (in light of Lemma 4.1) version of this below. Recall that $\mathfrak {p}$ is the pseudointersection number, i.e. the least size of a set $\mathcal {B} \subseteq [\omega ]^\omega$ with the finite intersection property and no pseudointersection, a set $x \in [\omega ]^\omega$ such that $x \subseteq ^* y$ for all $y \in \mathcal {B}$. The bounding number $\mathfrak {b}$ is the least size of a family $\mathcal {B} \subseteq \omega ^\omega$ such that there is no $f \in \omega ^\omega$ eventually dominating every member of $\mathcal {B}$. It is well known that $\aleph _1 \le \mathfrak {p} \le \mathfrak {b}$. An ultrafilter $\mathcal {U}$ is called a $P_\kappa$ point if for any $\mathcal {B} \in [\mathcal {U}]^{<\kappa }$ there is a pseudointersection $x \in \mathcal {U}$ of $\mathcal {B}$. In particular a P-point is the same as a $P_{\aleph _1}$-point.

Lemma 4.2

Assume $\kappa \le \mathfrak {p}$, $\mathcal {U}$ is an ultrafilter and let $\theta \ge (2^{2^{\aleph _0}})^+$. Then TFAE:

• (i) $\mathcal {U}$ is a $P_{\kappa }$-point.

• (i) For every $M \preccurlyeq H(\theta )$ with $\vert M\vert < \kappa$ and $\mathcal {U} \in M$, there is $x \in \mathcal {U}$ which is ${\mathbb {M}}(\mathcal {U})$ generic over M.

Proof

(ii) implies (i) is trivial.

(i) implies (ii): Let $\vert M\vert < \kappa \le \mathfrak {p}$. Then as $\mathcal {U}$ is a P$_\kappa$-point, there is $U \in \mathcal {U}$ so that $U \subseteq ^* V$ for every $V \in M \cap \mathcal {U}$. Define for every $D \in M$, which is a dense open subset of ${\mathbb {M}}(\mathcal {U})$ and every $V \in M \cap \mathcal {U}$ a function $f_{D,V} :\omega \rightarrow \omega$ so that for $n \in \omega$:

$$\begin{aligned} \forall a\subseteq & {} n \exists b \subseteq [n,f_{D,V}(n)) \exists V' \in M \cap \mathcal {U} ((a \cup b, V')\\\le & {} (a,V) \wedge (a \cup b, V') \in D \wedge U {\setminus } f_{D,V}(n) \subseteq V'). \end{aligned}$$

The set of functions $f_{D,V}$ is smaller than $\kappa \le \mathfrak {p} \le \mathfrak {b}$. Thus there is one $f \in \omega ^\omega$ dominating all of them. Let $i_0 = 0$, $i_{n+1} = f(i_n)$. We write $I_n = [i_n,i_{n+1})$. As $\mathcal {U}$ is an ultrafilter, either $U_0 = \bigcup _{n \in \omega } I_{2n} \cap U$ or $U_1 = \bigcup _{n \in \omega } I_{2n +1} \cap U$ is in $\mathcal {U}$. Assume wlog that $U_0 \in \mathcal {U}$.

We define a $\sigma$-centered partial order ${\mathbb {P}}$ as follows. ${\mathbb {P}}$ consists of pairs (s, F) where

• (1) $s :n \rightarrow [\omega ]^{<\omega }$ for some $n \in \omega$,

• (2) $s(i) \subseteq I_i$ for every $i < n$,

• (3) $s(i) = U \cap I_i$ when i is even,

• (4) $F \in \mathcal {U} \cap M$.

A condition (t, F) extends (s, E) iff $t \supseteq s$, $F \subseteq E$ and $(t(i) \subseteq E)$ whenever $i \in {{\,\mathrm{dom}\,}}t {\setminus } {{\,\mathrm{dom}\,}}s$ is odd. For any $D \in M$ which is dense in ${\mathbb {M}}(\mathcal {U})$ we define a subset of ${\mathbb {P}}$, ${\tilde{D}}$ as follows:

$$\begin{aligned} {\tilde{D}} = \{ (t,F) : (\bigcup _{i \in {{\,\mathrm{dom}\,}}t} t(i), F)\in D \}. \end{aligned}$$

We claim that ${{\tilde{D}}}$ is dense in ${\mathbb {P}}$. Let $(s,E) \in {\mathbb {P}}$ be arbitrary. Then as $f_{D,E} <^* f$ there is $n \in \omega$ so that $[i_{2n+1},f_{D,E}(i_{2n+1})) \subseteq [i_{2n+1},i_{2n+2})$ and $2n+1 \ge {{\,\mathrm{dom}\,}}s$. Now extend s to $s_0$ so that ${{\,\mathrm{dom}\,}}s_0 = 2n+1$ and $s_0(i) = \emptyset$ for $i \in 2n+1 {\setminus } {{\,\mathrm{dom}\,}}s$ odd and $s_0(i) = U \cap I_i$ for i even. By definition of $f_{D,E}$ there is $b \subseteq I_{2n+1}$ so that $\exists F \subseteq E$ with $(a \cup b, F) \in D$ where $a = \bigcup _{i<2n+1} s_0(i)$, $(a \cup b, F) \le (a,E)$ and $U {\setminus } i_{2n+2} \subseteq F$. Let $t = s_0 \cup \{(2n+1,b) \}$. Then $(t,F) \le (s,E)$ in ${\mathbb {P}}$ and $(t,F) \in {\tilde{D}}$.

Now as $\kappa \le \mathfrak {p}$ and by Bell’s theorem (see [2]) there is a ${\mathbb {P}}$ generic real $g :\omega \rightarrow [\omega ]^{<\omega }$ over M. But then $x := \bigcup _{i \in \omega } g(i) \in \mathcal {U}$ as $U_0 \subseteq x$ and x is ${\mathbb {M}}(\mathcal {U})$ generic over M. $\square$

Corollary 4.3

Suppose $\mathcal {U}$ is a P-point, $M \preccurlyeq H(\theta )$ countable and $\mathcal {U} \in M$. Then there is $x \in \mathcal {U}$, ${\mathbb {M}}(\mathcal {U})$ generic over M.

Lemma 4.4

(see [12, Chapter 24]) Assume $\mathcal {U} \in M$ is a Ramsey ultrafilter and x is ${\mathbb {M}}(\mathcal {U})$ generic over M. Then every $y \subseteq ^* x$ is ${\mathbb {M}}(\mathcal {U})$ generic over M.

Proof of Theorem 1.3

Suppose $\mathcal {U}$ is a Ramsey ultrafilter with a coanalytic base $X \subseteq [\omega ]^\omega$. As X is coanalytic, there is a continuous function $f : 2^\omega \rightarrow 2^\omega$ so that

$$\begin{aligned} x \in X \leftrightarrow f(x) \in {{\,\mathrm{WO}\,}}. \end{aligned}$$

Let $M \preccurlyeq H(\theta )$ be countable where $\theta \ge (2^{2^{\aleph _0}})^+$ is and $\mathcal {U}, f \in M$. As $\mathcal {U}$ is a P-point and by Corollary 4.3, there is $x \in \mathcal {U}$ that is ${\mathbb {M}}(\mathcal {U})$ generic over M. Moreover as $\mathcal {U}$ is Ramsey and by Lemma 4.4, any $y \subseteq ^* x$ is also generic over M. Let N be the transitive collapse of M, $\alpha := \omega _1^N = M \cap \omega _1$ and let $y \in X$ be arbitrary such that $y \subseteq ^* x$. Let $\beta = \Vert f(y)\Vert$, then $\beta \in N[y]$ and thus $\beta < \alpha = \omega _1^{N[y]}$. As y was arbitrary, we have shown that the set $X'= \{ y : f(y) \in WO \wedge \Vert f(y)\Vert \le \alpha \} \subseteq X$ contains $\{ y \subseteq ^* x : y \in X \}$. This means that $X'$ also generates $\mathcal {U}$. But $X'$ is Borel and cannot generate an ultrafilter. $\square$

5 ${\varvec{\Delta }}^1_2$ versus ${\varvec{\Pi }}^1_1$

Using a result of Shelah we can show the following.

Theorem 5.1

It is consistent that every P-point is ${\varvec{\Delta }}^1_2$ and has no ${\varvec{\Pi }}^1_1$ base.

Proof

This follows immediately by [19, Theorem XVIII.4.1] and the subsequent remark, which states that starting from L we can choose any Ramsey ultrafilter $\mathcal {U}$ and pass to an extension in which $\mathcal {U}$ generates the unique P-point up to permutation of $\omega$. Moreover this ultrafilter will stay Ramsey.

Thus let $\mathcal {U}$ be any (definition of a) $\Delta ^1_2$ Ramsey ultrafilter in L. Now apply Shelah’s theorem to this ultrafilter and pass to an extension V of L in which $\mathcal {U}^L$ generates the unique P-point and is Ramsey. In V, $\mathcal {U}^V$ will still have the finite intersection property and $\mathcal {U}^L \subseteq \mathcal {U}^V$ by Shoenfield’s absolutness theorem. Thus in V, $\mathcal {U}^V$ generates the same ultrafilter as $\mathcal {U}^L$. As $\mathcal {U}^V$ is $\Delta ^1_2$, the ultrafilter it generates will be $\Delta ^1_2$ as well. We know that in V, there is for every P-point $\mathcal {V}$ a permutation f of $\omega$ so that $V \in \mathcal {V} \leftrightarrow f(V) \in \mathcal {U}$. In particular $\mathcal {V}$ has a $\Delta ^1_2(f)$ definition. On the other hand, every P-point is a Ramsey ultrafilter so none of them can have a ${\varvec{\Pi }}^1_1$ base by Theorem 1.3. $\square$

Proof of Theorem 1.4

To simplify notation we assume that $r=0$. Let $\mathcal {U}$ be a $\Delta ^1_{n+1}$ ultrafilter. Let us introduce the following notation. For $y \in [\omega \times \omega ]^\omega$, we let $y_n$ be y’s n’th vertical section. We let $z(y) = \{ n \in \omega : y_n \ne \emptyset \}$. When z(y) is infinite then we denote with $y^n$, the n’th nonempty vertical section of y.

The Fubini product of $\mathcal {U}$, $\mathcal {U} \otimes \mathcal {U}$, consists of all $y \in [\omega \times \omega ]^\omega$ so that

$$\begin{aligned} \{n \in \omega : y_n \in \mathcal {U} \} \in \mathcal {U} . \end{aligned}$$

$\mathcal {U} \otimes \mathcal {U}$ is again an ultrafilter. We will show that it has a $\Pi ^1_n$ base. Let $\varphi (x,w)$ be $\Pi ^1_1$ so that

$$\begin{aligned} x \in \mathcal {U} \leftrightarrow \exists w \in 2^\omega (\varphi (x,w)). \end{aligned}$$

Let $r : \omega \times 2^\omega \rightarrow 2^\omega$ be a recursive function such that for any sequence $\langle w_n \rangle _{ n \in \omega }$ there is $w \in 2^\omega$, which is not eventually constant, so that $r(n,w) = w_n$ for every $n \in \omega$.

Let $O :[\omega \times \omega ]^\omega \rightarrow 2^\omega$ be the function defined by

$$\begin{aligned} O(y)(n) = {\left\{ \begin{array}{ll} 0\quad \text { if } \vert z(y) \vert< \omega \\ 0\quad \text { if } \min y^n \ge \min y^{n+1}\\ 1\quad \text { if } \min y^n < \min y^{n+1}. \end{array}\right. } \end{aligned}$$

O is obviously lightface Borel. Let us define $X \subseteq [\omega \times \omega ]^\omega$ as follows:

$$\begin{aligned}&y \in X \leftrightarrow \vert z(y) \vert = \omega \wedge \varphi (z(y),r(0,O(y))) \\&\quad \wedge \forall n \in \omega \exists s \in [\omega ]^{<\omega } [\varphi (s \cup y^n,r(n+1,O(y)))]. \end{aligned}$$

X is obviously $\Pi ^1_n$. Moreover $X \subseteq \mathcal {U} \otimes \mathcal {U}$. To see this let us decode what $y \in X$ means. The first clause in the definition of X says that y has infinitely many nonempty vertical sections. The next clause ensures that $z(y) \in \mathcal {U}$ as witnessed by r(0, O(y)), the 0’th real coded by O(y). The last clause ensures that for every nonempty vertical section $y^n$ of y, $s \cup y^n$ is in $\mathcal {U}$ for some finite s as witnessed by $r(n+1,O(y))$, the $n+1$’th real coded by O(y). In particular $y^n \in \mathcal {U}$. Thus we indeed have that $y \in X \rightarrow y \in \mathcal {U} \otimes \mathcal {U}$.

Moreover we have that X is a base for $\mathcal {U} \otimes \mathcal {U}$. To see this fix $u \in \mathcal {U} \otimes \mathcal {U}$ and we show that there is $y \in X$ so that $y \subseteq u$. First let $y_0 = \bigcup \{ \{n \} \times u_n : n \in \omega , u_n \in \mathcal {U} \}$, i.e. we remove from u the vertical sections that are not in $\mathcal {U}$. Then we let $w_0$ be such that $\varphi (z(y_0), w_0)$ holds true. Further we let $w_{n+1}$ be such that $\varphi (y_0^n, w_{n+1})$ holds true. Let $w \in 2^\omega$ be a single real coding the sequence $\langle w_n\rangle _{n \in \omega }$ via r, i.e. $r(n,w) = w_n$ for every $n \in \omega$. Find a sequence $\langle m_n \rangle _{n \in \omega }$ so that $m_n \in y_0^n$ for every n and $w(n) = 1$ iff $m_{n+1} > m_n$. Such a sequence can be constructed recursively. Whenever $w(n) = 1$ we can simply find $m_{n+1} \in y_0^{n+1}$ large enough such that $m_{n+1} > m_n$ and if additionally $w(n+1), \dots , w(n+k)$ is a maximal block of 0s in w then we let $m_{n+1} = \dots = m_{n+k+1} \in y^{n+1} \cap \dots \cap y^{n+k+1}$. Finally given the sequence $\langle m_n \rangle _{n\in \omega }$ let $y = \bigcup \{\{z(y_0)(n)\} \times (y_0^n {\setminus } m_n) : n \in \omega \}$, where $z(y_0)(n)$ is the n’th element of $z(y_0)$. We see that $y \subseteq y_0 \subseteq u$, that $z(y) = z(y_0)$, that $y^n =^* y_0^n$ for every n and that $O(y) = w$. In particular $y \in X$ by definition of X. $\square$

Remark 5.2

Let $\mathcal {U}$ be an ultrafilter. Then $\mathcal {U} \otimes \mathcal {U}$ is neither a P- nor a Q-point.

Proof

To see that $\mathcal {U} \otimes \mathcal {U}$ is not a P-point, consider its elements of the form $[n,\omega ) \times \omega$ for $n \in \omega$. Whenever y is a pseudointersection of $\{[n,\omega ) \times \omega : n \in \omega \}$, then $y_n$, the n’th vertical section of y, is finite for every $n \in \omega$. Thus y is not a member of $\mathcal {U} \otimes \mathcal {U}$.

For Q-points, consider the partition of $\omega \times \omega$ consisting of sets of the form $a_n := \{n\} \times n$ or $b_n := (n+1) \times \{n\}$, for $n \in \omega$. Assume $y \in \mathcal {U} \otimes \mathcal {U}$ is such that $\vert y \cap a_n \vert , \vert y\cap b_n \vert \le 1$ for every $n\in \omega$. Then there are $m < n$ so that $y_n, y_m \in \mathcal {U}$. In particular, $y_n \cap y_m$ is infinite and we find $i \in (y_n \cap y_m) {\setminus } n$. But then, as $i > n,m$, we have that $(m,i), (n,i) \in y \cap b_i$ and $(n,i) \ne (m,i)$ – a contradiction to $\vert y \cap b_i \vert \le 1$. $\square$

6 Adding reals

The purpose of the following section is to study the indestructibility of definitions for ultrafilters via forcings that add splitting reals, and as a consequence destroy all ultrafilters from a ground model (in the sense that they do not generate an ultrafilter in the extension). We will show that classical forcing notions adding splitting reals, namely Cohen, Random and Silver forcing, fail in preserving definitions for ultrafilters.

Let $A \subseteq V$. A set $X \in V$ is called ${{\,\mathrm{OD}\,}}(A)$ if it is definable over V from ordinals and elements of A as parameters. Recall that a poset ${\mathbb {P}}$ is weakly homogeneous if for any $p,q \in {\mathbb {P}}$, there is an automorphism $\pi :{\mathbb {P}} \rightarrow {\mathbb {P}}$ so that $\pi (p)$ is compatible to q. In this section we will denote with $\mathcal {P}_A$ the collection of weakly homogeneous ${{\,\mathrm{OD}\,}}(A)$ posets.

Lemma 6.1

Let c be a Cohen real over V, ${\mathbb {P}}\in (\mathcal {P}_V)^{V[c]}$ and G a ${\mathbb {P}}$-generic filter over V[c]. Then in V[c][G], c is splitting over any set of reals with the finite intersection property that is ${{\,\mathrm{OD}\,}}(V)$.

Proof

Let $X \in V[c][G]$ be an ${{\,\mathrm{OD}\,}}(V)$ set of reals with the finite intersection property, say $V[c][G] \models \text {``}\dot{X} = \{ x \in [\omega ]^\omega : \varphi (x,a,\bar{\alpha }) \}\text {''}$ where $a \in V$ and $\bar{\alpha }$ is a finite sequence of ordinals. Wlog we may assume that X is a filter, since the filter generated by X is also ${{\,\mathrm{OD}\,}}(V)$. Suppose c does not split X. This means exactly that $c \in X$ or $\omega {\setminus } c \in X$. Thus there is $s \subseteq c$, deciding the formula and parameters defining ${\mathbb {P}}$, and $\dot{p}$ with $\dot{p} [c] \in G$, $(s,\dot{p}) \Vdash \text {``}\varphi \text { defines a filter''}$ so that either

$$\begin{aligned} (s,\dot{p}) \Vdash \dot{c} \in \dot{X} \end{aligned}$$

or

$$\begin{aligned} (s,\dot{p}) \Vdash \omega {\setminus } \dot{c} \in \dot{X}. \end{aligned}$$

But now notice that $c' = s \cup \{ (n,1 - m) : (n,m) \in c, n \ge \vert s \vert \}$ is also Cohen over V with $s \subseteq c'$ (we identify c as a subset of $\omega$ with its characteristic function). Moreover $V[c] = V[c']$ and thus $\dot{{\mathbb {P}}}[c] = \dot{{\mathbb {P}}}[c']$. Let $p_0 := \dot{p}[c]$ and $p_1 :=\dot{p}[c']$. Working in V[c] we find that $p_0,p_1 \in {\mathbb {P}}$, so there is an automorphism $\pi$ of ${\mathbb {P}}$ so that $\pi (p_1)$ is compatible to $p_0$. Let H be ${\mathbb {P}}$-generic over V[c] containing $p_0$ and $\pi (p_1)$. In either of the above cases, $V[c][H]\models \varphi (c,a,\bar{\alpha })\wedge \varphi (c',a,\bar{\alpha })$. This is a contradiction to $(s,\dot{p}) \Vdash \text {``}\varphi \text { defines a filter''}$. $\square$

Lemma 6.2

Let r be a random real over V, ${\mathbb {P}}\in (\mathcal {P}_V)^{V[r]}$ and G a ${\mathbb {P}}$-generic filter over V[r]. Then in V[r][G], r is splitting over any set of reals with the finite intersection property that is ${{\,\mathrm{OD}\,}}(V)$.

Proof

Let us assume that ${\mathbb {P}}$ is simply the trivial forcing, since this part of the argument is essentially the same as in the last proof. As before we fix $X \in V[r]$ an ${{\,\mathrm{OD}\,}}(V)$ set with the finite intersection property and we assume that it is already a filter.

First note that any finite modification of r is still a random real. Moreover, as complementation is a measure preserving homeomorphism of $2^\omega$, the complement of a random real is still random. Thus any $r' =^* \omega {\setminus } r$ is still random.

Now similarly as in the proof for Cohen forcing we find that there is Borel set B of positive measure coded in V so that $r \in B$ and

$$\begin{aligned} B \Vdash \dot{r} \in X \end{aligned}$$

or

$$\begin{aligned} B \Vdash \omega {\setminus } \dot{r} \in X. \end{aligned}$$

Recall that for any Borel set A of positive measure, its $E_0$ closure ${{\tilde{A}}} = \{ x \in 2^\omega : \exists y \in A ( x =^* y) \}$ has full measure. To see this Let $\varepsilon >0$ be arbitrarily small. Apply Lebesgue’s density theorem to find a basic open set $[s] \subseteq 2^\omega$ so that $\frac{\mu (A \cap [s])}{\mu ([s])} > 1-\varepsilon$. Follow from this that $\mu ({{\tilde{A}}}) > 1- \varepsilon$.

Now let $C := \{ \omega {\setminus } x : x \in {{\tilde{B}}} \}$. C is coded in V and has full measure. Thus we have that $r \in B \cap C$. By definition of C, there is $r' \in B$ so that $r' =^* \omega {\setminus } r$. Moreover $r'$ is also a random real over V by our first remark. $r,r' \in X$ and $\omega {\setminus } r, \omega {\setminus } r' \in X$ are both contradictions to X having the finite intersection property. $\square$

Recall that Silver forcing consists of partial functions $p :\omega \rightarrow 2$ so that $\omega {\setminus } {{\,\mathrm{dom}\,}}(p)$ is infinite.

Lemma 6.3

Let s be a Silver real over V, ${\mathbb {P}}\in (\mathcal {P}_V)^{V[s]}$ and G a ${\mathbb {P}}$-generic filter over V[s]. Then, in V[s], there is a real splitting over any set of reals that is ${{\,\mathrm{OD}\,}}(V)$ in V[s][G].

Proof

Again we only consider the case when ${\mathbb {P}}$ is trivial. Let $X \in V[s]$ be an ${{\,\mathrm{OD}\,}}(V)$ filter. Let $S_s = \{n \in \omega : \vert \{ m < n : s(m) = 1 \} \vert \text { is even} \}$. As before assume $p \subseteq s$ is such that either

$$\begin{aligned} p \Vdash S_{\dot{s}} \in X \end{aligned}$$

or

$$\begin{aligned} p \Vdash \omega {\setminus } S_{\dot{s}} \in X. \end{aligned}$$

Let $n = \min (\omega {\setminus } {{\,\mathrm{dom}\,}}(p))$ and note that $s'$ defined by $s'(i) = s(i)$ for all $i \ne n$ and $s'(n) = 1- s(n)$ is also Silver and $p \subseteq s'$. But $S_{s'} =^* \omega {\setminus } S_{s}$. We get the same contradiction as in the last two proofs. $\square$

Corollary 6.4

Let $r \in 2^\omega$ and assume that there is a Cohen, a random or a Silver real over L[r]. Then there is no $\Delta ^1_2(r)$ ultrafilter.

In particular, the existence of a $\Delta ^1_2(r)$ ultrafilter implies that $\omega _1 = \omega _1^{L[r]}$.

Proof

Suppose that $\varphi$ is a $\Sigma ^1_2(r)$ definition for an ultrafilter and that c is a Cohen, random or Silver real over L[r]. In L[r][c], the set defined by $\varphi$ will have the finite intersection property by downwards absoluteness. Thus by Theorems 6.1, 6.2 or 6.3 respectively, $L[r][c] \models \exists x \in [\omega ]^\omega \forall y \in [\omega ]^\omega (\lnot \varphi (y) \vee (\vert x \cap y \vert = \omega \wedge \vert x \cap \omega {\setminus } y \vert = \omega ))$. This is a $\Sigma ^1_3(x,c)$ statement, so by upwards Shoenfield absoluteness it holds true in $V \supseteq L[x][c]$. Thus $\varphi$ cannot define an ultrafilter in V.

The second part follows, since whenever $\omega _1^{L[r]} < \omega _1$, there is a Cohen real in V over L[r]. $\square$

Another way of seeing the above for Cohen or random forcing is to use the classical result of Judah and Shelah (see [13]), saying that the existence of a Cohen or random real over L[r] is equivalent to every $\Delta ^1_2(r)$ set having the Baire property or being Lebesgue measurable respectively.

Theorem 6.5

There is no $OD({\mathbb {R}})$ ultrafilter, in particular no projective one, after adding $\omega _1$ many Cohen reals in a finite support iteration, random reals using a product of Lebesgue measure or Silver reals in a countable support iteration.

Proof

Let $\langle c_\alpha : \alpha < \omega _1 \rangle$ be Cohen reals added via a finite support iteration over a ground model V and suppose that in $V[\langle c_\alpha : \alpha < \omega _1 \rangle ]$ there is an ultrafilter $\mathcal {U}$ definable from a real a and ordinals. It is well known that there is $\xi < \omega _1$ so that $a \in V[\langle c_\alpha : \alpha \in \omega _1 {\setminus } \{\xi \} \rangle ]$. But then, by Lemma 6.1, $c_\xi$ is splitting over $\mathcal {U}$, since $V[\langle c_\alpha : \alpha < \omega _1 \rangle ] = V[\langle c_\alpha : \alpha \in \omega _1 {\setminus } \{\xi \} \rangle ][c_\xi ]$.

The argument for random reals is essentially the same.

Let $\langle {\mathbb {P}}_\alpha ,\dot{ {\mathbb {Q}}}_\alpha : \alpha \le \omega _1 \rangle$ be the $\omega _1$-length countable support iteration of Silver forcing. Any real a appears in $V^{{\mathbb {P}}_\xi }$ for some $\xi < \omega _1$. But now note that ${\mathbb {P}}_{\omega _1}$ is ${{\,\mathrm{OD}\,}}(V)$ and weakly homogeneous. Moreover, ${\mathbb {P}}_{\omega _1} \cong {\mathbb {P}}_{\xi } * \dot{{\mathbb {P}}}_{\omega _1}$. Thus applying Lemma 6.3, we find that there is no ultrafilter definable from parameters in $V^{{\mathbb {P}}_\xi }$ over $V^{{\mathbb {P}}_{\omega _1}}$. In particular there is no ${{\,\mathrm{OD}\,}}(\{a\})$ ultrafilter in $V^{{\mathbb {P}}_{\omega _1}}$. $\square$

7 The Borel ultrafilter number

The ultrafilter number $\mathfrak {u}$ is the least size of a base for an ultrafilter. As with mad families (see [16]) and maximal independent families (see [3]) it makes sense to introduce a Borel version of the ultrafilter number that is closely related to the definability of ultrafilters.

Definition 7.1

The Borel ultrafilter number is defined as

$$\begin{aligned} \mathfrak {u}_B := \min \{ \vert \mathcal {B} \vert : \mathcal {B} \subseteq {\varvec{\Delta }}^1_1, \bigcup \mathcal {B} \text { is an ultrafilter} \}. \end{aligned}$$

Note that $\aleph _1 \le \mathfrak {u}_B$, as a countable union of Borel sets is Borel.

Remark 7.1

Let $\mathfrak {u}'_B = \min \{ \vert \mathcal {B} \vert : \mathcal {B} \subseteq {\varvec{\Delta }}^1_1, \bigcup \mathcal {B} \text { is an ultrafilter base} \}$ and $\mathfrak {u}''_B = \min \{ \vert \mathcal {B} \vert : \mathcal {B} \subseteq {\varvec{\Delta }}^1_1, \bigcup \mathcal {B} \text { generates an ultrafilter} \}$. Then $\mathfrak {u}''_B =\mathfrak {u}'_B = \mathfrak {u}_B$.

Proof

Obviously, $\mathfrak {u}''_B \le \mathfrak {u}'_B \le \mathfrak {u}_{B}$. Remember that whenever B is Borel, then the filter $F_B$ that it generates is analytic. Thus $\mathfrak {u}''_B$ is uncountable as well. Now let $\mathcal {B}$ be a collection of Borel sets, whose union generates an ultrafilter. We may assume that $\mathcal {B}$ is closed under finite unions. For every $B \in \mathcal {B}$, let $F_B$ be the filter generated by B. Since $F_B$ is analytic, we can write it as an $\omega _1$-union $F_B = \bigcup _{\alpha < \omega _1} F_B^\alpha$ of Borel sets. Now consider $\{ F_B^\alpha : B \in \mathcal {B}, \alpha < \omega _1 \}$. It has the same size as $\mathcal {B}$ and is a witness for $\mathfrak {u}_B$. $\square$

Any coanalytic set is an $\omega _1$-union of Borel sets. Thus the existence of a coanalytic ultrafilter base implies that $\mathfrak {u}_B = \aleph _1$.

Theorem 7.2

${{\,\mathrm{cov}\,}}(\mathcal {M}),{{\,\mathrm{cov}\,}}(\mathcal {N}), \mathfrak {b}\le \mathfrak {u}_B \le \mathfrak {u}$.

Proof

Let $\mathcal {B}$ be a collection of $< {{\,\mathrm{cov}\,}}(\mathcal {M})$ many Borel sets and assume that $\bigcup \mathcal {B}$ has the finite intersection property. Let $M \preccurlyeq H(\theta )$ for some large $\theta$, so that $\vert M \vert < {{\,\mathrm{cov}\,}}(\mathcal {M})$ and $\mathcal {B} \subseteq M$. Then there is a Cohen real c over M. But then in M[c], c is splitting over every $B \in \mathcal {B}$. Moreover in V it is true that c is splitting over B, by $\Sigma _1$-upwards-absoluteness. Thus c is splitting over $\bigcup \mathcal {B}$ which cannot be an ultrafilter. The argument for random forcing is exactly the same.

For $\mathfrak {b} \le \mathfrak {u}_B$, note that any Borel filter is meager. By a classical result of Talagrand (see [20]), meager filters $\mathcal {F}$ are exactly those for which there is $f \in \omega ^\omega$ so that $\forall x \in \mathcal {F} \forall ^\infty n \in \omega (x \cap [n,f(n)) \ne \emptyset )$. For $\mathcal {B}$ a collection of Borel filters, we let $f_B$ be such a function for every $B \in \mathcal {B}$. If $\mathcal {B}$ has size smaller than $\mathfrak {b}$, then there is a single function $f \in \omega ^\omega$ so that $f_B <^* f$ for each $B \in \mathcal {B}$. Now note that $x_0 \cup x_1 = \omega$, where $x_0 := \bigcup _{n \in \omega } [f^{2n}(0),f^{2n+1}(0))$ and $x_1 := \bigcup _{n \in \omega } [f^{2n+1}(0),f^{2n+2}(0))$. But neither $x_0$ nor $x_1$ can be in $\bigcup \mathcal {B}$. $\square$

The following questions are answered positively in [17].

Question 7.1

Is it consistent that $\mathfrak {u}_B < \mathfrak {u}$? Is it consistent that there is a $\Pi ^1_1$ ultrafilter base while $\aleph _1 < \mathfrak {u}$?