Partially ordered sets (posets, for short) are a pretty useful concept that appear every now and then. As somebody once pointed out to me, they are (of course) just special cases of categories, but let's not go there.

To recall the definition, a poset is a set $X$ with a binary relation $\leq$ such that the following hold

• reflexivity: $a \leq a$ for all $a \in X$;
• antisymmetry: if $a \leq b$ and $b \leq a$, then $a = b$;
• transitivity: if $a \leq b$ and $b \leq c$, then $a \leq c$.

All pretty sensible properties, I'm sure you'd agree!

One of the first examples of posets you would probably see is to take a set of sets, ordered by set inclusion. That is, we say the set $A \leq B$ if $A \subseteq B$. This picture from wikipedia shows the Hasse diagram for the powerset $\mathcal{P}(\{x, y, z\})$.

A natural question (which I never asked before) is "how general is the example of sets ordered by inclusion?" Surely if we can just add elements to sets to enforce relations one by one, we could construct any desired partial order inside a powerset? That's correct!

Let $\phi$ be the isomorphism from $X$ to some powerset. For any pair $x, y \in X$ with $x < y$, we could put $(x, y) \in \phi(y)$ while having $(x, y) \notin \phi(x)$, so as to force $\phi(x) \subsetneq \phi(y)$. We would then also need to add the same pair to all the $\phi(z)$ where $y < z$, for consistency. If you like, this embeds the poset $X$ into $\mathcal{P}(X \times X)$ (ordered by inclusion). But we don't even need to go that far, because there's a really simple bijection, namely

$$ \phi : X \to \mathcal{P}(X) $$

defined by

$$\phi(x) = \{ z \in X \mid z \leq x \}. $$

To see that this gives an order isomorphism, we just need to convince ourselves that

$$ x \leq y \Leftrightarrow \phi(x) \subseteq \phi(y). $$

From how we've constructed $\phi$, we see immediately that $\phi(x) \subseteq \phi(y)$ is equivalent to saying that for all $z \in X$, if $z \leq x$ then $z \leq y$ also. So the $\Rightarrow$ direction holds by transitivity, and the $\Leftarrow$ direction holds by considering $z = x$ (and applying reflexivity).

You might notice that we never used antisymmetry, so this trick works for more general contexts. For example, we could encode the relation $u \to v$ meaning there is a directed path from vertex $u$ to vertex $v$ in a fixed directed (but not necessarily acyclic!) graph by identifying each vertex with the set of all vertices from which it is reachable.