Let $x\neq \emptyset$ be a set and let $\text{Part}(x)$ be the collection of all partitions of $x$. We need the following notation. Let $P \in \text{Part}(x)$ and $t\subseteq x$. We set $$P_{[t]} = \{p\in P:p\cap t \neq \emptyset\}.$$ We define the tiling relation on $\text{Part}(x)$ by $$ P \triangleleft Q \textrm{ if and only if for all } S\subseteq P\textrm{ we have } \mathsf{card}(S) \leq \mathsf{card}(Q_{[\bigcup S]}).$$ In other words, the relation $P\triangleleft Q$ holds if no subset $S$ of $P$ is covered by a subset of $Q$ having a smaller cardinality than $S$.


  1. Is the relation $\triangleleft$ on $\text{Part}(x)$ transitive?
  2. For $P,Q \in \text{Part}(x)$ is there $Z\in \text{Part}(x)$ such that
    • $Z$ refines $P\cup Q$ and
    • $Z \triangleleft P$ and $Z\triangleleft Q$?
  • $\begingroup$ Thanks for accepting my answer - let me emphasise that I wasn't able to answer the second question entirely, and I would very much like to see the complete answer. $\endgroup$ – Dominic van der Zypen Jan 6 '15 at 12:30

Question 1. The answer is No. Let $x= \{1,2,3,4\}$. For $i\in \{1,2,3\}$ let $P_i$ be the partition that has $\{i, i+1\}$ as the only non-singleton partition block. Then $P_i\triangleleft P_{i+1}$ for $i = 1,2$, but it is easy to verify that $\neg(P_1 \triangleleft P_3)$.

Question 2. I can only answer this in the case that the base set $x$ is finite. Let $x$ be a set of cardinality $n\in \omega$, and let $P, Q \in \text{Part}(x)$. Consider the set

$$S = \{Y \in \text{Part}(x) : Y \textrm{ refines }P \cup Q\}$$

and set

$$m = \min \{\text{card}(Y) : Y \in S \}.$$

We have $m \leq n$ , and there is $Y_0 \in S$ with $\text{card}(Y_0) = m$. Then I claim that $Y_0 \triangleleft P$ and $Y_0 \triangleleft Q$. The reason is if $\neg(Y_0 \triangleleft P)$, say, then you can find a refinement of $Y_0 \cup P$ (which also refines $P \cup Q$) that has smaller cardinality than $Y_0$, contradicting the minimality of $\text{card}(Y_0)$.

However I would be interested to see what the answer is to Question 2 for base set $x$ infinite.

| cite | improve this answer | |

Your Answer

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