Lecture 5

Relations
Objectives
By the end of this lecture, the student must be able to
By the end of this lecture the student must be able to
 Define relations between elements of the same sets
 Identify equivalence relations
 Describe the reflexive, transitive and symmetric
properties of relations
 Perform partition of sets

Key Terms
relation Equivalence Symmetry
relation
Transitive reflexive Equivalence
Class
Partition
______________________________________________________

Introduction
It also happens in language that one word can have multiple meanings. The
word ‘bat’ for example means a flat piece of wood used in some games, but
it also refers to a flying mammal.

In Lecture 3 we used the term relation when we were describing the

correspondence of elements between two sets. This time we use the same
term in another sense. It is now used to compare elements in the same set.
We claim that two elements in the same set are related if they exhibit a
specified property.

We learn of a particular type of relation called equivalence relation, and its

reflexive, symmetric and transitive properties. We learn how to partition a
set into equivalence classes, where elements in the same class have an
equivalence relation.
Section 5.1 Relation Between Members of a Set
Let , be elements in the same set . We state that there is a relation
between and if these elements obey a specified property. The notation is
. The relation needs to be defined.

Let us explain this concept using an example.

Example 5.1:
Consider the set . For any , ∈ we say ≤ if has a value less or
equal to the value of . The familiar symbol " ≤ " is used to describe the
relation between elements of the same set .

Example 5.2:
Consider the set . For any , ∈ let mean | | is an odd
number.Hence 3 8, (there is the specified relation between 3 and 8). But
we cannot claim 3 9, because the specified relation does not hold.

Example 5.3:
Let( , ), ( , ) ∈ . Define ( , ) ( , ) to mean 2 =2 . Then
(5,1) (4.5, 0)but (5, 1) (5, 0).

Define a relation on by ~ if + 2 is divisible by three. Check

? if the following hold: (i) 2 ~ 11, (ii) 7 ~ 8 (iii) 6 ~ 14.

5.1.1: Properties of Relations

Consider a set , , , ∈ and a relation between elements of set denoted
as .

The reflexive property

The relation is said to be reflexive if for all ∈ , .

In Example 4.1 we have for all ∈ , ≤ . Hence the relation " ≤ " is
reflexive. However the relation" " in Example 5.2 is not reflexive, for | |
is not odd for any ∈ . Check if in Example 5.3 is reflexive or not.

The symmetric property

The relation is said to be symmetric if for all , ∈ , → .

In Example 5.1 we have for all , ∈ , ≤ → ≤ . Here the relation " ≤ "
is not symmetric. We show it by a counterexample. We have 2 ≤ 3. On the
other hand 3 ≤ 2 is not true.

The relation " " in example 5.2 is symmetric, for | | is odd implies
| | is odd for all , ∈ . Check for the symmetric property for is
Example 5.3.

The transitive property

The relation is said to be transitive if for all , , ∈ , and

implies .

In example 5.1 we have for all , , ∈ , ≤ and ≤ implies ≤ , which

is true. Hence the relation " ≤ " is transitive.

On the other hand the relation " " in example 5.2 is not transitive. We
show it by giving an example where the property fails.Let = 2, = 3and
= 4. We have and but fails.

Check for the transitive property of the relation in Example 5.3.

Example 5.4:
For , ∈ 2 define to mean ∩ = . Check the reflexive, symmetric
and transitive properties of the relation.

Recall 2 means the power set of .

To check the symmetric property we use the commutativity of set
intersection.

→ ∩ =
→ ∩ =
→
As → , the relation is symmetric .

To check the reflexive property we need to show for all ∈ 2 . This is

only true if = . Hence in general the relation is NOT reflexive.

The relation is also not transitive for we can have ∩ = and ∩ = but
∩ ≠ as in the diagram below.
 Let ≈ be a relation of a set S. Complete each of the following
? de nitions:
(a) ≈is not re exive provided . . . .
(b) ≈is not symmetric provided . . . .
(c) ≈ is not transitive provided . . . .

5.1.2:Equivalence Relations
We start by defining a particular type of relation between elements of the
same set called the equivalence relation.

A relation between elements of the same set is called an

equivalence relation if it has the reflexive property, the
symmetric property and the transitive property.

For a relation to be an equivalence relation it must have all the three

properties: the reflexive, symmetric and transitive property. The relations ≤
and in Examples 5.1 and 5.2 are not equivalence relations because they
does not have all the three properties.

However the relation in Example 5.3 is an equivalence relation because it

exhibits all the three properties.

5.1.3: Equivalence Classes

Let us now define an equivalent class of an element in a set .

Let an equivalence relation be defined on a set . The

equivalence class of element ∈ is the set
[ ]={ ∈ : }
We denote the equivalence class of as [ ].
The equivalence class of element ∈ is the set of all elements in set for
which the relation holds. Note that [ ] is a subset of and that it
contains the element .

Example 5.4

For , ∈ define to mean | | = | |. You are given that is an

equivalence relation on . Determine [2], [5] and [ 5].

