Let $S$ is a partition of a set $U$. Let $c$ is an ultrafilter on $U$.
Prove or disprove this conjecture:
At least one of the following is true:
- $\exists D\in S, C\in c:C\subseteq D$ or
- $\exists C\in c\forall D\in S: \mathrm{card}(C\cap D)\le 1$.
MathOverflow is a question and answer site for professional mathematicians. It only takes a minute to sign up.
Sign up to join this communityLet $S$ is a partition of a set $U$. Let $c$ is an ultrafilter on $U$.
Prove or disprove this conjecture:
At least one of the following is true:
Take a partition of ${\mathbb N}^2$ into vertical lines $\{x\}\times {\mathbb N}$. In each vertical line take a non-principle ultrafilter $\omega_x$. Now take the set of all sets $Y$ that intersect all but finitely many vertical lines by a subset from $\omega_x$. Note that all complements of finite sets of ${\mathbb N}^2$ are in our set of sets, and that it is clearly a filter. Take any ultrafilter $\omega$ that contains that filter. It exists by the Zorn lemma. Clearly, the first option does not hold: none of the vertical lines is in $\omega$. Now suppose that for some $C\in\omega$, $C$ intersects each vertical line by at most 1 element. Then its complement intersects each vertical line by a subset that is either the whole line or the line without one element. That is impossible because we chose non-principle $\omega_x$. Thus $\omega$ is a counterexample.
Non-principal ultrafilters with the property in the question for all partitions are called "selective" or "Ramsey" ultrafilters. The "Ramsey" terminology comes from the following connection, due to Kunen, with Ramsey's theorem: Suppose $c$ is a selective ultrafilter on $U$, and the collection $[U]^n$ of $n$-element subsets of $U$ is partitioned into finitely many pieces; then there is a set $H\in c$ such that $[H]^n$ is included in one of the pieces.
The earlier answers show that not all non-principal ultrafilters on a countable set are selective. Whether any of them are is independent of ZFC. The continuum hypothesis (or any of various weaker conditions on cardinal characteristics of the continuum) implies that selective ultrafilters exist, but Kunen showed that there are no selective ultrafilters on $\omega$ in the random real model.
Selective ultrafilters on uncountable sets are much harder to get (unless you cheat by using an ultrafilter that concentrates on a countable subset). If $c$ is a selective ultrafilter, if $\kappa$ is the smallest cardinality of any set in $c$, and if $\kappa$ is uncountable, then $\kappa$ is necessarily a measurable cardinal (hence extremely large by ordinary mathematical standards).
The statement is false. Let $S=\bigcup S_n$ be a partition of an infinite set $S$ into infinite sets $S_n$, and let $\mu_n$ be a nonprincipal ultrafilter on $S_n$, and let $\mu$ be any nonprincipal ultrafilter on $\mathbb{N}$. Let $\nu=\int\mu_n d\mu$, which means $X\in\nu\iff \{n\mid X\cap S_n\in \mu_n\}\in\mu$. That is, a set $X$ is large with respect to $\nu$ if it is $\mu_n$-large for $\mu$-large many $n$. This is easily seen to be an ultrafilter on $S$. Since $\mu$ is nonprincipal, it follows that no single $S_n$ is in $\nu$. But also any set $C$ that meets each $S_n$ in a finite set is not $\mu_n$-large for any $n$, and hence is not $\nu$-large. Thus, neither condition holds and this makes a counterexample.
This is false. Let $U=\mathbb N\times\mathbb N$ and let $S$ consist of all columns. Let $c$ be a product ultrafilter, i.e. a set is large if most of its intersections with columns are large. Then no element of $S$ is large, but each large set intersects some column in at least 2.