Let $X$ be an infinite set and write $X^\ast$ for the collection of all free ultrafilters on $X$.

Two bipartitions $\{A,A^\complement\}$ and $\{B,B^\complement\}$ of $X$ are said to be nested if we can draw them both as lines in a drawing of $X$ such that the two lines possibly meet, but do not cross; formally: if one of the following four cases holds:

  • $A\subseteq B$
  • $A\subseteq B^\complement$
  • $A\supseteq B$
  • $A\supseteq B^\complement$

A nested set of bipartitions of $X$ is called a tree set of $X$.

You might know these definitions from a recent development around tree decompositions of graphs. In the setting of finite graphs, tree sets can be viewed as tree decompositions.

Let us say that a bipartition $\{A,A^\complement\}$ distinguishes two ultrafilters $U\neq U'\in X^\ast$ if either $A\in U$ and $A^\complement\in U'$ or vice versa. Then a tree set of $X$ with any two distinct free ultrafilters on $X$ being distinguished by some bipartition in that tree set can be seen as tree-like way of distinguishing/displaying the free ultrafilters on $X$.

My question is, whether there always exists such a tree set (for every set $X$).

As far as I can see, the existence of such a tree set is not obstructed by an obvious cardinality argument, for there are $2^{2^{\vert X\vert}}$ free ultrafilters and each of the $2^{\vert X\vert}$ many possible bipartitions can be oriented in two ways.

If one tries to construct such a tree set, an obvious try is to use Zorn's lemma to yield a maximal tree set (w.r.t. inclusion), but if $X=\omega$ this might return something like the set of all $\{n,\omega\setminus n\}$ (with $n<\omega$) which distinguishes nothing and cannot be extended to include bipartitions with both sides infinite. Of course we can decide to consider only bipartitions with both sides infinite, but the bad example might be extended to $X=\omega_1$ and $\{\alpha,\omega_1\setminus\alpha\}$ where $\omega\le\alpha<\omega_1$ or something.

Thanks for reading and sharing your thoughts!

  • $\begingroup$ If you want anything meaningful, you'll need to weaken your notion of "nested." For example, focusing only on the case when $X$ is countable, if you replaced $\subset$ and $\supset$ in all cases with the same relations taken mod-finite, you will actually be able to distinguish certain types of ultrafilters on $\omega$. $\endgroup$ – Not Mike Jul 8 '18 at 19:13
  • $\begingroup$ That's too bad, I'm afraid that weakening the notion of nested is not an option for me. You say that finding a tree set already fails for countable $X$---what makes you think so? $\endgroup$ – Sansevieria Jul 8 '18 at 20:15

Your Answer

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

Browse other questions tagged or ask your own question.