Relations on Sets

Section 8.1 Relations on Sets

We first saw relations in Section 1.3. In this section we revisit the definition, look at several examples, and connect the idea of a function to a relation.

🔗

Definition 8.1.1.

A relation,

R,

A \times B,

is a set of ordered pairs in

A \times B .

🔗

Simply put, a relation is just a subset,

R,

A \times B .

🔗

We often use the notation

x R y

to mean “

x

is related to

y .

” In particular,

(x, y) \in R

if and only if

x R y .

🔗

Example 8.1.2. Relation Defined by a Set.

Let

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

B = {1, 3, 5}

define the relation on

A \times B

R = {(1, 1), (1, 5), (3, 5), (2, 1), (4, 3)} .

Then

1 R 1, 3 R 5, 4 R 3,

for example. But 3 is not related to 1, for example.

Example 8.1.3. Relation Defined by Less Than.

We can also define relations with familiar mathematical relationships.

Let

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

B = {1, 3, 5}

define the relation on

A \times B

x R y \Leftrightarrow x < y .

Find the set of ordered pairs for

R .

Answer.

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

As with functions, we can draw an arrow diagram from

A

B

representing the relationship. We have an arrow from

a

b

a R b,

(a, b) \in R .

🔗

The arrow diagram for the relation “a< b”, given in Example 8.1.2 is given in the following figure.

🔗

Figure 8.1.4. Arrow diagram for less than.
🔗

A function is a relation. Let

f : A \to B, f (a) = b .

Then define

R

🔗

(a, b) \in R \Leftrightarrow f (a) = b .

🔗

We can see that Example 8.1.3 is not a function since an element of

A

can map to two different elements of

B :

(1, 3), (1, 5) .

🔗

Example 8.1.5. A Function as a Relation.

Let

f : Z \to Z

be given by

f (n) = n^{2} .

Let

F

be the relation given by

f :

(a, b) \in F \Leftrightarrow f (a) = b .

True or false:

(1, 1) \in F .

Answer 1.

True

True or false:

(3, 9) \in F .

Answer 2.

True

True or false:

(9, 3) \in F .

Answer 3.

False

True or false:

(- 2, 4) \in F .

Answer 4.

True

True or false:

(2, - 4) \in F .

Answer 5.

False

True or false:

(1, 3) \in F .

Answer 6.

False

Determining if a Relation Is a Function.

A relation is a function if the following two properties hold:

🔗

For every $a \in A$ there must be a $b \in B$ related to $a .$
Each $a \in A$ can only be related in one $b \in B .$

🔗

We can translate this idea into the ordered pair notation:

🔗

For every $a \in A$ there must be a $b \in B$ such that $(a, b) \in F .$
If $(a, b) \in F$ and $(a, c) \in F$ then $b = c .$

🔗

Definition 8.1.6.

Let

R

be a relation on

A \times B .

The inverse relation,

R^{- 1},

B \times A

🔗

R^{- 1} = {(b, a) \in B \times A : (a, b) \in R} .

🔗

In other words,

(a, b) \in R

if and only if

(b, a) \in R^{- 1} .

🔗

Example 8.1.7. Inverse Relation.

Let

R = {(1, 3), (1, 5), (2, 3), (2, 5), (3, 5), (4, 5)} .

This is the relation in Example 8.1.3.

Find

R^{- 1} .

Answer.

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

Activity 8.1.1.

Let

A = {1, 2, 3, 4}

and

B = {0, 1} .

Define the relation from

A

B

🔗

(x, y) \in R ⟺ x - y is even .

🔗

(a)

Find the set of ordered pairs given by this relation.

🔗

(b)

Draw the arrow diagram for this relation.

🔗

(c)

Give the inverse relation for

R .

Remember, it is a set of ordered pairs.

🔗

(d)

Is the relation

R

a function?

🔗

Definition 8.1.8.

A relation on

A

is a relation on

A \times A .

We also say a relation from

A

A .

🔗

We can use a directed graph to represent a relation on

A .

We label the vertices with the elements from

A

and draw and arrow from

a

b

a R b .

Note, if

a R a,

then we get a “loop” at

a .

🔗

Example 8.1.9. Directed Graph of a Relation.

Let

A = {1, 2, 3} .

Let

R = {(x, y) : x < y} .

Then we get the following directed graph for

R .

Figure 8.1.10. Directed graph for less than.

If we now want the relations for less than or equal to,

R = {(x, y) : x \leq y},

we have the following directed graph.

Figure 8.1.11. Directed graph for less than or equal.

Activity 8.1.2.

Let

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

Define the relation on

A

🔗

(x, y) \in R ⟺ 3 ∣ (x - y) .

🔗

(a)

Find the set of ordered pairs given by this relation.

🔗

(b)

Draw the directed graph for this relation.

🔗

(c)

Give the inverse relation for

R .

