| < Free Open Study > |
|
A binary relation R on a set S is reflexive if R relates every element of S to itself—that 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.
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.
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
s ≤ j and t ≤ j, and
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
m ≤ s and m ≤ t, and
for any element n Î S with n ≤ s and n ≤ t, we have n ≤ m.
A reflexive, transitive, and symmetric relation on a set S is called an equivalence on S.
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*.
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.
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 R—i.e., that it satisfies the conditions given in Definition 2.2.5.
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*.
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.)
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 > |
|