ads Basic Definitions

Section 6.1 Basic Definitions

In Chapter 1 we introduced the concept of the Cartesian product of sets. Let’s assume that a person owns three shirts and two pairs of slacks. More precisely, let

A = {blue shirt, tan shirt, mint green shirt}

and

B = {grey slacks, tan slacks} .

Then

A \times B

is the set of all six possible combinations of shirts and slacks that the individual could wear. However, an individual may wish to restrict himself or herself to combinations which are color coordinated, or “related.” This may not be all possible pairs in

A \times B

but will certainly be a subset of

A \times B .

For example, one such subset may be

{(blue shirt, grey slacks), (blue shirt, tan slacks), (mint green shirt, tan slacks)} .

🔗

Subsection 6.1.1 Relations between two sets

🔗

Definition 6.1.1. Relation.

🔗

Let

A

and

B

be sets. A relation from

A

into

B

is any subset of

A \times B .

Example 6.1.2. A simple example.

Let

A = {1, 2, 3}

and

B = {4, 5} .

Then

{(1, 4), (2, 4), (3, 5)}

is a relation from

A

into

B .

Of course, there are many others we could describe; 64, to be exact.

Example 6.1.3. Divisibility Example.

Let

A = {2, 3, 5, 6}

and define a relation

r

from

A

into

A

(a, b) \in r

if and only if

a

divides evenly into

b .

The set of pairs that qualify for membership is

r = {(2, 2), (3, 3), (5, 5), (6, 6), (2, 6), (3, 6)} .

🔗

Subsection 6.1.2 Relations on a Set

🔗

Definition 6.1.4. Relation on a Set.

🔗

A relation from a set

A

into itself is called a relation on

A .

🔗

The relation “divides” in Example 6.1.3 will appear throughout the book. Here is a general definition on the whole set of integers.

🔗

Definition 6.1.5. Divides.

🔗

Let

a, b \in Z,

a \neq 0 .

We say that

a

divides

b,

denoted

a ∣ b,

if and only if there exists an integer

k

such that

a k = b .

🔗

Be very careful in writing about the relation “divides.” The vertical line symbol use for this relation, if written carelessly, can look like division. While

a ∣ b

is either true or false,

a / b

is a number.

🔗

Based on the equation

a k = b,

we can say that

a | b

is equivalent to

k = \frac{b}{a},

a

divides evenly into

b .

In fact the “divides” is short for “divides evenly into.” You might find the equation

k = \frac{b}{a}

initially easier to understand, but in the long run we will find the equation

a k = b

more convenient.

🔗

Sometimes it is helpful to illustrate a relation with a graph. Consider Example 6.1.2. A graph of

r

can be drawn as in Figure 6.1.6. The arrows indicate that 1 is related to 4 under

r .

Also, 2 is related to 4 under

r,

and 3 is related to 5, while the upper arrow denotes that

r

is a relation from the whole set

A

into the set

B .

The graph of a relation. On the left, there is a set consisting of three points, 1, 2, and 3. On the right a set consisting of two points 4 and 5. Arrows corresponding to the ordered pairs (1,4), (2,4), and (3,5) connect the points in the two sets. — 🔗
Figure 6.1.6. The graph of a relation

🔗

A typical element in a relation

r

is an ordered pair

(x, y) .

In some cases,

r

can be described by actually listing the pairs which are in

r,

as in the previous examples. This may not be convenient if

r

is relatively large. Other notations are used with certain well-known relations. Consider the “less than or equal” relation on the real numbers. We could define it as a set of ordered pairs this way:

\leq= {(x, y) | x \leq y}

🔗

However, the notation

x \leq y

is clear and self-explanatory; it is a more natural, and hence preferred, notation to use than

(x, y) \in\leq .

🔗

Many of the relations we will work with “resemble” the relation

\leq,

x s y

is a common way to express the fact that

x

is related to

y

through the relation

s .

🔗

Relation Notation Let

s

be a relation from a set

A

into a set

B .

Then the fact that

(x, y) \in s

is frequently written

x s y .

🔗

Subsection 6.1.3 Composition of Relations

🔗

With

A = {2, 3, 5, 8},

B = {4, 6, 16},

and

C = {1, 4, 5, 7},

let

r

be the relation “divides,” from

A

into

B,

and let

s

be the relation

\leq

from

B

into

C .

r = {(2, 4), (2, 6), (2, 16), (3, 6), (8, 16)}

and

s = {(4, 4), (4, 5), (4, 7), (6, 7)} .

🔗

Notice that in Figure 6.1.8 that we can, for certain elements of

A,

go through elements in

B

to results in

C .

That is:

🔗

Table 6.1.7.

2 | 4 and 4 \leq 4

2 | 4 and 4 \leq 5

2 | 4 and 4 \leq 7

2 | 6 and 6 \leq 7

3 | 6 and 6 \leq 7

The graphs of two relations being composed. — 🔗
Figure 6.1.8. Relation Composition - a graphical view

🔗

Based on this observation, we can define a new relation, call it

r s,

from

A

into

C .

In order for

(a, c)

to be in

r s,

