Which posets arise as $P\to\Bbb B$ for $P$ a poset?

93 Views Asked by At

Let $\Bbb B$ be the poset $\{\top,\bot\}$ with $\bot\leq\top$. Given a poset $P$ let $P\to\Bbb B$ be the poset of order-preserving functions from $p$ to $\Bbb B$, ordered by $f\leq g$ if and only if $f(p)\leq g(p)$ for every $p$ in $P$. Which posets arise as $P\to\Bbb B$ for some $P$?


I know that if we restrict $P$ to be a discrete poset then we get precisely the complete atomic Boolean algebras, and this gives an equivalence of categories $\bf Set^\rm{op}\simeq\bf CABA$. So what I'm asking for is an analogous description of $\bf Poset^\rm{op}$.

2

There are 2 best solutions below

5
On BEST ANSWER

Let $\mathcal O(P)$ denote the lattice of order ideals of $P$, and $\langle P \to \Bbb B\rangle$ be the poset of order-preserving functions from $P$ to $\Bbb B$.
We prove that $\mathcal O(P)$ is isomorphic to the order-dual of $\langle P\to\Bbb B\rangle$, that is, $\langle P\to\Bbb B\rangle$ is isomorphic to the poset of order-filters of $P$.

Let us star by defining, for each subset $U$ of $P$, the characteristic function of $U$, as $\chi_U:P\to\Bbb B$, with $\chi_U(x)=\top$ iff $x \in U$.
A subset $U$ of $P$ is an order-filter (or up-set) iff $\chi_U$ is order-preserving.
As $$\chi_U \leq \chi_V \Leftrightarrow U \subseteq V,$$ it follows that $U \mapsto \chi_U$ is an order-isomorphism from the order-filters of $P$ (dual of $\mathcal O(P)$) to $\langle P \to \Bbb B\rangle$.

Since the order-dual of a poset is still a poset, we may conclude that the posets that look like $\langle P \to \Bbb B\rangle$ are precisely the posets (lattices) of order-ideals (down-sets) of some poset (in this case, the order dual of $P$).


Update.

From Introduction to Lattices and Order, by Brian Davey and Hilary Priestley, 2nd edition, we have

Theorem 10.29. Let $L$ be a lattice. The following are equivalent:

  1. $L$ is isomorphic to $\mathcal O(P)$ for some poset $P$;
  2. $L$ is isomorphic to a complete lattice of sets;
  3. $L$ is distributive and both $L$ and $L^{\partial}$ are algebraic;
  4. $L$ is complete, satisfies (JID) and the completely join-irreducible elements are join-dense;
  5. the map $\eta:a\mapsto \{x\in \mathcal J_p(L):x\leq a\}$ is an isomorphism from $L$ onto $\mathcal O(\mathcal J_p(L))$;
  6. $L$ is completely distributive and algebraic;
  7. $L$ is complete, satisfies (JID) and (MID) and is weakly atomic.

About the notation above, $L^{\partial}$ denotes the order-dual of $L$, (JID) is the join-infinite distributive law: $$x \wedge \bigvee_{j \in J}y_j = \bigvee_{j \in J}x\wedge y_j,$$ while (MID) is the dual condition.
The set $\mathcal J_p(L)$ is the set of completely join-prime elements of $L$.

0
On

The poset of order ideals can be identified with $hom(P,\mathbb{B}$), and this poset is a distributive lattice. In the finite case (and in a mild infinite case), we have that every finite distributive lattice arises in this way, and we can describe the poset associated to the distributive lattice as the subset of join irreducibles with induced order.

This gives a (contravariant) equivalence of categories of finite posets and finite distributive lattices.

This is spelled out in detail in Stanley's Enumerative Combinatorics, Vol 1, chapter 3 for posets in general, and Theorem 3.4.1/proposition 3.4.3 for this exact point. His $J(P)$ is your "maps of $P$ to $\mathbb{B}$".