2Sets, functions and relations

IA Numbers and Sets

2.3 Relations

Definition

(Relation)

.

A relation

R

on

A

specifies that some elements of

A

are

related to some others. Formally, a relation is a subset

R ⊆ A × A

. We write

aRb iff (a, b) ∈ R.

Example. The following are examples of relations on natural numbers:

(i) aRb iff a and b have the same final digit. e.g. (37)R(57).

(ii) aRb iff a divides b. e.g. 2R6 and 2 6R7.

(iii) aRb iff a 6= b.

(iv) aRb iff a = b = 1.

(v) aRb iff |a − b| ≤ 3.

(vi) aRb iff either a, b ≥ 5 or a, b ≤ 4.

Again, we wish to classify different relations.

Definition (Reflexive relation). A relation R is reflexive if

(∀a) aRa.

Definition (Symmetric relation). A relation R is symmetric iff

(∀a, b) aRb ⇔ bRa.

Definition (Transitive relation). A relation R is transitive iff

(∀a, b, c) aRb ∧ bRc ⇒ aRc.

Example. With regards to the examples above,

Examples (i) (ii) (iii) (iv) (v) (vi)

Reflexive X X × × X X

Symmetric X × X X X X

Transitive X X × X × X

Definition (Equivalence relation). A relation is an equivalence relation if it is

reflexive, symmetric and transitive. e.g. (i) and (vi) in the above examples are

equivalence relations.

If it is an equivalence relation, we usually write

∼

instead of

R

. As the name

suggests, equivalence relations are used to describe relations that are similar

to equality. For example, if we want to represent rational numbers as a pair

of integers, we might have an equivalence relation defined by (

n, m

)

∼

(

p, q

) iff

nq

=

mp

, such that two pairs are equivalent if they represent the same rational

number.

Example.

If we consider a deck of cards, define two cards to be related if they

have the same suite.

As mentioned, we like to think of things related by

∼

as equal. Hence we

want to identify all “equal” things together and form one new object.

Definition

(Equivalence class)

.

If

∼

is an equivalence relation, then the equiva-

lence class [x] is the set of all elements that are related via ∼ to x.

Example. In the cards example, [8♥] is the set of all hearts.

Definition

(Partition of set)

.

A partition of a set

X

is a collection of subsets

A

α

of X such that each element of X is in exactly one of A

α

.

Theorem.

If

∼

is an equivalence relation on

A

, then the equivalence classes of

∼ form a partition of A.

Proof.

By reflexivity, we have

a ∈

[

a

]. Thus the equivalence classes cover the

whole set. We must now show that for all

a, b ∈ A

, either [

a

] = [

b

] or [

a

]

∩

[

b

] =

∅

.

Suppose [

a

]

∩

[

b

]

6

=

∅

. Then

∃c ∈

[

a

]

∩

[

b

]. So

a ∼ c, b ∼ c

. By symmetry,

c ∼ b

. By transitivity, we have

a ∼ b

. For all

b

0

∈

[

b

], we have

b ∼ b

0

. Thus

by transitivity, we have

a ∼ b

0

. Thus [

b

]

⊆

[

a

]. By symmetry, [

a

]

⊆

[

b

] and

[a] = [b].

On the other hand, each partition defines an equivalence relation in which

two elements are related iff they are in the same partition. Thus partitions and

equivalence relations are “the same thing”.

Definition

(Quotient map)

.

The quotient map

q

maps each element in

A

to

the equivalence class containing a, i.e. a 7→ [a]. e.g. q(8♥) = {♥}.