it must be possible to travel along a path in Figure 6.1.8 from

a

c .

In other words,

(a, c) \in r s

if and only if

(\exists b)_{B} (a r b and b s c) .

The name

r s

was chosen because it reminds us that this new relation was formed by the two previous relations

r

and

s .

The complete listing of all elements in

r s

{(2, 4), (2, 5), (2, 7), (3, 7)} .

We summarize in a definition.

🔗

Definition 6.1.9. Composition of Relations.

🔗

Let

r

be a relation from a set

A

into a set

B,

and let

s

be a relation from

B

into a set

C .

The composition of

r

with

s,

written

r s,

is the set of pairs of the form

(a, c) \in A \times C,

where

(a, c) \in r s

if and only if there exists

b \in B

such that

(a, b) \in r

and

(b, c) \in s .

🔗

Remark: A word of warning to those readers familiar with composition of functions. (For those who are not, disregard this remark. It will be repeated at an appropriate place in the next chapter.) As indicated above, the traditional way of describing a composition of two relations is

r s

where

r

is the first relation and

s

the second. However, function composition is traditionally expressed in the opposite order:

s \circ r,

where

r

is the first function and

s

is the second.

🔗

Exercises 6.1.4 Exercises

🔗

1.

🔗

For each of the following relations

r

defined on

P,

determine which of the given ordered pairs belong to

r

🔗

$x r y$ iff $x | y;$ (2, 3), (2, 4), (2, 8), (2, 17)
$x r y$ iff $x \leq y;$ (2, 3), (3, 2), (2, 4), (5, 8)
$x r y$ iff $y = x^{2}$ ; (1,1), (2, 3), (2, 4), (2, 6)

Answer.

$(2, 4), (2, 8)$
$(2, 3), (2, 4), (5, 8)$
$(1, 1), (2, 4)$

🔗

2.

🔗

The following relations are on

P = {0, 1, 2, \dots 8, 9} .

Let

A = {(9, 8), (9, 7), (6, 5), (6, 4), (3, 2), (3, 1)}

🔗

and

B = {((8, 6), (7, 6), (5, 3), (4, 3), (2, 0), (1, 0)} .

🔗

List all elements in $A B .$
List all elements in $B A .$
Illustrate $A B$ and $B A$ via a diagraph.
In one version of the game of nim players A and B take turns removing one or two stones from a pile. The player who manages to remove the last stone wins. Explain how these two relations describe the winning moves for B if A plays first with nine stones in the pile at the start of the game.

🔗

3.

🔗

Let

A = {1, 2, 3, 4, 5}

and define

r

A

x r y

iff

x + 1 = y .

We define

r^{2} = r r

and

r^{3} = r^{2} r .

Find:

$r$
$r^{2}$
$r^{3}$

Answer.

$r = {(1, 2), (2, 3), (3, 4), (4, 5)}$
$r^{2} = {(1, 3), (2, 4), (3, 5)} = {(x, y) : y = x + 2, x, y \in A}$
$r^{3} = {(1, 4), (2, 5)} = {(x, y) : y = x + 3, x, y \in A}$

🔗

4.

🔗

Given

s

and

t,

relations on

Z,

s = {(1, n) : n \in Z}

and

t = {(n, 1) : n \in Z},

what are

s t

and

t s ?

Hint: Even when a relation involves infinite sets, you can often get insights into them by drawing partial graphs.

🔗

5.

🔗

Let

ρ

be the relation on the power set,

P (S),

of a finite set

S

of cardinality

n

defined

ρ

(A, B) \in ρ

iff

A \cap B = \emptyset .

🔗

Consider the specific case $n = 3,$ and determine the cardinality of the set $ρ .$
What is the cardinality of $ρ$ for an arbitrary $n ?$ Express your answer in terms of $n .$ (Hint: There are three places that each element of S can go in building an element of $ρ .$ )

Answer.

When $n = 3,$ there are 27 pairs in the relation.
Imagine building a pair of disjoint subsets of $S .$ For each element of $S$ there are three places that it can go: into the first set of the ordered pair, into the second set, or into neither set. Therefore the number of pairs in the relation is $3^{n},$ by the product rule.

🔗

6.

🔗

Consider the two relations on people:

M,

where

a M b

a

’s mother is

b;

and

S,

where

a S b

a

and

b

are siblings. Describe, in words, the two relations

M S

and

S M

in simple English terms.

🔗

7.

🔗

Let

r_{1},

r_{2},

and

r_{3}

be relations on any set

A .

Prove that if

r_{1} \subseteq r_{2}

then

r_{1} r_{3} \subseteq r_{2} r_{3} .

Solution.

Assume

(x, y) \in r_{1} r_{3} .

This implies that there exist

z \in A

such that

(x, z) \in r_{1}

and

(z, y) \in r_{3} .

We are given that

r_{1} \subseteq r_{2},

which implies that

(x, z) \in r_{2} .

Combining this with

(z, y) \in r_{3}

implies that

(x, y) \in r_{2} r_{3},

which proves that

r_{1} r_{3} \subseteq r_{2} r_{3} .

You have attempted 1 of 1 activities on this page.

Prev Top Next