2.2 Ordered Sets

 < Free Open Study > 



2.2 Ordered Sets

2.2.1 Definition

A binary relation R on a set S is reflexive if R relates every element of S to itselfthat is, s R s (or (s,s) Î R) for all s Î S. R is symmetric if s R t implies t R s, for all s and t in S. R is transitive if s R t and t R u together imply s R u. R is antisymmetric if s R t and t R s together imply that s = t.

2.2.2 Definition

A reflexive and transitive relation R on a set S is called a preorder on S. (When we speak of "a preordered set S," we always have in mind some particular preorder R on S.) Preorders are usually written using symbols like or . We write s < t ("s is strictly less than t") to mean s t s t.

A preorder (on a set S) that is also antisymmetric is called a partial order on S. A partial order is called a total order if it also has the property that, for each s and t in S, either s t or t s.

2.2.3 Definition

Suppose that is a partial order on a set S and s and t are elements of S. An element j Î S is said to be a join (or least upper bound) of s and t if

  1. s j and t j, and

  2. for any element k Î S with s k and t k, we have j k.

Similarly, an element m Î S is said to be a meet (or greatest lower bound) of s and t if

  1. m s and m t, and

  2. for any element n Î S with n s and n t, we have n m.

2.2.4 Definition

A reflexive, transitive, and symmetric relation on a set S is called an equivalence on S.

2.2.5 Definition

Suppose R is a binary relation on a set S. The reflexive closure of R is the smallest reflexive relation R that contains R. ("Smallest" in the sense that if R is some other reflexive relation that contains all the pairs in R, then we have R R.) Similarly, the transitive closure of R is the smallest transitive relation R that contains R. The transitive closure of R is often written R+. The reflexive and transitive closure of R is the smallest reflexive and transitive relation that contains R. It is often written R*.

2.2.6 Exercise [⋆⋆ ]

Suppose we are given a relation R on a set S. Define the relation R as follows:

  • R = R {(s, s) | s Î S}.

That is, R contains all the pairs in R plus all pairs of the form (s, s). Show that R is the reflexive closure of R.

2.2.7 Exercise [⋆⋆, ]

Here is a more constructive definition of the transitive closure of a relation R. First, we define the following sequence of sets of pairs:

  •  

    R0

    =

    R

    Ri+1

    =

    Ri {(s, u) | for some t, (s, t) Î Ri and (t, u) Î Ri}

That is, we construct each Ri+1 by adding to Ri all the pairs that can be obtained by "one step of transitivity" from pairs already in Ri. Finally, define the relation R+ as the union of all the Ri:

Show that this R+ is really the transitive closure of Ri.e., that it satisfies the conditions given in Definition 2.2.5.

2.2.8 Exercise [⋆⋆, ]

Suppose R is a binary relation on a set S and P is a predicate on S that is preserved by R. Show that P is also preserved by R*.

2.2.9 Definition

Suppose we have a preorder on a set S. A decreasing chain in is a sequence s1, s2, s3, ... of elements of S such that each member of the sequence is strictly less than its predecessor: si+1 < si for every i. (Chains can be either finite or infinite, but we are more interested in infinite ones, as in the next definition.)

2.2.10 Definition

Suppose we have a set S with a preorder . We say that is well founded if it contains no infinite decreasing chains. For example, the usual order on the natural numbers, with 0 < 1 < 2 < 3 < ... is well founded, but the same order on the integers, ... < -3 < -2 < -1 < 0 < 1 < 2 < 3 < ... is not. We sometimes omit mentioning explicitly and simply speak of S as a well-founded set.



 < Free Open Study > 



Types and Programming Languages
Types and Programming Languages
ISBN: 0262162091
EAN: 2147483647
Year: 2002
Pages: 262

flylib.com © 2008-2017.
If you may any questions please contact us: flylib@qtcs.net