INFS3450 Topics

Reflexive and Strict Partial Orders

A relation R on a set X is called a strict partial order if R is irreflexive, asymmetric, and transitive.

Since the relation R defined on the set of tables in a relational database by

(x,y) Î R if x must be created before y

is irreflexive, asymmetric and transitive, R is a strict partial order.

A relation R on a set X is called a reflexive partial order if R is reflexive, antisymmetric, and transitive.

Since the relation R defined on the positive integers by

(x,y) Î R if x divides y (evenly)

is reflexive, antisymmetric and transitive, R is a reflexive partial order.

If R is a partial order on a set X, the notation x ≼ y is sometimes used to indicate that (x,y) Î R. This suggests that we are interpreting the relation as an ordering of the elements in X.

Suppose that R is a partial order on a set X. If x,y Î X and either x ≼ y or y ≼ x, we say that x and y are comparable. If x, y Î X and x ⌐≼ y and y ⌐≼ x, we say that x and y are incomparable. If every pair of elements in X is comparable, we call R a partial order. The less than or equals relations on the positive integers is a total order since, if x and y are integers, either x ≤ y or y ≥ x. The reason for the term “partial order” is that in general some elements in X may be incomparable.

RMU C&IS INFS 3450