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.


1 Answer 1


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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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