Partial Orders

Given a partial order $R$ on a set $A$:

An element $x\in A$ is maximal if

$$\forall_{a\in A} xRa\rightarrow x=a.$$

An element $x\in A$ is minimal if

$$\forall_{a\in A} aRx\rightarrow x=a.$$

An element $x\in A$ is a greatest element if

$$\forall_{a\in A} aRx.$$

An element $x\in A$ is a least element if

$$\forall_{a\in A} xRa.$$

Let $B\subseteq A$.

An element $x\in A$ is a lower bound of $B$ if

$$\forall_{b\in B} xRb.$$

An element $x$ is a greatest lower bound (glb) of $B$ if $x$ is a lower bound of $B$, and for every lower bound $x'$ of $B$, $x'Rx$.

Let $B\subseteq A$.

An element $x\in A$ is a upper bound of $B$ if

$$\forall_{b\in B} bRx.$$

An element $x$ is a least upper bound (lub) of $B$ if $x$ is an upper bound of $B$, and for every upper bound $x'$ of $B$, $xRx'$.

Example: project planning.

Code	Activity	Depends on:
A	Rent concert hall	B
B	Get sponsors	-
C	Print programs	D,A,J
D	Get program ads	E
E	Plan advertising	B
F	Print tickets	G
G	Set ticket prices	B
H	Advertise	E
I	Sell tickets	F
J	Get program material	-
K	Hold concert	G,C,I

A partition of a set $A$ is a collection of $k$ sets $A_i$ ($1\leq i\leq k$) so that:

• $A_i\not=\emptyset$ for all $i$, $1\leq i\leq k$,
• $$\bigcup_{i=1}^k A_i=A$$, and
• $A_i\cap A_j=\emptyset$ for all $i,j$, $1\leq i<j\leq k$.

Each subset $A_i$ is called a block of the partition.

An equivalence relation $R$ on a set $A$ partitions the set into equivalence classes.

An equivalence class is a subset of $A$ so that every pair of elements from the class is in the relation, while any pair of an element in the class and an element outside the class is not in the relation.

Every element in $A$ is in exactly one of the equivalence classes.

Notation: $[x]$ denotes the equivalence class of which $x$ is a member. Note that $[x]=[y]$ if and only if $xRy$.

Example:

Let $R$ be the relation on the set $\{ 0,1,\dots, 20\}$ where $xRy$ if $x$ and $y$, divided by 5, have the same remainder.

Equivalence classes:

$\{ 0,5,10,15,20\}$, $\{ 1,6,11,16\}$, $\{ 2,7,12,17\}$, $\{ 3,,8,13,18\}$, $\{ 4,9,14,19\}$.