Chapter Review 217
the same number of places to the right or to the left. Prove that this relation is an equiv-
alence relation. How many equivalence classes are there, and what are the members
of each equivalence class? Can you conjecture how many equivalence classes there
would be if there were n friends?
- Let R be a reflexive relation on a set A. R is an equivalence relation if and only if
(a, b), (a, c) E R implies that (b, c) e R.
- Let T be a relation on A, and let R be a reflexive and transitive relation on A. Prove that
T is an equivalence relation on A provided (a, b) e T if and only if (a, b), (b, a) E R.
- Let R 1 be a partial order on S and R 2 a partial order on T. For (si, tI), (s2, t 2 ) E S x T,
define (sl, t 1 ) R 3 (s2, t 2 ) if and only if sl R 1 s2 andt 1 R 2 t 2 .Prove that R 3 is a partial
order.
- Let X = { 1, 2, 3, 41, and let P (X) be the power set of X. Let P (X) be partially ordered
by set inclusion. Find an embedding of this partial ordering into a total ordering.
3.12.4 Using Discrete Mathematics in Computer Science
Definition. An upper bound of two elements in a partial order is an element that is
greater than both of the elements. A least upper bound is an upper bound that is smaller
than any other upper bound. A lower bound of two elements in a partial order is an element
that is less than both of the elements. A greatest lower bound is a lower bound that is
larger than any other lower bound.
- Find the least upper bound and the greatest lower bound of each pair of elements in the
partial order represented by the following diagram:
h
f g
e
d
bc
a
- Find the least upper bound and the greatest lower bound of each pair of elements in the
partial order represented by the following diagram:
f g
e
d
bc
a
