Page 594 - Discrete Mathematics and Its Applications

CH A P TER

9 Relations

9.1 Relations and elationships between elements of sets occur in many contexts. Every day we deal with
Their Rrelationships such as those between a business and its telephone number, an employee
Properties and his or her salary, a person and a relative, and so on. In mathematics we study relationships
such as those between a positive integer and one that it divides, an integer and one that it is
9.2 n-ary Relations congruent to modulo 5, a real number and one that is larger than it, a real number x and the
and Their value f(x) where f is a function, and so on. Relationships such as that between a program and
Applications
a variable it uses, and that between a computer language and a valid statement in this language
9.3 Representing often arise in computer science.
Relations Relationships between elements of sets are represented using the structure called a relation,
which is just a subset of the Cartesian product of the sets. Relations can be used to solve problems
9.4 Closures of such as determining which pairs of cities are linked by airline flights in a network, finding a
Relations
viable order for the different phases of a complicated project, or producing a useful way to store
9.5 Equivalence information in computer databases.
Relations In some computer languages, only the first 31 characters of the name of a variable matter.
The relation consisting of ordered pairs of strings where the first string has the same initial
9.6 Partial
31 characters as the second string is an example of a special type of relation, known as an
Orderings
equivalence relation. Equivalence relations arise throughout mathematics and computer science.
We will study equivalence relations, and other special types of relations, in this chapter.

9.1 Relations and Their Properties

Introduction

The most direct way to express a relationship between elements of two sets is to use ordered pairs
made up of two related elements. For this reason, sets of ordered pairs are called binary relations.
In this section we introduce the basic terminology used to describe binary relations. Later in this
chapter we will use relations to solve problems involving communications networks, project
scheduling, and identifying elements in sets with common properties.

DEFINITION 1 Let A and B be sets. A binary relation from A to B is a subset of A × B.

In other words, a binary relation from A to B is a set R of ordered pairs where the first element
of each ordered pair comes from A and the second element comes from B. We use the notation
aRb to denote that (a, b) ∈ R and a R b to denote that (a, b) /∈ R. Moreover, when (a, b)
belongs to R, a is said to be related to b by R.
Binary relations represent relationships between the elements of two sets. We will introduce
n-ary relations, which express relationships among elements of more than two sets, later in this
chapter. We will omit the word binary when there is no danger of confusion.
Examples 1–3 illustrate the notion of a relation.

EXAMPLE 1 Let A be the set of students in your school, and let B be the set of courses. Let R be
the relation that consists of those pairs (a, b), where a is a student enrolled in course b.
For instance, if Jason Goodfriend and Deborah Sherman are enrolled in CS518, the pairs

573