The lattice of partial partitions

327 Views Asked by At

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?

1

There are 1 best solutions below

1
On BEST ANSWER

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$.