7
$\begingroup$

The following result is relatively well-known: (for example in Math StackExchange answer #37161)

For every countable linear order $(R,\prec)$, there is an $X\subseteq\mathbb Q$ such that $(R,\prec)$ is isomorphic to $(X,<)$, i.e. $X$ ordered by the usual order on rationals.

Generalizing this idea, the paper "Embedding Trees in the Rationals" (Baumgartner, Malitz, Reinhardt, Proceedings of the National Academy of Sciences vol. 67, no. 4, 1970) considered a weaker notion of embedding into the rationals. They define:

[$(P,\leq)$] is tree-like iff for each $z\in P$, $P_q=\{x\in P:x\leq q\}$ is linearly ordered. $P$ is a tree iff each $P_q$ is well-ordered.

...

$P$ is embeddable in the rationals iff there is a function $f:P\to\mathbb Q$ preserving strict order, i.e., such that $x<y$ implies $f(x)<f(y)$. [Blackboard bold added in this quote.] Note that $f$ is not required to be one-one.

The main result of the paper is that Martin's axiom implies that every tree $(P,<)$ of cardinality $\leq\aleph_1$ and with no uncountable chains embeds into the rationals, and that since this consequent implies the Suslin hypothesis, it is independent of ZFC.

At the end of the paper, there are three open problems listed. The first two are even more general, as they deal with partial orders in general embedding into the rationals:

  1. Is it consistent with ZFC to assume that for any partial order $P$, if $\textrm{card }P=\aleph_1$ and every uncountable subset of $P$ contains an uncountable anti-chain, then $P$ can be embedded into the rationals?
  2. (Galvin, unpublished) Is it consistent with ZFC to assume that for any partial order $P$, if $\textrm{card }P=\aleph_2$ and if every $P'\subseteq P$ with $\textrm{card }P'\subseteq\aleph_1$ can be embedded in the rationals, then $P$ can be embedded in the rationals?

All seem to be variations on the question of what partial orders embed into $(\mathbb Q,<)$. Has there been progress on this topic in the last 50 years?

$\endgroup$
2
  • $\begingroup$ I've updated my answer with references proveded in comments by @Holo. That 1991 Milner–Pouzet paper may be relevant to your query. $\endgroup$
    – bof
    Commented Sep 9, 2023 at 18:46
  • $\begingroup$ Small gripe: I don't love using the word "embed" when the image is not an isomorphic copy of the domain. $\endgroup$ Commented Sep 10, 2023 at 9:27

1 Answer 1

10
$\begingroup$

The following simple counterexample to Question 1 can be found on p. 473 of the Milner–Pouzet paper cited below.

Let $P=\omega_1\times\omega_1$ with the strict partial order $$(x,y)\lt(x',y')\iff x\lt x'\text{ and }y\gt y'.$$ By the Erdős–Dushnik–Miller theorem, every uncountable poset contains either an uncountable antichain or an infinite chain. Since $P$ contains no infinite chains, every uncountable subset of $P$ contains an uncountable antichain.

$P$ is not the union of countably many antichains (i.e., is not embeddable in $\mathbb Q$) because an antichain in $P$ can have uncountable intersection with at most one subset of the form $\{x\}\times\omega_1$.

Question 2 seems to be much deeper, and I don't know anything about it. The nearest thing I've found to a reference is in a survey paper of Stevo Todorcevic, Combinatorial dichotomies in set theory, Bull. Symbolic Logic 17 (2011), 1–72. In that survey Conjecture 3.4 is called "Galvin's Conjecture", and it is analogous to Question 2, but it asks about decompositions of posets into chains rather than antichains. On the other hand Conjecture 4.3 (Rado's conjecture) is just Question 2 for the special case of trees, and is apparently an open problem, or was at the time of that survey. But I've only skimmed it, and may have missed or misunderstood something.

Order embeddings and antichain decompositions. I thank @Holo for informing me in a comment that the following proposition is a special case of a theorem of Đuro Kurepa, Ensembles ordonnés et ramifiés, Thèse, Paris 1935; Math. Belgrade 4 (1935), 1–138. See also E. C. Milner and M. Pouzet, Antichain decompositions of a partially ordered set, in: Colloq. Math. Soc. János Bolyai 60, Sets, Graphs, and Numbers (Budapest, 1991), pp. 469–498.

Proposition. A poset $P$ is embeddable in $\mathbb Q$ if and only if $P$ is the union of countably many antichains.

Proof. For the nontrivial direction, suppose $P$ is the union of antichains $A_1,A_2,A_3,\dots,A_n,\dots$. Recursively construct order-preserving maps $$f_n:A_1\cup A_2\cup\cdots\cup A_n\to\mathbb Q$$ such that the range of $f_n$ is finite (in fact has at most $2^n-1$ elements) and $f_n\subseteq f_{n+1}$. Then $\bigcup_{n=1}^\infty f_n$ is an embedding of $P$ into $\mathbb Q$.

$\endgroup$
5
  • $\begingroup$ +1, clever poset! About the last paragraph and the comment on the original question, is it shown over ZFC+MA that $P$ is embeddable in $\mathbb Q$ iff $P$ is the union of countably many antichains? $\endgroup$
    – C7X
    Commented Sep 8, 2023 at 4:24
  • 1
    $\begingroup$ The last Proposition is a theorem by Kurepa, who proved the more general form statement: For a cardinal $κ$ let $T_2(κ)=(2^{<κ}, <_{lex})$, if $P$ is a union of $κ$-many anti-chains, then it is embeddable into $T_2(κ)$. Let $(A_α\mid α<κ)$ be some well-ordering of an antichain decomposition (as we may assume they are disjoint), and let $ι(x)$ to be the unique $α$ with $x∈A_α$. Define the witness $f:P→T_2(κ)$ by $f(x)∈2^{ι(x)}$ with $f(x)_α=1$ iff there exists $y∈A_α$ with $y≤x$ $\endgroup$
    – Holo
    Commented Sep 9, 2023 at 10:46
  • 1
    $\begingroup$ I noticed I made a mistake in my previous comment, the correct function is $f:P→T_2(κ)$ with $f\in 2^{ι(x){\boldsymbol{+1}}}$ $\endgroup$
    – Holo
    Commented Sep 9, 2023 at 15:51
  • 1
    $\begingroup$ @bof the original reference is in French I believe (I think it is this), but you can find a mention of this fact in "Antichain Decompositions of a Partially Ordered Set" $\endgroup$
    – Holo
    Commented Sep 9, 2023 at 17:29
  • 1
    $\begingroup$ @bof yeah, I think it is fine $\endgroup$
    – Holo
    Commented Sep 9, 2023 at 21:31

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .