Study Guides for Discrete Mathematics

Section 6.6 - Partial Orderings

Members of the underlying set of an equivalence relation may usually be compared as being equal or not equal. Members of a partially ordered set (poset) may be compared in a more linear fashion. For example, two integers may be compared to determine which is larger. Often members of a arbitrary poset are not comparable.

The symbol used to indicate comparison in a poset is £ . Keep in mind that the symbol does not necessarily have anything to do with "less than or equal to".

 

Example:

Let a relation, R, be defined on the positive integers such that aRb iff a divides b. "divides" defines a partial order on the integers. Note some important characteristics.
    1. Some integers are comparable and some are not. 2 | 4, therefore 2 £ 4. However 2 and 5 are not comparable.
    2. The relation is reflexive. Obviously a | a.
    3. The relation is antisymmetric. I.e. if a £ b and b £ a then a = b. Obviously if a divides b and b divides a then a and b must be the same number.
    4. The relation is transitive. I.e. if a £ b and b £ c then a £ c. For example, 2 divides 4 and 4 divides 8, therefore 2 divides 8.

The above example leads us directly to the definition of a partially ordered set.

A relation R on a set S is called a partially ordered set (poset) if it is

    1. reflexive
    2. antisymmetric and
    3. transitive.

For some posets all elements are comparable. For example, as stated earlier, one may compare any two integers to determine which is larger.

If S is a poset such that any two elements are comparable then S is a totally ordered set.

If S is a totally ordered set such that every nonempty subset has a least element then S is well ordered.

 

Example:

The positive integers with the standard "<=" ordering is well ordered since every subset has a least element.

Example:

The integers with the standard "<=" ordering is not well ordered. To see this, let E be the subset comprised of all even integers (positive and negative). E has no least element.

Lexicographic Order

 Oftentimes the elements under consideration are not atomic. I.e. they may have ordered components. For example, the words in a dictionary are strings of characters. Points on the two dimensional plane are normally represented as ordered pairs such as (1, 2) or (-3, 1.5). The height of a person is often expressed in feet and inches (5' 4" or 6" 2"). In all of the above examples the elements under consideration have more than one component. And, unlike the elements of a set, the order of the components is important. The word "tin" is not the same as the word "nit". The point (-1, 2) is different from the point (2, -1). And having a height of 5' 7" is certainly different than having a height of 7' 5".

A lexicographic ordering of multi-dimensional objects as given above is often natural and useful. In a lexicographic ordering elements are first sorted by their first component, then their second, and so on. So, for example, all of the words beginning with A appear first in the dictionary. For those words that begin with 'A', those beginning with 'AA' (aardvark) come before those beginning with 'AB' (abalone). Similarly for the heights of people. All those whose height has a first component of 6 (i.e. those who are 6 ft. tall or taller) are taller than those whose first component is 5. Among those whose first height component is 6, we then order by the second height component (inches).

 

Hasse Diagrams

 

Maximal and Minimal Elements

Maximal, minimal, greatest, least, least upper bound, greatest lower bound

 

Lattices

 

Topological Sorting