Why the character of a non-principal ultrafilter (on an infinite set) is at least $\aleph_1$?

Preliminary definition: let $\mathcal{U}$ be an ultrafilter; then its character, or $\chi(\mathcal{U})$, is the least size of a family $\mathcal{E} \subset \mathcal{U}$ that generates $\mathcal{U}$ (i.e. every element in $\mathcal{U}$ is an extension of a finite intersection of elements of $\mathcal{E}$).

I don't know how to prove the following: if $\mathcal{U}$ is a non-principal ultrafilter on an infinite set $A$, then $\chi(\mathcal{U})$ is at least $\aleph_1$.

I prefer a hint before a complete solution, thanks.

If $A$ is uncountable, then notice that $\mathcal{U}$ have to contain the Fréchet filter in $A$. So, it is impossible that $\chi(\mathcal{U})=\aleph_0$ in this case.

Suppose that $A$ is a countable set and $\mathcal{U}$ is a non-principal ultrafilter on $A$ such that $\chi(\mathcal{U})=\aleph_0$. Then, there is a family of sets $\mathcal{E}=\{X_i:i\in \mathbb{N}\}$ such that every element $X\in\mathcal{U}$ contains a finite intersection of elements in $\mathcal{E}$.

Let $A=\{a_n:1\leq n<\omega\}$ be an enumeration of $A$, and let $\mathcal{I}=\{Y_n:1\leq n<\omega\}$ be an enumeration of all finite intersections of elements in $\mathcal{E}$. (Notice that there are countably many of them, since each intersection is codified by a finite increasing sequence of natural numbers).

Notice also that every element in $Y_j$ is infinite: otherwise, $\mathcal{U}$ would contain a finite set, and so it would be principal.

Proposition: There are sets $U,V\subseteq A$ such that $U\cup V=A$, $U\cap V=\emptyset$ and neither $U$ nor $V$ contain any $Y_j$.

@Umberto Hint: construct the sets $U,V$ inductively using the given enumerations.

Proof of the Proposition: Start with the sets $U_0=\emptyset,V_0=\emptyset$.

Given $a_1$, Put $U_1'=\{a_1\}$. On the other hand, notice that $Y_1$ is infinite, so there are different elements elements $a_{i_1},a_{j_1}\neq a_1$ such that $a_{i_1},a_{j_1}\in Y_1$.

Put $U_1=\{a_1,a_{i_1}\}$ and $V_1=\{a_{j_1}\}$.

Suppose we have constructed $U_n,V_n$. Consider now the elements $a_{n+1}$:

• If $a_{n+1}\not\in U_n\cup V_n$, put $U_{n+1}'=U_n\cup \{a_{n+1}\}$. Otherwise, put $U_{n+1}'=U_n$.

Now, since $Y_n$ is infinite, there are different elements $a_{i_n},a_{j_n}$ that are not in the finite set $U_n'\cup V_n$, so put $U_n=U_{n+1}'\cup \{a_{i_n}\}$ and $V_n=V_n' \cup \{a_{j_n}\}$.

Finally, take $\displaystyle{U=\bigcup_{n\in\mathbb{N}} U_n}$ and $\displaystyle{V=\bigcup_{n\in\mathbb{N}} V_n}$. Then we have:

1. $U\cup V=A$: Notice that for every $n\geq 1$ we had either $a_n\in U_n$ or $a_n\in V_n$.
2. $U\cap V=\emptyset$: If $a\in U\cap V$, there would be $m<n$ such that $a\in U_n\cap V_m$, and so in particular $a\in U_n\cap V_n$. It can be easily shown by induction that $U_n\cap V_n=\emptyset$ for all $n$, so this never happens.
3. Suppose $Y_n\in \mathcal{E}$. Then, by construction, $a_{j_n}\in Y_n\cap V_n$ and since $V_n$ is disjoint from $U$, we have $Y_n\not\subseteq U$. Also, $a_{i_n}\in Y_n\cap U_n$, so $Y_n\not\subseteq V$. $\Box$

However, since $\mathcal{U}$ was an ultrafilter on $A$, either $U\in \mathcal{U}$ or $V\in \mathcal{U}$. So we have constructed an element in the ultrafilter which does not contain any finite intersection of elements in $\mathcal{E}$.

• Thank you very much. I cannot see anything special in $\omega$ in this argument: is it reusable, mutatis mutandis, with any uncountable cardinal? In other words: is it provable that the character of a non-principal ultrafilter on a set of cardinality $\kappa$ is at least $\kappa^+$? – Umberto Cavasinni Sep 18 '16 at 3:55
• I think you can do the changes without problem, and use transfinite induction to construct the sets $U$ and $V$. – Darío G Sep 19 '16 at 12:22

HINT: Suppose that $\mathscr{U}$ is a free ultrafilter on $A$, and let $\mathscr{V}=\{V_n:n\in\omega\}\subseteq\mathscr{U}$. Suppose that $\mathscr{V}$ generates $\mathscr{U}$. Without loss of generality we may assume that $V_{n+1}\subseteq V_n$ and $|V_{n}\setminus V_{n+1}|\ge 2$ for each $n\in\omega$. (Why?) Recursively choose distinct $a_n\in A$ for $n\in\omega$ in such a way that $a_{2n},a_{2n+1}\in V_n\setminus V_{n+1}$. Let $S=\{a_{2n}:n\in\omega\}$. One of $S$ and $A\setminus S$ must belong to $\mathscr{U}$, but ... ?

• If $V_{n+1} \subseteq V_n$, then $V_{n+1} \setminus V_n = \emptyset$. Is it only a typo? – Umberto Cavasinni Sep 18 '16 at 4:03
• @Umberto: Yes, it was a typo: the subscripts were the wrong way round. Thanks for catching it. – Brian M. Scott Sep 18 '16 at 4:06