Remember, it is a set of ordered pairs.

🔗

(d)

Is the relation

R

a function?

🔗

Activity 8.1.3.

Let

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

Define the relation on

A

🔗

(x, y) \in R ⟺ x divides y .

🔗

(a)

Find the set of ordered pairs given by this relation.

🔗

(b)

Draw the directed graph for this relation.

🔗

(c)

Give the inverse relation for

R .

🔗

Hint.

Remember, it is a set of ordered pairs.

🔗

(d)

Is the relation

R

a function?

🔗

Reading Questions Check Your Understanding

1.

Let

A = {1, 2, 3}, B = {2, 4, 6, 8} .

Determine which of the ordered pairs are in the relation on

A \times B

given by

🔗

a R b \Leftrightarrow a \geq b

🔗

$(2, 2)$
Correct, $2 \geq 2$
$(3, 2)$
Correct, $3 \geq 2$
$(2, 6)$
Is $2 \geq 6 ?$
$(4, 2)$
Is 4 in $A ?$

🔗

2.

Let

C = {0, 1} .

Determine which of the ordered pairs are in the relation for the relation on

C

given by

🔗

a R b \Leftrightarrow a + b is even

🔗

$(0, 0)$
Correct, $0 + 0 = 0,$ which is even.
$(1, 1)$
Correct, $1 + 1 = 2,$ which is even.
$(0, 1)$
Is $0 + 1$ even?
$(1, 3)$
Is 3 in $C ?$

🔗

3.

Let

A = {1, 2, 3}, B = {2, 4, 6, 8} .

True or false: the relation on

A \times B

given by

🔗

a R b \Leftrightarrow a \geq b

is a function from

A

B .

🔗

True.
1 does not map to anything in $B .$
False.
1 does not map to anything in $B .$

🔗

4.

Let

C = {0, 1} .

True or false: the relation on

C

given by

🔗

a R b \Leftrightarrow a + b is even

is a function on

C .

🔗

True.
False.

🔗

5.

Let

B = {2, 4, 6, 8} .

Give the ordered pairs for the relation on

B

given by

🔗

a R b \Leftrightarrow a ∣ b .

🔗

Hint.

Your answer should have 8 ordered pairs.

🔗

6.

Give the ordered pairs for the inverse relation,

R^{- 1}

B

when

R

is given by

🔗

a R b \Leftrightarrow a ∣ b .

🔗

Hint.

Your answer should have 8 ordered pairs.

🔗

Exercises Exercises

1.

Define the congruence modulo 3 relation,

T,

Z

🔗

m T n ⟺ 3 ∣ (m - n) .

🔗

Is $10 T 1 ?$ Is $1 T 10 ?$ Is $(2, 2) \in T ?$ Is $(8, 1) \in T ?$
List five integers $n$ such that $n T 0 .$
List five integers $n$ such that $n T 1 .$
List five integers $n$ such that $n T 2 .$

🔗

2.

Let

X = {a, b, c}

and

P (X)

be the power set of

X .

Define the relation

R

P (X)

🔗

A R B ⟺ A has the same number of elements as B .

🔗

Is ${a, b} R {b, c} ?$
Is ${a} R {a, b} ?$
Is ${c} R {b} ?$

🔗

3.

Define the relation,

S,

Z

🔗

m S n ⟺ 5 ∣ (m^{2} - n^{2}) .

🔗

Is $1 S (- 9) ?$
Is $2 S 13 ?$
Is $2 S (- 8) ?$
Is $(- 8) S 2 ?$

🔗

4.

Let

A = {3, 4, 5}

and

B = {4, 5, 6}

and let

R

be the “less than” relation. That is, for all

(x, y) \in A \times B,

🔗

x R y ⟺ x < y .

🔗

Find the set of ordered pairs in $R .$
Find the set of ordered pairs in $R^{- 1} .$

🔗

5.

Let

A = {3, 4, 5}

and

B = {4, 5, 6}

and let

S

be the “divides” relation. That is, for all

(x, y) \in A \times B,

🔗

x S y ⟺ x ∣ y .

🔗

Find the set of ordered pairs in $S .$
Find the set of ordered pairs in $S^{- 1} .$

🔗

6.

Let

A = {a, b, c, d} .

Define the relation

R

A

🔗

R = {(a, b), (a, c), (b, c), (d, d)} .

Draw the directed graph for

R .

🔗

7.

Let

A = {2, 3, 4, 5, 6, 7, 8} .

Define the relation

S

A

🔗

x S y ⟺ x ∣ y .

Draw the directed graph for

S .

🔗

8.

Let

A = {2, 3, 4, 5, 6, 7, 8} .

Define the relation

T

A

🔗

x T y ⟺ 3 ∣ (x - y) .

Draw the directed graph for

T .

🔗

You have attempted 1 of 7 activities on this page.

🔗

Prev Top Next