# The lattice of partial partitions

In perusing A kind of Eulerian numbers connected to Whitney numbers of Dowling lattices I have gotten confused over what seems a very elementary point. The beginning of section 2 of the paper is

Let $X = \{x_1, \dots , x_n\}$ be a finite set with $n$ elements. A partial partition of $X$ is a partition of a subset of $X$. That is, $\alpha = \{A_1, \dots , A_r\}$ is a partial partition of $X$, when $A_i \ne \varnothing$ $(i = 1,\dots, r)$, $A_i \cap A_j = \varnothing$ $(i \ne j)$ and $\cup_{i=1}^r A_i \subset X$ [ed. here I think $\cup_{i=1}^r A_i \subseteq X$ is really intended]. The elements of $\alpha$ are called blocks. Let $Q_n$ be the set of all partial partitions of $X$. The set $Q_n$ can be partially ordered: let $\alpha \le \beta$ if every block in $\beta$ is a union of blocks from $\alpha$. So ordered, $Q_n$ is isomorphic to the lattice of partitions of an $(n + 1)$-set $X \cup \{x_{n+1}\}$.

While it is certainly true that these two lattices (viz., partial partitions of $[n]$ and partitions of $[n+1]$) have the same number of elements, I don't see how the last sentence above can be true. For instance, the lattice $\Pi_3$ of partitions of $[3]$ has three maximal chains, while as far as I can tell the lattice $Q_2$ has only two. Am I missing something or is the quoted claim (which appears immaterial to the actual thrust of the paper) incorrect?

• The claim sounds correct, with the natural mapping that elements not contained in any block of a partial partition get lumped with $x_{n+1}$ in the full partition. – hardmath Jan 25 '16 at 14:16
• @hardmath - your mapping is why the two lattices clearly have the same size. But when I draw $Q_2$ I get two maximal chains, viz. $() \le (1) \le (1)(2) \le (12)$ and $() \le (2) \le (1)(2) \le (12)$, while for $\Pi_3$ the three maximal chains are $(1)(2)(3) \le (12)(3) \le (123)$, $(1)(2)(3) \le (13)(2) \le (123)$, and $(1)(2)(3) \le (1)(23) \le (123)$. – S Huntsman Jan 25 '16 at 14:27
• It's not true that $(1)\le(1)(2)$: $(2)$ is not a union of blocks of $(1)$. In fact, $\alpha\le\beta$ implies that $\bigcup\alpha\supseteq\bigcup\beta$. – Brian M. Scott Jan 25 '16 at 15:23
• @BrianM.Scott- thanks for your comment. I'd been using the order for $\Pi_{\le n}$ (a la Hanlon, Hersh, and Shareshian) instead of $Q_n$ and didn't notice these were different. – S Huntsman Jan 25 '16 at 16:13

You don't have $(1) \le (1)(2)$ because $(2)$ is not a reunion of blocks from $(1)$, just like you don't have $(1)(23) \le (1)(2)(3)$ because $(2)$ isn't a reunion of blocks from $(1)(23)$.
You can prove that the natural bijection $f : \alpha \mapsto \alpha \cup \{ \{x_{n+1}\} \cup X \setminus \bigcup \alpha \}$ preserves the ordering.
If $\alpha \le \beta$ then every block of $f(\beta)$ that was in $\beta$ is still a reunion of blocks from $\alpha$ hence of blocks of $f(\alpha)$. And the new block in $f(\beta)$ is the reunion of the unused blocks from $\alpha$ and the new block in $f(\alpha)$. So $f(\alpha) \le f(\beta)$
Conversely, if $f(\alpha) \le f(\beta)$ this is almost direct because the blocks of $\beta$ are also in $f(\beta)$ so they must be reunions of blocks of $f(\alpha)$. Since blocks in $\beta$ don't contain $x_{n+1}$ they can't use the new block of $f(\alpha)$ so they can only take blocks of $\alpha$. So $\alpha \le \beta$.