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♥) = {♥}.