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}$.

  • $\begingroup$ 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^+$? $\endgroup$ – Umberto Cavasinni Sep 18 '16 at 3:55
  • $\begingroup$ I think you can do the changes without problem, and use transfinite induction to construct the sets $U$ and $V$. $\endgroup$ – 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 ... ?

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.