Sublattices of rank n of the Boolean algebra and partial orders

Question

Let $f(n)$ be the number of sub lattices of rank n the Boolean algebra $B_n$. I want to show that $f(n)$ is also the number of partial orders of $P$ on $[]$.

I have read this question from Counting Partial Orders Using Sub-lattices (Stanley EC Chapter 3 Problem 46a) and it suggests we should write a bijection between them, assigning to each partial order on $[]$ a sublattice of the powerset of $[]$ and vice versa but I am not sure how this would work, thanks

Answer 1

There are maps $\alpha$ and $\beta$ between sublattices $L$ of the Boolean algebra $B_n=\{S\mid S\subseteq\{1,\ldots,n\}\}$ which contain $\emptyset$ and $\{1,\ldots,n\}$ and preorders $\le$ on $\{1,\ldots,n\}$ given by \begin{eqnarray*} \alpha:\,\,\,\, L&\mapsto&\le \hbox{ such that } i\le j \hbox{ iff for all $S\in L$, $i\in S$ implies $j\in S$},\\ \beta: \ \le&\mapsto&\{S\subseteq\{1,\ldots,n\} \mid \hbox{$i\in S$ and $i\le j$ implies that $j\in S$}\}. \end{eqnarray*} A preorder is a binary relation that is reflexive and transitive, but not necessarily antisymmetric. The reason for the condition that $\emptyset$ and $\{1,\ldots,n\}$ are in $L$ is that this makes $L$ closed under arbitrary intersections and unions, including empty ones. It's easy to check that $\alpha$ and $\beta$ are inverse to each other, so they are bijections.

If $\le$ is not antisymmetric then there are $i\ne j$ such that $i\le j$ and $j\le i$, so $i\in S$ iff $j\in S$ for all $S\in\beta(\le)$ and $\beta(\le)$ cannot have rank $n$. On the other hand, if $\le$ is a partial order and $S$ and $T\supsetneq S$ are in $\beta(\le)$, let $j$ be any maximal element of $T\setminus S$. Then $S\cup\{j\}$ will also be in $\beta(\le)$, so any covering relation in $\beta(\le)$ must add exactly one element. In this case then $\beta(\le)$ has rank $n$.

Added later: You could define $\alpha$ and $\beta$ more generally as maps between the set of all sets of subsets of $\{1,\ldots,n\}$ and the set of all relations on $\{1,\ldots,n\}$. Then, you get a Galois connection between these two sets. $\alpha \circ \beta$ sends any relation to its reflexive-transitive closure, and $\beta \circ \alpha$ sends any set of subsets of $\{1,\ldots,n\}$ to the lattice including $\emptyset$ and $\{1,\ldots,n\}$ generated by it.

Answer 2

To make the above answer more clear (specifically the map from partial orders to sublattices), I would say define $L$ to be, given a poset $P$ on $[n]$, the set of all subsets of $[n]$ (i.e. elements of $B_{n}$) s.t. $x\in S$ and $x\prec y$ implies $y\in S$.

Letting $\rho(S) = |S|$, $L$ is clearly ranked and has rank $n$. To prove that $L$ is a lattice, notice that $S_{1}\vee S_{2} = S_{1}\cup S_{2}$ and $S_{1}\wedge S_{2} = S_{1}\cap S_{2}$ for any $S_{1}, S_{2}\in L$, which are not difficult to show to be elements in $L$.