An ultrafilter and a partition - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-19T02:39:38Z http://mathoverflow.net/feeds/question/44051 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/44051/an-ultrafilter-and-a-partition An ultrafilter and a partition porton 2010-10-29T03:41:41Z 2010-10-29T22:41:12Z <p>Let $S$ is a partition of a set $U$. Let $c$ is an ultrafilter on $U$.</p> <p>Prove or disprove this conjecture:</p> <p>At least one of the following is true:</p> <ul> <li>$\exists D\in S, C\in c:C\subseteq D$ or</li> <li>$\exists C\in c\forall D\in S: \mathrm{card}(C\cap D)\le 1$.</li> </ul> http://mathoverflow.net/questions/44051/an-ultrafilter-and-a-partition/44054#44054 Answer by Bjørn Kjos-Hanssen for An ultrafilter and a partition Bjørn Kjos-Hanssen 2010-10-29T04:00:11Z 2010-10-29T04:29:57Z <p>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.</p> http://mathoverflow.net/questions/44051/an-ultrafilter-and-a-partition/44055#44055 Answer by Mark Sapir for An ultrafilter and a partition Mark Sapir 2010-10-29T04:05:49Z 2010-10-29T22:41:12Z <p>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. </p> http://mathoverflow.net/questions/44051/an-ultrafilter-and-a-partition/44056#44056 Answer by Joel David Hamkins for An ultrafilter and a partition Joel David Hamkins 2010-10-29T04:25:49Z 2010-10-29T04:25:49Z <p>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.</p> http://mathoverflow.net/questions/44051/an-ultrafilter-and-a-partition/44067#44067 Answer by Andreas Blass for An ultrafilter and a partition Andreas Blass 2010-10-29T06:02:05Z 2010-10-29T06:02:05Z <p>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. </p> <p>The earlier answers show that not <em>all</em> non-principal ultrafilters on a countable set are selective. Whether <em>any</em> 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. </p> <p>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).</p>