Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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$.
share|improve this question

4 Answers 4

up vote 4 down vote accepted

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.

share|improve this answer
    
I don't understand the phrase "intersect ... by a subset". If by a subset it is meant a member of $\omega_x$ then it seems for me making no sense, because $\{x\}\times\mathbb N \in \omega_x$. –  porton Oct 29 '10 at 4:51
    
I mean that the the intersection belongs to $\omega_x$. In general one says that $X$ intersects $Y$ by $Z$ if $X\cap Y=Z$. In this case $Z$ must be in $\omega_x$. By the way, essentially the three first solutions are all the same except that I use the Zorn lemma, and the other people use products of ultrafilters. But all the ideas are the same. Andreas' answer is different and I do not quite understand it, see my comment after his answer. –  Mark Sapir Oct 29 '10 at 9:31
    
"the sets of all sets ... it is clearly a filter" is wrong. Your collection of sets contains $(\mathbb{N}\setminus\{0\})\times\mathbb{N}$. If we add one point $(0;0)$ to this set, it is not in your "set of all sets". So it is not an upper set and so not a filter. Can your proof be saved? –  porton Oct 29 '10 at 21:52
    
Yes, one condition was extra: the intersection with almost all lines should be large, but we do not need a restriction on the intersection with the others. Another way to fix it would be not to say that it is a filter, but to first generate a filter by this set of sets (include all over-sets), and then complete to an ultrafilter. –  Mark Sapir Oct 29 '10 at 22:43
    
Probably really stupid, but I don't understand why "its complement intersects each vertical line by a subset that is either the whole line or the line without one element" is impossible. I will yet try to understand this myself, but a hint would be helpful. –  porton Oct 30 '10 at 17:52

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).

share|improve this answer
    
@Andreas: Are you sure that these are selective ultrafilters? Here is an article, incidentally communicated by you, where a different definition is given: ams.org/journals/proc/1999-127-10/S0002-9939-99-04835-2/… Note that the question here is not about any partition, but about one particular partition. –  Mark Sapir Oct 29 '10 at 9:15
    
As I wrote in my answer (but now with emphasis added), non-principal ultrafilters with the property in the question for all partitions are called "selective" ... The property used as the definition of selectivity in Eisworth's paper is equivalent to this. It immediately implies the definition I gave (partition the pairs $\{a,b\}$ according to whether $a$ and $b$ are in hte same piece of the given partition of $U$), and it immediately follows from the "Ramsey" of Kunen that I cited (by specializing to $n=2$. –  Andreas Blass Oct 30 '10 at 7:11

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.

share|improve this answer
    
Where you've got that usage of integral sign? –  porton Oct 29 '10 at 4:41
    
This is the usual way of integrating measures with respect to a measure. We are adding up the $\mu_n$ values of the set $X$ with respect to the measure $\mu$. –  Joel David Hamkins Oct 29 '10 at 4:58
    
Where can I read a short introduction about such use of integral sign? –  porton Oct 29 '10 at 22:03
    
Porton: A decent book on measure theory should cover this, I would expect, though perhaps the examples there will be mostly non-atomic measures that are not 2-valued as in this case. (In particular, look at the Radon-Nikodym derivative, en.wikipedia.org/wiki/Radon%E2%80%93Nikodym_theorem) But the notation and the background prerequisites are a bit of a distraction here, Joel explicitly defined what it means for the case under consideration. –  Andres Caicedo Oct 30 '10 at 0:26
    
In Wikipedia there is defined integral of a function. But Joel integrates a measure rather than a function. Where can I read about this? –  porton Oct 30 '10 at 20:22

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.

share|improve this answer
    
How you define "large"? (I assume that it means to be in your ultrafilter, correct?) How you define "most"? Why the filter you defined is an ultrafilter? –  porton Oct 29 '10 at 4:40
1  
I think Bjorn's answer is completely fine---it is essentially the same as mine, for the special case where where all $\mu_n$ are the same. That is, $\mu\times\eta=\int\eta d\mu$. –  Joel David Hamkins Oct 29 '10 at 5:02

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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