Optimal Partitions Amongst Given Set of Partitions – Techniques

infinite-combinatoricspartitionsset-theory

Let $X\neq \emptyset$ be a set. By $\text{Part}(X)$ we denote the set of all partitions of $X$ not containing $\emptyset$ as an element.

First, note that $\bigcup{\frak P}$ is the collection of subsets of $X$ that are a member of at least one partition in ${\frak P}$. We say that ${\frak P}\subseteq \text{Part}(X)$ is admissible if it is closed under refinement and if for all $b\in \bigcup {\frak P}$ there is $b_0\in \bigcup{\frak P}$ such that $b \subseteq b_0$, and $b_0$ is maximal in $\bigcup{\frak P}$ with respect to set inclusion. Moreover, we say that ${\frak P}$ has the optimality property if there is $P_0\in {\frak P}$ such that $|P_0\setminus P| \leq |P \setminus P_0|$ for all $P\in {\frak P}$.

Given ${\frak P}\subseteq \text{Part}(X)$ as well as a non-empty set $S\subseteq X$, we let ${\frak P}|_S$ be ${\frak P}$ "cut down to $S$", or more formally, $${\frak P}|_S := \{P \in \text{Part}(S): (\exists Q \in \text{Part}(X))(\forall
b\in P)(\exists b' \in Q) b = b'\cap S\}.$$

Let $X$ be non-empty and ${\frak P}\subseteq \text{Part}(X)$ be admissible. Suppose that ${\cal C}$ is a collection of subsets of $X$ such that for $C, C'\in {\cal C}$ we have $C\subseteq C'$ or $C'\subseteq C$, and also we have $\bigcup {\cal C} = X$. Suppose further that for every set $C\in {\cal C}$, the collection ${\frak P}|_C \subseteq \text{Part}(C)$ has the optimality property.

Question. Does this imply that $\frak P$ itself has the optimality property?

Note. Without the maximality requirement for admissibility, there would be an easy negative answer for the question. Let $X = \omega$, and let ${\frak P}$ consist of the partitions of $\omega$ such that every block (= member of the partition) is finite. Let ${\cal C}$ consist of the sets of the form $n := \{0, \ldots, n-1\}$ for all positive integers $n$. Then the union of ${\cal C}$ equals $\omega$, and ${\frak P}|_n$ trivially satisfies the optimality property, but ${\frak P}$ itself does not.

Best Answer

Modifying your note at the end slightly, try the following.

Let $X=\{0,1,2,\ldots\}$ and let $P=\{\{0,1\},\{2,3\},\{4,5\},\ldots\}$. Let $\mathfrak{P}$ be all partitions of $X$ which refine $P$ and moreover contain only finitely many of the blocks in $P$ (thus for instance $P$ itself does not belong). Cover $X$ by sets of the form $\{0,1,\ldots,n\}$, like in your note. Now I think $\mathfrak{P}$ is admissible but still fails the optimality property.

Related Question