Show that the Boolean lattice $B_{n}$ is isomorphic to the $n$-fold product of the chain $[2]$.

boolean-algebralattice-ordersorder-theorysolution-verification

For two posets $\left(\Pi_{1}, \preceq_{1}\right)$ and $\left(\Pi_{2}, \preceq_{2}\right)$ we define their (direct) product with underlying set $\Pi_{1} \times \Pi_{2}$ and partial order
$$
\left(x_{1}, x_{2}\right) \preceq\left(y_{1}, y_{2}\right) \quad: \Leftrightarrow \quad x_{1} \preceq_{1} y_{1} \quad \text { and } \quad x_{2} \preceq_{2} y_{2}
$$

Show that the Boolean lattice $B_{n}$ is isomorphic to the $n$-fold product of the chain $[2]$.

I need to show this statement based on first principles. I have a rough idea, but there are some points that I can’t turn into rigorous mathematical statements, so I’d like to ask for some help.

  1. By the definition above, an element of the $n$-fold product of the chain $[2]$, for example in the case $n = 3$, would look like $((a_1,a_2),a_3)$, where $a_1,a_2,a_3 \in \{0,1\}$. In my argument, I want to identify these elements with vertices of a $n$-cube, i.e. the $n$-tuples $\{0,1\}^n$, by just “removing the extra parentheses”. Is this a clear enough bijection?

  2. Assuming that we have the transformation above, my idea for the isomorphism between $B_n = ([n], \subseteq)$ and the vertices of the $n$-cube is as follows: a set $S \subseteq [n]$ would be mapped to a vertex containing $|S| \ 1$’s, with the positions of the $1$’s indexed by the elements in $S$. For $n = 3$, for example, we would have $\{1\} \mapsto (1,0,0)$, $\{2\} \mapsto (0,1,0)$, $\{1,3\} \mapsto (1,0,1)$, $\{1,2,3\} \mapsto (1,1,1)$, etc. How do I make this into precise function definition?

Best Answer

You are right in both points.

A possible way to define your desired map is to take $$S \mapsto (u_1, \ldots, u_n),$$ where $u_i \in \{0,1\}$ and $u_i = 1$ iff $i \in S$.

Related Question