CSCE 222 Lecture 16

« previous | Wednesday, March 2, 2011 | next »

Partial Orderings

These relations must work for all comparable numbers

Antisymmetry

Relation R on a set A is called antisymmetric iff ${}_{a}R_{b}$ and ${}_{b}R_{a}$ implies that $a=b$

Examples:

• ≤ operator on integers is antisymmetric
• = operator on integers is antisymmetric

Partial Order

Relation R on S is a partial order iff it is reflexive, antisymmetric, and transitive.

Examples:

• ≤ operator on integers is a partial order
• ⊆ operator on $P(S)$ is a partial order

Comparability

We call two elements $a$ and $b$ of a partially ordered set $(S,\leq )$ comparable iff a ≤ b or b ≤ a

Examples:

• The set $(P(\mathbb {Z} ),\subseteq )$ contains {1, 2} and {1, 3}, but they are not subsets of each other, so they are incomparable.
• $(\mathbb {N} ,|)$ (a "divides" b implies b mod a = 0) is:
  • reflexive (every number divides itself)
  • transitive (if a is a factor of b and b is a factor of c, then a is a factor of c)
  • antisymmetric (if a divides b and b divides a, then a and b must be equal)
• $(\mathbb {Z} ,|)$ is not a partial order since it is not antisymmetric (1 divides −1 and −1 divides 1, but 1 ≠ −1)

Hasse Diagrams

Sample Hasse diagram for partial order $(\{2,4,5,10,12,20,25\},|\})$

A set of lines connecting all numbers that satisfy a partial order relations:

• Remove all self/reflexive satisfying loops
• Any upward-chained connecting lines imply transitivity
• All edges "point" upward

Maximal/Minimal

Let $(S,\leq )$ be a partially ordered set.

A number $b\in S$ is called maximal iff it is the largest element.

A number $a\in S$ is called minimal iff it is the smallest element.

Example

$(\{2,4,5,10,12,20,25\},|)$: in a Hasse diagram (see image at right), 12, 20, 25 are maximal elemets; 2, 5 are minimal.