# CSCE 222 Lecture 16

Jump to navigation
Jump to search

« 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 and implies that

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 is a partial order

### Comparability

We call two elements and of a partially ordered set comparable iff *a* ≤ *b* or *b* ≤ *a*

Examples:

- The set contains {1, 2} and {1, 3}, but they are not subsets of each other, so they are incomparable.
- (
*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)

- is not a partial order since it is not antisymmetric (1 divides −1 and −1 divides 1, but 1 ≠ −1)

## Hasse Diagrams

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 be a partially ordered set.

A number is called maximal iff it is the largest element.

A number is called minimal iff it is the smallest element.

#### Example

: in a Hasse diagram (see image at right), 12, 20, 25 are maximal elemets; 2, 5 are minimal.