Poset (Partial Order Relations)

or order relation

Discrete Mathematics ETH, p.60

A partial order on a set $A$ is a relation that is reflexive, antisymmetric, and transitive

The only difference to an equivalence relation is antisymmetric instead of symmetric Noted as $⪯$

Example

$A=\mathbb{Z}$, Relation $⪯=\le$

Definition

$$\prec \stackrel{def}{=}⪯\setminus \text{id}$$

Example

$A=\mathbb{N}\setminus \{0\},⪯=|$ (division relation) $A=\mathcal{P}(B),⪯=\subseteq$

Definition Poset

$(A;⪯)$ is a poset. It’s just a partial order relation on a set, and this thing is called a poset

Lemma

If $(A;⪯)$ is a poset, $\prec$ is transitive

$a\prec b⟹a⪯b\wedge a\ne b$ $b\prec c⟹b⪯c\wedge b\ne c$ $a⪯b\wedge b⪯c⟹a⪯c$

Hasse diagrams

Combination of Posets

Direct Product

$(A;⪯)\times (B;⊑)$ is $(A\times B;\le )$ with $(a_1,b_1)\le (a_2,b_2)\stackrel{def}{⟺}(a_1⪯a_2)\wedge (b_1⊑b_2)$

(see similar concept External Direct Product in Groups)

lexicographic order

For $(A;⪯)$ and $(B;⊑)$, $(A\times B;{\le }_{lex})$ is also a poset. $(a_1,b_1){\le }_{lex}(a_2,b_2)\stackrel{def}{⟺}(a_1\prec a_2)\vee (a_1=a_2\wedge b_1⊑b_2)$

NOTE

Think of the relations of two-digits numbers (A is the first digit, B is the second digit)

Definition: totally ordered

Quote

If any two elements of a poset $(A;⪯)$ are comparable, then A is called totally ordered (or linearly ordered) by $⪯$.

The hasse diagram would look like a line. (reason why it is also called as linearly ordered)

Definition: well-ordered

Quote

A poset $(A;⪯)$ is well-ordered if it is totally ordered and if every non-empty subset of A has a least element.

NOTE

every totally ordered finite poset is well-ordered