Partial Order Relations

We begin with a little review (as generalized from Fletcher R. Norris, Discrete Structures: an introduction to mathematics for computer science, Prentice-Hall, 1985):

  1. R is said to be reflexive: " a Î A, a R a. This means that every element in the universe of discourse, set A, is related to itself through R. Examples are:
    a) Is equal to.
    b) Is parallel to.
    c) Is the same color as.
    d) £
    e) ³
    f) Í
    In the main diagonal of an adjacency matrix M there would be all 1’s.
  2. A relation is symmetric: a R b ® b R a. Examples are:
    a) Is perpendicular to.
    b) Has a border in common with.
    c) Is the same height as.
    d) Is a sibling of.
    e) Is equal to.
    For every value not in the main diagonal of M there is the same value reflected on the other side of the main diagonal.
  3. A relation is transitive: (a R b Ù b R c) ® (a R c). Whenever two elements are linked together through a third element, they are linked directly. Examples are:
    a) Í
    b) Ì
    c) Is equal to.
    d) Is a multiple of.
    e) Is a divisor of.
    f) Is due north of (except when already on the North Pole).
    g) Is an ancestor (or descendant) of.
    h) <
    i) £

    4. Now we learn two more relations:

  4. A relation R is said to be irreflexive if no element of A is related to itself. " a Î A, a R a, that is if no element of A is related to itself. Examples are:
    a) Ì
    b) >
    c) Is taller than.
    d) Is the sister of.
    e) Is the father of.
  5. The antisymmetric property of relations states that: If for some a and b we have a R b and also b R a, then a = b. This relation implies equality for any two elements for which the relation holds in both directions. Antisymmetry is met vacuously whenever relations hold in only one direction.
    Symbolically: (a R b Ù b R a) ® (a = b). Examples are:
    a) Is a subset of. (For example, if A Í B and B Í A, then A = B.)
    b) £
    c) ³

In isolation, properties of relations, in general, do not carry much information about the structure of a set. However, they may be grouped together in such ways to develop useful classifications. We have already studied one of these groupings, equivalence relations. Another grouping that has had considerable impact within computer science is known as a partial order.

Definition: Let R be a binary relation defined on a set A. R is a partial order relation if, and only if, R is reflexive, antisymmetric, and transitive.

From our lists above two relations stand out as partial order relations: Í , and £ . The £ symbol is so prototypical of a partial order relation that a form of it, p , has been used to refer to a general partial order relation.

Some relations are partial order relations only when the size of the set is suitable. Consider the "divides" relation on the set of positive integers (the natural numbers N ), certainly reflexive, antisymmetric, and transitive. But the same relation applied to the set of integers Z, is not antisymmetric since –2 | 2 and 2 | -2 but –2 ¹ 2.

Lexicography, according to Webster, is the principles and practices of dictionary making. Theorem 8.5.1 breaks lexicographic order down into a partial order relation.

Hasse diagrams (named after Helmut Hasse a twentieth-century German number theorist), take the partial order relation digraph and transforms it into a much simpler graph.

Example Consider the divisors of 30, the set of A = {1, 2, 3, 5, 6, 10, 15, 30}, with two binary operators meet = gcd (x, y) and join = lcm (x, y). The complement, xc, of an element is the quotient of 30 divided by x, where x Î A ={1, 2, …, 30}.

gcd (x, xc ) = 1 (1 is the zero element)

lcm (x, xc ) = 30 (30 is the unit element)

gcd (1, 30) = 1

lcm (1, 30) = 30

gcd (2, 15) = 1

lcm (2, 15) = 30

gcd (3, 10) = 1

lcm (3, 10) = 30

gcd (5, 6) = 1

lcm (5, 6) = 30

To create the Hasse diagram for the partial order relation R such that {(x, y) Î R « x divides y} on the set of A, we begin with the digraph ordered from the least element in R to the greatest element in R. To convert the digraph to a Hasse diagram proceed as follows:

  1. Remove all loops.
  2. Delete all the edges implied by the transitive property.
    {(1, 6,), (1, 10), (1, 15), (1, 30), (2, 30), (3, 30), (5, 30)}
  3. Arrange all edges to point upward, and delete all arrows.
    4.
Compare the above Hasse diagram to the one Example 10.5.7 which considers the subset relation on the power set of {a, b, c}, that is, for all sets U and V in P({a, b, c}),

U Í V « " x, x Î U ® x Î V.

Notice the similarity. All Boolean algebras on sets of a given size share the same Hasse diagram.

Recall from chapter 5, on Set Theory, what a Boolean Algebra is (p. 266). In propositional logic Ù , Ú , played the roles of meet '× ', and join '+', contradiction 'c' played the zero element and tautology 't' played the unit element. In set theory, for a set of subsets on a nonempty set S, È, and Ç, play +, and ×, while U and Æ play the roles of unit and zero, and complement plays negation.

Every Boolean algebra has defined on it a partial order relation.