Page 639 - Discrete Mathematics and Its Applications

618 9 / Relations

∗ 58. Each bead on a bracelet with three beads is either red, 61. Determine the number of different equivalence relations
white, or blue, as illustrated in the figure shown. on a set with three elements by listing them.
62. Determine the number of different equivalence relations
Bead 1 on a set with four elements by listing them.
Red
∗ 63. Do we necessarily get an equivalence relation when we
form the transitive closure of the symmetric closure of
the reflexive closure of a relation?
∗ 64. Do we necessarily get an equivalence relation when we
Bead 3 Bead 2
Blue White form the symmetric closure of the reflexive closure of the
transitive closure of a relation?
Define the relation R between bracelets as: (B 1 ,B 2 ),
where B 1 and B 2 are bracelets, belongs to R if and only 65. Suppose we use Theorem 2 to form a partition P from
an equivalence relation R. What is the equivalence rela-
if B 2 can be obtained from B 1 by rotating it or rotating it
tion R that results if we use Theorem 2 again to form an

and then reflecting it.
equivalence relation from P?
a) Show that R is an equivalence relation.
66. Suppose we use Theorem 2 to form an equivalence rela-
b) What are the equivalence classes of R?
tion R from a partition P. What is the partition P that
∗ 59. Let R be the relation on the set of all colorings of the 2 × 2 results if we use Theorem 2 again to form a partition
checkerboard where each of the four squares is colored from R?
either red or blue so that (C 1 ,C 2 ), where C 1 and C 2 are 67. Devise an algorithm to find the smallest equivalence re-
2 × 2 checkerboards with each of their four squares col- lation containing a given relation.
ored blue or red, belongs to R if and only if C 2 can be
∗ 68. Let p(n) denote the number of different equivalence
obtained from C 1 either by rotating the checkerboard or
by rotating it and then reflecting it. relations on a set with n elements (and by Theo-
rem 2 the number of partitions of a set with n ele-
a) Show that R is an equivalence relation.
ments). Show that p(n) satisfies the recurrence relation
b) What are the equivalence classes of R? n−1
p(n) = j=0 C(n − 1, j)p(n − j − 1) and the initial
60. a) Let R be the relation on the set of functions from Z + condition p(0) = 1. (Note: The numbers p(n) are called
+
to Z such that (f, g) belongs to R if and only if f Bell numbers after the American mathematician E. T.
is (g) (see Section 3.2). Show that R is an equiva- Bell.)
lence relation. 69. Use Exercise 68 to find the number of different equiv-
b) Describe the equivalence class containing f (n) = n 2 alence relations on a set with n elements, where n is a
for the equivalence relation of part (a). positive integer not exceeding 10.
9.6 Partial Orderings

Introduction

We often use relations to order some or all of the elements of sets. For instance, we order words
using the relation containing pairs of words (x, y), where x comes before y in the dictionary.
We schedule projects using the relation consisting of pairs (x, y), where x and y are tasks in
a project such that x must be completed before y begins. We order the set of integers using
the relation containing the pairs (x, y), where x is less than y. When we add all of the pairs
of the form (x, x) to these relations, we obtain a relation that is reflexive, antisymmetric, and
transitive. These are properties that characterize relations used to order the elements of sets.

DEFINITION 1 A relation R on a set S is called a partial ordering or partial order if it is reflexive, antisym-
metric, and transitive. A set S together with a partial ordering R is called a partially ordered
set,or poset, and is denoted by (S, R). Members of S are called elements of the poset.

We give examples of posets in Examples 1–3.

EXAMPLE 1 Show that the “greater than or equal” relation (≥) is a partial ordering on the set of integers.