$\DeclareMathOperator{\NPU}{\operatorname{NPU}}\DeclareMathOperator{\RK}{\,\mathrm{RK}}$A pre-ordered set is a pair $(P, \leq)$ where $P$ is a set and $\leq\subseteq P\times P$ is a reflexive and transitive relation.

Let $\NPU(\omega)$ be the set of non-principal ultrafilters on $\omega$. The Rudin-Keisler pre-order on $\NPU(\omega)$ is defined by $${\cal U} \leq_{\RK} {\cal V} :\Leftrightarrow (\exists f:\omega\to\omega)(\forall U\in{\cal U}) f^{-1}(U)\in {\cal V} .$$

It is easy to see that $\leq_{\RK}$ is reflexive and transitive, but not anti-symmetric.

Question. Given a finite pre-ordered set $(P,\leq)$, is there a finite subset $S\subseteq\NPU(\omega)$ such that $(P,\leq)$ is isomorphic to $S$ with the pre-order inherited from $\text{NPU}(\omega)$?

  • 2
    $\begingroup$ There are incomparable ultrafilters, and since the product operation gives you upper bounds, one might hope to find a sufficiently independent family of ultrafilters, whose products make a copy of a finite Boolean algebra in the RK order. This would embed any partial order into the RK order. For pre-orders, you can easily handle clusters of equivalent nodes, since any nontrivial permutation of $\omega$ makes an isomorphic ultrafilter, which is RK equivalent but not equal. So my strategy is: find a strong antichain of ultrafilters, meaning incomparable products are RK incomparable. $\endgroup$ – Joel David Hamkins Oct 31 at 21:41
  • 1
    $\begingroup$ In particular, I claim that to embed every finite preorder it suffices to embed every finite partial order. $\endgroup$ – Joel David Hamkins Oct 31 at 21:49
  • 1
    $\begingroup$ I agree with @Joel's strategy, and I'll add that under CH (or weaker assumptions like cov(category)=c), there are lots of non-isomorphic selective ultrafilters, and these constitute what Joel calls a strong antichain. $\endgroup$ – Andreas Blass Oct 31 at 22:10
  • 1
    $\begingroup$ I wouldn't be surprised if the existence of an infinite strong antichain could be proved in ZFC, perhaps by an independent-sets argument. $\endgroup$ – Andreas Blass Oct 31 at 22:13
  • 1
    $\begingroup$ @AndreasBlass Could you post an answer explaining why nonisomorphic selective ultrafilters necessarily form a strong antichain? $\endgroup$ – Joel David Hamkins Nov 1 at 9:41

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.