I'm interested in a possible generalization of Tiling relation on the set of partitions (the question has only been partially answered).

Let $x$ be an infinite set and let $\text{Part}(x)$ be the collection of all partitions of $x$. Moreover, 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$.

Let $\mathcal{A}\subseteq \text{Part}(x)$ be a non-tempty collection of partitions on the set $x$ such that there is a set $M$ of subsets of $x$ so that every member of $\mathcal{A}$ refines $M$ (that is, for every $A\in\mathcal{A}$ and $a\in A$ there is $m\in M$ with $a\subseteq m$).

Question. Is there a partition $Z\in\text{Part}(x)$ such that

  • $Z$ refines $M$ and
  • $Z \triangleleft A$ for all $A\in\mathcal{A}$?

1) This question (as posed) has a simple negative answer. Just take any countable set $x$ and put $M$ be the family of finite subsets of $x$. Then for the family $\mathcal A$ of all possible partitions of $x$ into finite subsets there is no partition $Z$ of $x$ into finite sets such that $Z\triangleleft A$ for every $A\in\mathcal A$.

Indeed, any partition $Z$ of $x$ into finite sets is infinite. So, we can take any 2-element subfamily $S=\{z,z'\}\subset Z$ and take any partition $A\in\mathcal A$ such that $\{z,z'\}\in A$. Then $|S|=2>1=|A_{[\cup S]}|$, witnessing that $Z\not\triangleleft A$.

2) A bit more complicated counterexample can be constructed as follows. Consider the family $\mathcal A$ of all possible partitions of the set $\mathbb P:=\mathbb R\setminus\mathbb Q$ of irrational numbers into compact susbets. Let $M$ be the family of all compact subsets of $\mathbb P$, endowed with the Vietoris topology. It is well-known that the space $M$ is separable and metrizable.

Then there is no partition $Z$ of $\mathbb P$ into compact subsets such that $Z\triangleleft A$ for all $A\in\mathcal A$.

Indeed, since the space $\mathcal P$ is not $\sigma$-compact, each partition $Z$ of $\mathbb P$ into non-empty compact subsets of $\mathbb P$ is uncountable and considered as a subspace of the hyperspace $M$ is not discrete. Hence $Z$ contains a sequence $\{z_n\}_{n\in\omega}\subset Z$ of pairwise distinct elements that converges to a compact set $z_\omega\in Z$. Then the set $S:=\{z_n\}_{n\le\omega}$ has compact union in $\mathbb P$ and hence $\bigcup S\in A$ for some partition $A$ of $\mathbb P$ into compact sets. Taking into account that $|S|=\omega>|A_{[\cup S]}|=1$, we conclude that $Z\not\triangleleft A$.

3) In fact, the gap between $|S|$ and $|A_{[\cup S]}|$ can be arbitrarily high. Indeed, for any infinite regular cardinal $\kappa$ consider the set $x=\kappa$ and the family $M$ of subsets of $x$ of cardinality $<\kappa$. Let $\mathcal A$ be the family of all possible partitions of $x$ into subsets of cardinality $<\kappa$. Then for any partition $Z\in\mathcal A$ and any subfamily $S\subset Z$ of cardinality $|S|<\kappa$ there union $\bigcup S$ has cardinality $<\kappa$ and hence is an eleemnt of some partition $A\in\mathcal A$, for which $|A_{[\cup S]}|=1$.

| cite | improve this answer | |

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.