5
$\begingroup$

The following is motivated by an (as of yet) unanswered question on optimal colorings of graphs. I am convinced that the question below has a positive answer in $\newcommand{\ZF}{{\sf (ZF)}}\ZF$, but so far it has escaped me.

Let $X\neq\emptyset$ be a set, and let $\newcommand{\Part}{\text{Part}}\Part(X)$ be the collection of partitions of $X$. For $P, Q \in \Part(X)$ we write $P \newcommand{\preq}{\preceq^*}\preq Q$ if there is an injection $\iota: (P \setminus Q) \to (Q \setminus P)$.

Question. If $P,Q,R\in\Part(X)$ with $P\preq Q\preq R$, does this entail that $P\preq R$?

Note. The answer is easily seen to be positive for $P, Q, R$ finite.

Improve this question
$\endgroup$
5
  • 1
    $\begingroup$ Do you want to restrict to partitions with the same number (cardinality) of parts? That case seems more related to your other question. $\endgroup$
    – Sam Hopkins
    Commented Mar 12 at 14:13
  • 1
    $\begingroup$ It seems that $P \newcommand{\preq}{\preceq^*}\preq Q$ iff the cardinality of $P$ is no greater than that of $Q$. But then the "yes" answer is trivial. $\endgroup$
    – Iosif Pinelis
    Commented Mar 12 at 16:34
  • 1
    $\begingroup$ @IosifPinelis: that’s not right. See the example in the question Dominic linked to. $\endgroup$
    – Sam Hopkins
    Commented Mar 12 at 18:54
  • 1
    $\begingroup$ @SamHopkins : Thank you for your comment. I thought the partitions are finite. $\endgroup$
    – Iosif Pinelis
    Commented Mar 12 at 20:00
  • $\begingroup$ @SamHopkins Thanks for your comment Sam -- I might restrict it to the same cardinality of parts / blocks -- but my hope is that the transitivity for $\preceq^*$ holds even in the general case. $\endgroup$
    – Dominic van der Zypen
    Commented Mar 12 at 20:48

1 Answer 1

Reset to default
7
$\begingroup$

Counterexample. Consider the following partitions of $\omega$.

$P=\{\{0\},\{1\},\{2\},\{3\},\{4\},\{5\},\{6\},\dots\}$
$Q=\{\{0,1,2\},\{3,4\},\{5,6\},\dots\}$
$R=\{\{0,1\},\{2\},\{3\},\{4\},\{5\},\{6\},\dots\}$

Now $|P\setminus Q|=|Q\setminus P|=|Q\setminus R|=|R\setminus Q|=\aleph_0$, so $P\preceq^*Q\preceq^*R$;
but $|P\setminus R|=2$ and $|R\setminus P|=1$, so $P\not\preceq^*R$.

On the other hand, if $P\prec^*Q$ means $|P\setminus Q|\lt|Q\setminus P|$, then (at least in ZFC, I don't know about ZF) we have: $$P\prec^*Q\prec^*R\implies P\prec^*R;$$ $$P\prec^*Q\preceq^*R\implies P\preceq^*R;$$ $$P\preceq^*Q\prec^*R\implies P\preceq^*R.$$ Here $P$, $Q$, $R$ are just sets, it doesn't matter if they are partitions. It will suffice to prove the first implication, as the others are just restatements. So assume for a contradiction that there are sets $P$, $Q$, $R$ such that $P\prec^*Q\prec^*R\preceq^*P$.

Let $a=|P\setminus(Q\cup R)|$, $b=|Q\setminus(P\cup R)|$, $c=|R\setminus(P\cup Q)|$, $d=|(P\cap Q)\setminus R|$, $e=|(Q\cap R)\setminus P|$, $f=|(P\cap R)\setminus Q|$; so that $|P\setminus Q|=a+f$, $|Q\setminus P|=b+e$, etc. From $P\prec^*Q\prec^*R\preceq^*P$ we have: $$a+f\lt b+e,\tag1$$ $$b+d\lt c+f,\tag2$$ $$c+e\le a+d,\tag3$$ where $a$, $b$, $c$, $d$, $e$, $f$ are some (finite or infinite) cardinal numbers. From $(1)$ and $(2)$ we have $$a+b+d+f\lt b+c+e+f\tag4$$ since two strict inequalities can be added. If we also had $c+e\lt a+d$, then adding this to $(4)$ we would get the nonsensical $a+b+c+d+e+f\lt a+b+c+d+e+f$. Therefore $c+e=a+d$, but then $b+c+e+f=a+b+d+f$, contradicting $(4)$.

Improve this answer
$\endgroup$

You must log in to answer this question.

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