Elementary Foundations: An introduction to topics in discrete mathematics

The usual notion of $\le$ is a partial order on $\mathbb{N}$ (or $\mathbb{Z}$ or $\mathbb{Q}$ or $\mathbb{R}$), but $<$ is not.

For every set $U\text{,}$ the relation $\subseteq$ is a partial order on $\mathcal{P}(U)\text{,}$ but $⫋$ is not.

For every graph $G\text{,}$ the subgraph relation $⪯$ is a partial order on $\mathcal{S}(G)\text{,}$ the set of subgraphs of $G\text{.}$

Suppose $U$ is a universal set, and consider the collection of finite subsets of $U\text{.}$ Then we have a natural way to compare sizes of these subsets: write $ARB$ to mean $\left|A\right|\le \left|B\right|\text{.}$ However, this relation is not a partial order as it is not antisymmetric. This is because it is possible to have both $ARB$ and $BRA$ with $A\ne B\text{,}$ in the case that $\left|A\right|=\left|B\right|\text{.}$ Changing the relation to mean $\left|A\right|\lneqq \left|B\right|$ doesn’t help, since then it wouldn’t be reflexive.

Now suppose the universal set $U$ is infinite and consider all (hence possibly infinite) subsets of $U\text{.}$ In this case we have a more general idea of smaller and larger, where $A$ is smaller than $B$ if there exists an injection $A\hookrightarrow B$ but no bijection $A\to B\text{.}$ This more general notion of size comparison via cardinality suffers the same flaws as in the finite set case, as it is not reflexive, and if we try to fix that by adding “or same size as” then it will not be antisymmetric.

However, in both finite and (possibly) infinite cases, we can turn cardinality comparison into a partial order using “smaller than or equal to”, where “smaller” must mean strictly smaller in terms of cardinality, but “equal” means equality of sets rather than equality of cardinality.

We can flip “smaller/less than or equal to” around to “larger/greater than or equal to.” For example, for elements $m,n\in \mathbb{N}\text{,}$ write $m⪯n$ to mean $m\ge n\text{.}$ Then $⪯$ is a partial order on $\mathbb{N}\text{.}$

This is an instance of a more general pattern. Given a partial order $⪯$ on a set $A\text{,}$ the inverse relation ${⪯}^{-1}\text{,}$ where $a_1{⪯}^{-1}{a}_2$ means $a_2⪯a_1\text{,}$ is also a partial order on $A\text{,}$ called the dual order.

Let $A=\{a,b,c,d\}\text{,}$ and let us “encode” each element of $\mathcal{P}(A)$ by the following algorithm.

The facts that $\le$ is a partial order on $\mathbb{N}$ and that this encoding process is one-to-one will combine to make $⪯$ a partial order.

Generalizing Example 19.2.10, suppose $f:A\hookrightarrow B$ is an injection where $B$ is partially ordered by ${⪯}_B\text{.}$ Then we can “pull back” the partial order on $B$ to create a partial order on $A$ as follows: define $a_1{⪯}_A{a}_2$ to mean that $f(a_1){⪯}_{B}f(a_2)$ is true. Note that the assumption that $f$ is injective is essential to guarantee that ${⪯}_A$ will be antisymmetric.