[2] = { ∈ : | | = |2|}
= { ∈ : | | = 2}
= { 2, 2}

Similarly you will find [ 5] = [5] = { 5, 5}.

Let = {1, 2, , 29, 30}. For all , ∈ , let ~ if | | is divisible

? by 4. Find the equivalence classes [3], [13]and [23].

Properties of Equivalent Classes

Let us state some properties of equivalent classes.

Theorem 5.1
Let be an equivalence relation on the set . If , ∈ and
then
(i) [ ] = [ ], and
(ii) ∈ [ ].

Proof:

[ ]={ ∈ : }
⇒ ∈[ ]

We now show that [ ] ⊂ [ ].

∈[ ]→
→ (by transitive property as )
→ ∈[ ]

Using similar argument we can show that [ ] ⊂ [ ]. Hence [ ] = [ ] .

Theorem 5.1 has the following implication expressed in the following
theorem.

Theorem 5.2
Let be an equivalence relation on the set . If , ∈ and
then
(i) [ ] [ ], and
(ii) [ ].

Partitions

A partition of a set is a collection of non empty subsets of , such that

each element belongs to at least one of the subsets, and the distinct subsets
are disjoint.

Let us put it formally.

The collection ={ , , } of subsets of is a partition of set

if

= ,

≠ for all
and
∩ = for ≠

Note:We sometimes call a set whose elements are sets as a collection of

sets, or a family of sets. By doing this we avoid using the confusing term
of set of sets, which however, would be a correct term.

Example 5.4
Consider the set = {1, 2, 3, … , 9, 10}

= {1,2,3}, {4, 6, }, {5,7,8,9} is a partition of set . There are many more

possible partitions of . Note that if is an infinite set, some of the elements
in the partition may be infinite sets too. It is also possible for a set to have
an infinite number of elements in its partition.

Example 5.5
The four suits of a deck of cards form a partition of the deck, because:
(i) every card belongs to one of the suits, (ii) no card belongs to more than
one suit, (iii) each suit has at least one card and (iv) the union of the four
suits form the entire deck of cards. (Note: you need to remove the Jokers!)

Example 5.6
Consider the set , the set of integers. ⁄3 = {3 , 3 + 1, 3 + 2}is a partition
of where

3 = { ∈ : = 3 , ∈ }, 3 +1={ ∈ : = 3 + 1, ∈ },
3 + 2 = { ∈ : = 3 + 2, ∈ }

In other terms

3 = {… , 9, 6, 3, 0, 3, 6, 9, … }
3 + 1 = {… , 8, 5, 1, 4, 7, 10, … }
3 + 2 = {… , 7, 4, 2, 5, 8, 11, … }

? Partition the set = {1, 2, 3, , 10} into four sets.

Partioning a set using Equivalence Classes

Equivalence classes partition sets. They allocate elements of a set into

distinct, non empty, disjoint subsets such that each element belongs exactly
one of the subsets.

Formally we state that, if is an equivalence relation on a set the

equivalence classes of form a partition of set . Let us recall what an
equivalence class [ ] means.

[ ] ={ ∈ : }

Because of the reflexive property ∈ [ ], hence all equivalence classes are

non empty and the union of all equivalence classes is . Now we need to
show that no two distinct equivalence classes overlap.

Suppose and are two distinct elements in and [ ] ∩ [ ] ≠ . We need to

show that [ ] = [ ].
Since [ ] ∩ [ ] ≠ we can pick an element such that ∈ [ ]and ∈ [ ]. As
∈ [ ]then . Similarly as ∈ [ ] then . Thus by transitive and
symmetry properties of equivalence relations we have and .

Now we want to show that [ ] ⊂ [ ].

∈[ ]→ . But , hence by the transitive property, → ∈ [ ]. This

means [ ] ⊂ [ ]. By a similar argument we get [ ] ⊂ [ ]implying [ ] = [ ] .

Example 5.5
Partition set in its equivalence classes, where the equivalence relation on
is whenever is divisible by 3.

We have three distinct partitions corresponding to [0], [1] and [2] where

[0] = {… , 9, 6, 3, 0, 3, 6, 9, … }
[1] = { 8, 5, 2, 1, 4, 7, 10, … }
[2] = { 7, 4, 1, 2, 5, 8, 11, … }

Note that no two partitions overlap, and the union of the three partitions
gives .

Which of the following are partitions of the set of integers ?

? (i) the sets of even numbers and the set of odd numbers.
(ii) the set of positive numbers and the set of negative numbers.
(iii) the set of rational numbers and the set of irrational numbers.
(iv) the set of numbers divisible by three and the set of numbers
divisible by 2.
(v) the set of numbers less than 10 and the set of numbers
greater than nine.

Summary
In this lecture we study a process of comparing elements within
the same set by use of a relation. We learned about a particular
type of relation, called an equivalence relation which allocates
each element of a set into a unique equivalence class. The
equivalence classes derived from an equivalence relation form a
partition of a set. The partitioning of a set assists us in studying
properties of set elements in groups, by assembling elements
with similar, (or identical) properties in distinct groups.