Additional Concepts for Posets

We say \((X,P)\) and \((Y,Q)\) are isomorphic, and write \((X,P) \cong(Y,Q)\) if there exists a bijection (11 and onto map) \(f:X\to Y\) so that \(x_1\le x_2\) in \(P\) if and only if \(f(x_1)\le f(x_2)\) in \(Q\). In this definition, the map \(f\) is called an isomorphism from \(\bfP\) to \(\bfQ\). In , the first two posets are isomorphic.

An isomorphism from \(\bfP\) to \(\bfP\) is called an automorphism of \(\bfP\). An isomorphism from \(\bfP\) to a subposet of \(\bfQ\) is called an embedding of \(\bfP\) in \(\bfQ\). In most settings, we will not distinguish between isomorphic posets, and we will say that a poset \(\PXP\) is contained in \(\QYQ\) (also \(\bfQ\) contains \(\bfP\)) when there is an embedding of \(\bfP\) in \(\bfQ\). Also, we will say that \(\bfP\) excludes \(\bfQ\) when no subposet of \(\bfP\) is isomorphic to \(\bfQ\), and we will frequently say \(\bfP=\bfQ\) when \(\bfP\) and \(\bfQ\) are isomorphic.

With the notion of isomorphism, we are lead naturally to the notion of an unlabeled posets, and in , we show a diagram for such a poset.

Note that the poset shown in has the property that there is only one maximal point. Such a point is sometimes called a one, denoted not surprisingly as\(1\). Also, there is only one minimal point, and it is called a zero, denoted\(0\).

The dual of a partial order \(P\) on a set \(X\) is denoted by \(P^d\) and is defined by \(P^d=\{(y,x):(x,y)\in P\}\). The dual of a poset \(\PXP\) is denoted by \(\bfP^d\) and is defined by \(\bfP^d=(X,P^d)\). A poset \(\bfP\) is self-dual if \(\bfP=\bfP^d\).

Condensed: the full section is in Keller & Trotter, Applied Combinatorics.