Dsicrete Mathematics

SHENG BAU

University of Kwazulu-Natal, Pietermaritzburg, South Africa

Sets
We do not define sets in this course.
Sets
We do not define sets in this course.
The concept
Sets
We do not define sets in this course.
The concept
We understand a set X is given if for every x, exactly one of the following can be
determined: x ∈ X or x ̸∈ X.
Sets
We do not define sets in this course.
The concept
We understand a set X is given if for every x, exactly one of the following can be
determined: x ∈ X or x ̸∈ X.
An object satisfying this condition is understood to be a set and an object not satisfying
this condition is understood to be not a set. There are more rigorous and axiomatic
treatment of this, but our treatment in this course is a naive one based on this
understanding. Let A and B be sets.
 A ⊆ B: x ∈ A ⇒ x ∈ B;
Sets
We do not define sets in this course.
The concept
We understand a set X is given if for every x, exactly one of the following can be
determined: x ∈ X or x ̸∈ X.
An object satisfying this condition is understood to be a set and an object not satisfying
this condition is understood to be not a set. There are more rigorous and axiomatic
treatment of this, but our treatment in this course is a naive one based on this
understanding. Let A and B be sets.
 A ⊆ B: x ∈ A ⇒ x ∈ B;
 A = B: A ⊆ B and B ⊆ A;
Sets
We do not define sets in this course.
The concept
We understand a set X is given if for every x, exactly one of the following can be
determined: x ∈ X or x ̸∈ X.
An object satisfying this condition is understood to be a set and an object not satisfying
this condition is understood to be not a set. There are more rigorous and axiomatic
treatment of this, but our treatment in this course is a naive one based on this
understanding. Let A and B be sets.
 A ⊆ B: x ∈ A ⇒ x ∈ B;
 A = B: A ⊆ B and B ⊆ A;
 A ∪ B = {x : x ∈ A or x ∈ B};
Sets
We do not define sets in this course.
The concept
We understand a set X is given if for every x, exactly one of the following can be
determined: x ∈ X or x ̸∈ X.
An object satisfying this condition is understood to be a set and an object not satisfying
this condition is understood to be not a set. There are more rigorous and axiomatic
treatment of this, but our treatment in this course is a naive one based on this
understanding. Let A and B be sets.
 A ⊆ B: x ∈ A ⇒ x ∈ B;
 A = B: A ⊆ B and B ⊆ A;
 A ∪ B = {x : x ∈ A or x ∈ B};
 A ∩ B = {x : x ∈ A and x ∈ B};
Sets
We do not define sets in this course.
The concept
We understand a set X is given if for every x, exactly one of the following can be
determined: x ∈ X or x ̸∈ X.
An object satisfying this condition is understood to be a set and an object not satisfying
this condition is understood to be not a set. There are more rigorous and axiomatic
treatment of this, but our treatment in this course is a naive one based on this
understanding. Let A and B be sets.
 A ⊆ B: x ∈ A ⇒ x ∈ B;
 A = B: A ⊆ B and B ⊆ A;
 A ∪ B = {x : x ∈ A or x ∈ B};
 A ∩ B = {x : x ∈ A and x ∈ B};
 A \ B = {x : x ∈ A and x ̸∈ B};
Sets
We do not define sets in this course.
The concept
We understand a set X is given if for every x, exactly one of the following can be
determined: x ∈ X or x ̸∈ X.
An object satisfying this condition is understood to be a set and an object not satisfying
this condition is understood to be not a set. There are more rigorous and axiomatic
treatment of this, but our treatment in this course is a naive one based on this
understanding. Let A and B be sets.
 A ⊆ B: x ∈ A ⇒ x ∈ B;
 A = B: A ⊆ B and B ⊆ A;
 A ∪ B = {x : x ∈ A or x ∈ B};
 A ∩ B = {x : x ∈ A and x ∈ B};
 A \ B = {x : x ∈ A and x ̸∈ B};
 A + B = (A \ B) ∪ (B \ A) = (A ∪ B) \ (A ∩ B).
Let A and B be sets. The cartesian product of A and B is defined to be

A × B = {(x, y) : x ∈ A, y ∈ B}.
Let A and B be sets. The cartesian product of A and B is defined to be

A × B = {(x, y) : x ∈ A, y ∈ B}.

Let S be a set and A ⊆ S. Then Ā = S \ A is the complement of A in S.

Let A and B be sets. The cartesian product of A and B is defined to be

A × B = {(x, y) : x ∈ A, y ∈ B}.

Let S be a set and A ⊆ S. Then Ā = S \ A is the complement of A in S.

EXAMPLE 1
Let A = {0, 2, 5} and B = {0, 5, 6, 9}.
Let A and B be sets. The cartesian product of A and B is defined to be

A × B = {(x, y) : x ∈ A, y ∈ B}.

Let S be a set and A ⊆ S. Then Ā = S \ A is the complement of A in S.

EXAMPLE 1
Let A = {0, 2, 5} and B = {0, 5, 6, 9}.
Let A and B be sets. The cartesian product of A and B is defined to be

A × B = {(x, y) : x ∈ A, y ∈ B}.

Let S be a set and A ⊆ S. Then Ā = S \ A is the complement of A in S.

EXAMPLE 1
Let A = {0, 2, 5} and B = {0, 5, 6, 9}.
Then
A ∪ B = {0, 2, 5, 6, 9},
Let A and B be sets. The cartesian product of A and B is defined to be

A × B = {(x, y) : x ∈ A, y ∈ B}.

Let S be a set and A ⊆ S. Then Ā = S \ A is the complement of A in S.

EXAMPLE 1
Let A = {0, 2, 5} and B = {0, 5, 6, 9}.
Then
A ∪ B = {0, 2, 5, 6, 9},
A ∩ B = {0, 5},
Let A and B be sets. The cartesian product of A and B is defined to be

A × B = {(x, y) : x ∈ A, y ∈ B}.

Let S be a set and A ⊆ S. Then Ā = S \ A is the complement of A in S.

EXAMPLE 1
Let A = {0, 2, 5} and B = {0, 5, 6, 9}.
Then
A ∪ B = {0, 2, 5, 6, 9},
A ∩ B = {0, 5},
A \ B = {2},
Let A and B be sets. The cartesian product of A and B is defined to be

A × B = {(x, y) : x ∈ A, y ∈ B}.

Let S be a set and A ⊆ S. Then Ā = S \ A is the complement of A in S.

EXAMPLE 1
Let A = {0, 2, 5} and B = {0, 5, 6, 9}.
Then
A ∪ B = {0, 2, 5, 6, 9},
A ∩ B = {0, 5},
A \ B = {2},
B \ A = {6, 9},
Let A and B be sets. The cartesian product of A and B is defined to be

A × B = {(x, y) : x ∈ A, y ∈ B}.

Let S be a set and A ⊆ S. Then Ā = S \ A is the complement of A in S.

EXAMPLE 1
Let A = {0, 2, 5} and B = {0, 5, 6, 9}.
Then
A ∪ B = {0, 2, 5, 6, 9},
A ∩ B = {0, 5},
A \ B = {2},
B \ A = {6, 9},
A + B = {2, 6, 9},
Let A and B be sets. The cartesian product of A and B is defined to be

A × B = {(x, y) : x ∈ A, y ∈ B}.

Let S be a set and A ⊆ S. Then Ā = S \ A is the complement of A in S.

EXAMPLE 1
Let A = {0, 2, 5} and B = {0, 5, 6, 9}.
Then
A ∪ B = {0, 2, 5, 6, 9},
A ∩ B = {0, 5},
A \ B = {2},
B \ A = {6, 9},
A + B = {2, 6, 9},
A × B = {(0, 0), (0, 5), (0, 6), (0, 9), (2, 0), (2, 5), (2, 6), (2, 9),
(5, 0), (5, 5), (5, 6), (5, 9)}.
Let A and B be sets. The cartesian product of A and B is defined to be

A × B = {(x, y) : x ∈ A, y ∈ B}.

Let S be a set and A ⊆ S. Then Ā = S \ A is the complement of A in S.

EXAMPLE 1
Let A = {0, 2, 5} and B = {0, 5, 6, 9}.
Then
A ∪ B = {0, 2, 5, 6, 9},
A ∩ B = {0, 5},
A \ B = {2},
B \ A = {6, 9},
A + B = {2, 6, 9},
A × B = {(0, 0), (0, 5), (0, 6), (0, 9), (2, 0), (2, 5), (2, 6), (2, 9),
(5, 0), (5, 5), (5, 6), (5, 9)}.
If S = {0, 1, . . . , 10}, then Ā = {1, 3, 4, 6, 7, 8, 9, 10}.
Sets often encountered in this course:
 The set of natural numbers (or positive integers):

N = {1, 2, . . . , n, . . .}.
Sets often encountered in this course:
 The set of natural numbers (or positive integers):

N = {1, 2, . . . , n, . . .}.

 The set of integers:

Z = {. . . , −2, −1, 0, 1, 2, . . .}.
Sets often encountered in this course:
 The set of natural numbers (or positive integers):

N = {1, 2, . . . , n, . . .}.

 The set of integers:

Z = {. . . , −2, −1, 0, 1, 2, . . .}.
 The set of real numbers: R (What is the definition of R?).
Sets often encountered in this course:
 The set of natural numbers (or positive integers):

N = {1, 2, . . . , n, . . .}.

 The set of integers:

Z = {. . . , −2, −1, 0, 1, 2, . . .}.
 The set of real numbers: R (What is the definition of R?).
 The set of rational numbers:
na o
Q= : a, b ∈ Z, b ̸= 0 .
b
Sets often encountered in this course:
 The set of natural numbers (or positive integers):

N = {1, 2, . . . , n, . . .}.

 The set of integers:

Z = {. . . , −2, −1, 0, 1, 2, . . .}.
 The set of real numbers: R (What is the definition of R?).
 The set of rational numbers:
na o
Q= : a, b ∈ Z, b ̸= 0 .
b
 The set of irrational numbers: R \ Q.
Sets often encountered in this course:
 The set of natural numbers (or positive integers):

N = {1, 2, . . . , n, . . .}.

 The set of integers:

Z = {. . . , −2, −1, 0, 1, 2, . . .}.
 The set of real numbers: R (What is the definition of R?).
 The set of rational numbers:
na o
Q= : a, b ∈ Z, b ̸= 0 .
b
 The set of irrational numbers: R \ Q.
Sets often encountered in this course:
 The set of natural numbers (or positive integers):

N = {1, 2, . . . , n, . . .}.

 The set of integers:

Z = {. . . , −2, −1, 0, 1, 2, . . .}.
 The set of real numbers: R (What is the definition of R?).
 The set of rational numbers:
na o
Q= : a, b ∈ Z, b ̸= 0 .
b
 The set of irrational numbers: R \ Q.

EXAMPLE 2 √
−1 ∈ Z \ N, 2 ∈ R \ Q, and
N ⊆ Z ⊆ Q ⊆ R.
THEOREM 1 (De Morgan’s)
Let S be a set and A1 , A2 , . . . , An ⊆ S. Then

A1 ∪ A2 ∪ · · · ∪ An = Ā1 ∩ Ā2 ∩ · · · ∩ Ān .

THEOREM 1 (De Morgan’s)
Let S be a set and A1 , A2 , . . . , An ⊆ S. Then

A1 ∪ A2 ∪ · · · ∪ An = Ā1 ∩ Ā2 ∩ · · · ∩ Ān .

Proof.
By definitions (which?), we have

x ∈ A1 ∪ A2 ∪ · · · ∪ An ⇔ x ̸∈ A1 ∪ A2 ∪ · · · ∪ An
THEOREM 1 (De Morgan’s)
Let S be a set and A1 , A2 , . . . , An ⊆ S. Then

A1 ∪ A2 ∪ · · · ∪ An = Ā1 ∩ Ā2 ∩ · · · ∩ Ān .

Proof.
By definitions (which?), we have

x ∈ A1 ∪ A2 ∪ · · · ∪ An ⇔ x ̸∈ A1 ∪ A2 ∪ · · · ∪ An
THEOREM 1 (De Morgan’s)
Let S be a set and A1 , A2 , . . . , An ⊆ S. Then

A1 ∪ A2 ∪ · · · ∪ An = Ā1 ∩ Ā2 ∩ · · · ∩ Ān .

Proof.
By definitions (which?), we have

x ∈ A1 ∪ A2 ∪ · · · ∪ An ⇔ x ̸∈ A1 ∪ A2 ∪ · · · ∪ An
⇔ x ̸∈ A1 and x ̸∈ A2 and · · · and x ̸∈ An
THEOREM 1 (De Morgan’s)
Let S be a set and A1 , A2 , . . . , An ⊆ S. Then

A1 ∪ A2 ∪ · · · ∪ An = Ā1 ∩ Ā2 ∩ · · · ∩ Ān .

Proof.
By definitions (which?), we have

x ∈ A1 ∪ A2 ∪ · · · ∪ An ⇔ x ̸∈ A1 ∪ A2 ∪ · · · ∪ An
⇔ x ̸∈ A1 and x ̸∈ A2 and · · · and x ̸∈ An
⇔ x ∈ Ā1 and x ∈ Ā2 and · · · and x ∈ Ān
THEOREM 1 (De Morgan’s)
Let S be a set and A1 , A2 , . . . , An ⊆ S. Then

A1 ∪ A2 ∪ · · · ∪ An = Ā1 ∩ Ā2 ∩ · · · ∩ Ān .

Proof.
By definitions (which?), we have

x ∈ A1 ∪ A2 ∪ · · · ∪ An ⇔ x ̸∈ A1 ∪ A2 ∪ · · · ∪ An
⇔ x ̸∈ A1 and x ̸∈ A2 and · · · and x ̸∈ An
⇔ x ∈ Ā1 and x ∈ Ā2 and · · · and x ∈ Ān
⇔ x ∈ Ā1 ∩ Ā2 ∩ · · · ∩ Ān .
EXAMPLE 3
Let S = {1, 2, . . . , 8}, A = {1, 2, 3, 4} and B = {3, 4, 5, 6}.
EXAMPLE 3
Let S = {1, 2, . . . , 8}, A = {1, 2, 3, 4} and B = {3, 4, 5, 6}.
EXAMPLE 3
Let S = {1, 2, . . . , 8}, A = {1, 2, 3, 4} and B = {3, 4, 5, 6}.
Then
EXAMPLE 3
Let S = {1, 2, . . . , 8}, A = {1, 2, 3, 4} and B = {3, 4, 5, 6}.
Then

A ∪ B = {1, 2, 3, 4, 5, 6},
EXAMPLE 3
Let S = {1, 2, . . . , 8}, A = {1, 2, 3, 4} and B = {3, 4, 5, 6}.
Then

A ∪ B = {1, 2, 3, 4, 5, 6},
A ∪ B = {7, 8},
EXAMPLE 3
Let S = {1, 2, . . . , 8}, A = {1, 2, 3, 4} and B = {3, 4, 5, 6}.
Then

A ∪ B = {1, 2, 3, 4, 5, 6},
A ∪ B = {7, 8},
Ā = {5, 6, 7, 8},
EXAMPLE 3
Let S = {1, 2, . . . , 8}, A = {1, 2, 3, 4} and B = {3, 4, 5, 6}.
Then

A ∪ B = {1, 2, 3, 4, 5, 6},
A ∪ B = {7, 8},
Ā = {5, 6, 7, 8},
B̄ = {1, 2, 7, 8},
EXAMPLE 3
Let S = {1, 2, . . . , 8}, A = {1, 2, 3, 4} and B = {3, 4, 5, 6}.
Then

A ∪ B = {1, 2, 3, 4, 5, 6},
A ∪ B = {7, 8},
Ā = {5, 6, 7, 8},
B̄ = {1, 2, 7, 8},
Ā ∩ B̄ = {7, 8}.
Partitions
Let A, B be sets. If A ∩ B = ∅ then A and B are said to be disjoint. Definition Let X be a
set. If X is the disjoint union of a set of nonempty subsets of X, then X is said to be
partitioned into these subsets.
Partitions
Let A, B be sets. If A ∩ B = ∅ then A and B are said to be disjoint. Definition Let X be a
set. If X is the disjoint union of a set of nonempty subsets of X, then X is said to be
partitioned into these subsets.
If A1 , A2 , . . . , An are nonemtpy subsets of X such that i ̸= j implies Ai ∩ Aj = ∅ and
A1 ∪ A2 ∪ · · · ∪ An = S, then {A1 , A2 , . . . , An } is called a partition of S.
Partitions
Let A, B be sets. If A ∩ B = ∅ then A and B are said to be disjoint. Definition Let X be a
set. If X is the disjoint union of a set of nonempty subsets of X, then X is said to be
partitioned into these subsets.
If A1 , A2 , . . . , An are nonemtpy subsets of X such that i ̸= j implies Ai ∩ Aj = ∅ and
A1 ∪ A2 ∪ · · · ∪ An = S, then {A1 , A2 , . . . , An } is called a partition of S.
Let I, X be sets. A partition is characterized by conjunction of the three conditions:
 For every i ∈ I, Ai ̸= ∅ and Ai ⊆ X;
Partitions
Let A, B be sets. If A ∩ B = ∅ then A and B are said to be disjoint. Definition Let X be a
set. If X is the disjoint union of a set of nonempty subsets of X, then X is said to be
partitioned into these subsets.
If A1 , A2 , . . . , An are nonemtpy subsets of X such that i ̸= j implies Ai ∩ Aj = ∅ and
A1 ∪ A2 ∪ · · · ∪ An = S, then {A1 , A2 , . . . , An } is called a partition of S.
Let I, X be sets. A partition is characterized by conjunction of the three conditions:
 For every i ∈ I, Ai ̸= ∅ and Ai ⊆ X;
 For every i, j ∈ I, i ̸= j ⇒ Ai ∩ Aj = ∅;
Partitions
Let A, B be sets. If A ∩ B = ∅ then A and B are said to be disjoint. Definition Let X be a
set. If X is the disjoint union of a set of nonempty subsets of X, then X is said to be
partitioned into these subsets.
If A1 , A2 , . . . , An are nonemtpy subsets of X such that i ̸= j implies Ai ∩ Aj = ∅ and
A1 ∪ A2 ∪ · · · ∪ An = S, then {A1 , A2 , . . . , An } is called a partition of S.
Let I, X be sets. A partition is characterized by conjunction of the three conditions:
 For every i ∈ I, Ai ̸= ∅ and Ai ⊆ X;
 For every i, j ∈ I, i ̸= j ⇒ Ai ∩ Aj = ∅;
S
 X = Ai .
i∈I
Partitions
Let A, B be sets. If A ∩ B = ∅ then A and B are said to be disjoint. Definition Let X be a
set. If X is the disjoint union of a set of nonempty subsets of X, then X is said to be
partitioned into these subsets.
If A1 , A2 , . . . , An are nonemtpy subsets of X such that i ̸= j implies Ai ∩ Aj = ∅ and
A1 ∪ A2 ∪ · · · ∪ An = S, then {A1 , A2 , . . . , An } is called a partition of S.
Let I, X be sets. A partition is characterized by conjunction of the three conditions:
 For every i ∈ I, Ai ̸= ∅ and Ai ⊆ X;
 For every i, j ∈ I, i ̸= j ⇒ Ai ∩ Aj = ∅;
S
 X = Ai .
i∈I
Partitions
Let A, B be sets. If A ∩ B = ∅ then A and B are said to be disjoint. Definition Let X be a
set. If X is the disjoint union of a set of nonempty subsets of X, then X is said to be
partitioned into these subsets.
If A1 , A2 , . . . , An are nonemtpy subsets of X such that i ̸= j implies Ai ∩ Aj = ∅ and
A1 ∪ A2 ∪ · · · ∪ An = S, then {A1 , A2 , . . . , An } is called a partition of S.
Let I, X be sets. A partition is characterized by conjunction of the three conditions:
 For every i ∈ I, Ai ̸= ∅ and Ai ⊆ X;
 For every i, j ∈ I, i ̸= j ⇒ Ai ∩ Aj = ∅;
S
 X = Ai .
i∈I
Each Ai is called a part of the partition.
Partitions
Let A, B be sets. If A ∩ B = ∅ then A and B are said to be disjoint. Definition Let X be a
set. If X is the disjoint union of a set of nonempty subsets of X, then X is said to be
partitioned into these subsets.
If A1 , A2 , . . . , An are nonemtpy subsets of X such that i ̸= j implies Ai ∩ Aj = ∅ and
A1 ∪ A2 ∪ · · · ∪ An = S, then {A1 , A2 , . . . , An } is called a partition of S.
Let I, X be sets. A partition is characterized by conjunction of the three conditions:
 For every i ∈ I, Ai ̸= ∅ and Ai ⊆ X;
 For every i, j ∈ I, i ̸= j ⇒ Ai ∩ Aj = ∅;
S
 X = Ai .
i∈I
Each Ai is called a part of the partition. For each x ∈ X, there exists exactly one i ∈ I with
x ∈ Ai .
EXAMPLE 4
Let X = {1, 2, . . . , 10}, A1 = {2, 3, 8}, A2 = {1}, A3 = {4, 5, 9, 10}, A4 = {6, 7}.
EXAMPLE 4
Let X = {1, 2, . . . , 10}, A1 = {2, 3, 8}, A2 = {1}, A3 = {4, 5, 9, 10}, A4 = {6, 7}.
EXAMPLE 4
Let X = {1, 2, . . . , 10}, A1 = {2, 3, 8}, A2 = {1}, A3 = {4, 5, 9, 10}, A4 = {6, 7}.
Then
 {A1 , A2 , A3 , A4 } is a partition of X;
EXAMPLE 4
Let X = {1, 2, . . . , 10}, A1 = {2, 3, 8}, A2 = {1}, A3 = {4, 5, 9, 10}, A4 = {6, 7}.
Then
 {A1 , A2 , A3 , A4 } is a partition of X;
 {{1}, {2}, . . . , {10}} is also a partition of X;
EXAMPLE 4
Let X = {1, 2, . . . , 10}, A1 = {2, 3, 8}, A2 = {1}, A3 = {4, 5, 9, 10}, A4 = {6, 7}.
Then
 {A1 , A2 , A3 , A4 } is a partition of X;
 {{1}, {2}, . . . , {10}} is also a partition of X;
 If A′1 = {1, 2, 3, 8}, then {A′1 , A2 , A3 , A4 } is not a partition of X.
EXAMPLE 4
Let X = {1, 2, . . . , 10}, A1 = {2, 3, 8}, A2 = {1}, A3 = {4, 5, 9, 10}, A4 = {6, 7}.
Then
 {A1 , A2 , A3 , A4 } is a partition of X;
 {{1}, {2}, . . . , {10}} is also a partition of X;
 If A′1 = {1, 2, 3, 8}, then {A′1 , A2 , A3 , A4 } is not a partition of X.
EXAMPLE 4
Let X = {1, 2, . . . , 10}, A1 = {2, 3, 8}, A2 = {1}, A3 = {4, 5, 9, 10}, A4 = {6, 7}.
Then
 {A1 , A2 , A3 , A4 } is a partition of X;
 {{1}, {2}, . . . , {10}} is also a partition of X;
 If A′1 = {1, 2, 3, 8}, then {A′1 , A2 , A3 , A4 } is not a partition of X.

EXAMPLE 5
{Q, R \ Q} is a partition of R.
EXAMPLE 4
Let X = {1, 2, . . . , 10}, A1 = {2, 3, 8}, A2 = {1}, A3 = {4, 5, 9, 10}, A4 = {6, 7}.
Then
 {A1 , A2 , A3 , A4 } is a partition of X;
 {{1}, {2}, . . . , {10}} is also a partition of X;
 If A′1 = {1, 2, 3, 8}, then {A′1 , A2 , A3 , A4 } is not a partition of X.

EXAMPLE 5
{Q, R \ Q} is a partition of R.
EXAMPLE 4
Let X = {1, 2, . . . , 10}, A1 = {2, 3, 8}, A2 = {1}, A3 = {4, 5, 9, 10}, A4 = {6, 7}.
Then
 {A1 , A2 , A3 , A4 } is a partition of X;
 {{1}, {2}, . . . , {10}} is also a partition of X;
 If A′1 = {1, 2, 3, 8}, then {A′1 , A2 , A3 , A4 } is not a partition of X.

EXAMPLE 5
{Q, R \ Q} is a partition of R.

EXAMPLE 6
Let
A0 = {3r : r ∈ Z},
A1 = {3r + 1 : r ∈ Z},
A2 = {3r + 2 : r ∈ Z}.
EXAMPLE 4
Let X = {1, 2, . . . , 10}, A1 = {2, 3, 8}, A2 = {1}, A3 = {4, 5, 9, 10}, A4 = {6, 7}.
Then
 {A1 , A2 , A3 , A4 } is a partition of X;
 {{1}, {2}, . . . , {10}} is also a partition of X;
 If A′1 = {1, 2, 3, 8}, then {A′1 , A2 , A3 , A4 } is not a partition of X.

EXAMPLE 5
{Q, R \ Q} is a partition of R.

EXAMPLE 6
Let
A0 = {3r : r ∈ Z},
A1 = {3r + 1 : r ∈ Z},
A2 = {3r + 2 : r ∈ Z}.
EXAMPLE 4
Let X = {1, 2, . . . , 10}, A1 = {2, 3, 8}, A2 = {1}, A3 = {4, 5, 9, 10}, A4 = {6, 7}.
Then
 {A1 , A2 , A3 , A4 } is a partition of X;
 {{1}, {2}, . . . , {10}} is also a partition of X;
 If A′1 = {1, 2, 3, 8}, then {A′1 , A2 , A3 , A4 } is not a partition of X.

EXAMPLE 5
{Q, R \ Q} is a partition of R.

EXAMPLE 6
Let
A0 = {3r : r ∈ Z},
A1 = {3r + 1 : r ∈ Z},
A2 = {3r + 2 : r ∈ Z}.

We verify that {A0 , A1 , A2 } is a partition of Z.

Binary Relations
Binary Relations
Binary Relations
Binary Relations Let X, Y be sets. Then every subset R ⊆ X × Y is a called a binary
relation from X to Y.
domR = {x ∈ X : ∃y ∈ Y, (x, y) ∈ R},
ranR = {y ∈ Y : ∃x ∈ X, (x, y) ∈ R}.

These are called domain and range of R.

Binary Relations
Binary Relations Let X, Y be sets. Then every subset R ⊆ X × Y is a called a binary
relation from X to Y.
domR = {x ∈ X : ∃y ∈ Y, (x, y) ∈ R},
ranR = {y ∈ Y : ∃x ∈ X, (x, y) ∈ R}.

These are called domain and range of R.

A binary relation R ⊆ X × X is called a binary relation on X.
Binary Relations
Binary Relations Let X, Y be sets. Then every subset R ⊆ X × Y is a called a binary
relation from X to Y.
domR = {x ∈ X : ∃y ∈ Y, (x, y) ∈ R},
ranR = {y ∈ Y : ∃x ∈ X, (x, y) ∈ R}.

These are called domain and range of R.

A binary relation R ⊆ X × X is called a binary relation on X.
A binary relation f ⊆ X × Y satisfying the two conditions below is called a function or a
mapping from X to Y.
Binary Relations
Binary Relations Let X, Y be sets. Then every subset R ⊆ X × Y is a called a binary
relation from X to Y.
domR = {x ∈ X : ∃y ∈ Y, (x, y) ∈ R},
ranR = {y ∈ Y : ∃x ∈ X, (x, y) ∈ R}.

These are called domain and range of R.

A binary relation R ⊆ X × X is called a binary relation on X.
A binary relation f ⊆ X × Y satisfying the two conditions below is called a function or a
mapping from X to Y.
1. ∀x ∈ X, ∃y ∈ Y, (x, y) ∈ f ;
Binary Relations
Binary Relations Let X, Y be sets. Then every subset R ⊆ X × Y is a called a binary
relation from X to Y.
domR = {x ∈ X : ∃y ∈ Y, (x, y) ∈ R},
ranR = {y ∈ Y : ∃x ∈ X, (x, y) ∈ R}.

These are called domain and range of R.

A binary relation R ⊆ X × X is called a binary relation on X.
A binary relation f ⊆ X × Y satisfying the two conditions below is called a function or a
mapping from X to Y.
1. ∀x ∈ X, ∃y ∈ Y, (x, y) ∈ f ;
2. (x, y), (x, z) ∈ f ⇒ z = y.
EXAMPLE 7
Let A = {1, 2, 3, 4}, B = {a, b, c, d} and R = {(1, a), (1, c), (2, a), (2, b), (3, c)}.
EXAMPLE 7
Let A = {1, 2, 3, 4}, B = {a, b, c, d} and R = {(1, a), (1, c), (2, a), (2, b), (3, c)}.
EXAMPLE 7
Let A = {1, 2, 3, 4}, B = {a, b, c, d} and R = {(1, a), (1, c), (2, a), (2, b), (3, c)}.
Then
 R is a binary relation;
EXAMPLE 7
Let A = {1, 2, 3, 4}, B = {a, b, c, d} and R = {(1, a), (1, c), (2, a), (2, b), (3, c)}.
Then
 R is a binary relation;
 domR = {1, 2, 3};
EXAMPLE 7
Let A = {1, 2, 3, 4}, B = {a, b, c, d} and R = {(1, a), (1, c), (2, a), (2, b), (3, c)}.
Then
 R is a binary relation;
 domR = {1, 2, 3};
 ranR = {a, b, c}.
EXAMPLE 7
Let A = {1, 2, 3, 4}, B = {a, b, c, d} and R = {(1, a), (1, c), (2, a), (2, b), (3, c)}.
Then
 R is a binary relation;
 domR = {1, 2, 3};
 ranR = {a, b, c}.
EXAMPLE 7
Let A = {1, 2, 3, 4}, B = {a, b, c, d} and R = {(1, a), (1, c), (2, a), (2, b), (3, c)}.
Then
 R is a binary relation;
 domR = {1, 2, 3};
 ranR = {a, b, c}.
Next consider some basic properties of a binary relation that are of interest.
EXAMPLE 7
Let A = {1, 2, 3, 4}, B = {a, b, c, d} and R = {(1, a), (1, c), (2, a), (2, b), (3, c)}.
Then
 R is a binary relation;
 domR = {1, 2, 3};
 ranR = {a, b, c}.
Next consider some basic properties of a binary relation that are of interest.
Let R be a binary relation on a set X.
 Reflexivity: ∀x ∈ X, (x, x) ∈ R;
EXAMPLE 7
Let A = {1, 2, 3, 4}, B = {a, b, c, d} and R = {(1, a), (1, c), (2, a), (2, b), (3, c)}.
Then
 R is a binary relation;
 domR = {1, 2, 3};
 ranR = {a, b, c}.
Next consider some basic properties of a binary relation that are of interest.
Let R be a binary relation on a set X.
 Reflexivity: ∀x ∈ X, (x, x) ∈ R;
 Irreflexivity: ∀x ∈ X, (x, x) ̸∈ R;
EXAMPLE 7
Let A = {1, 2, 3, 4}, B = {a, b, c, d} and R = {(1, a), (1, c), (2, a), (2, b), (3, c)}.
Then
 R is a binary relation;
 domR = {1, 2, 3};
 ranR = {a, b, c}.
Next consider some basic properties of a binary relation that are of interest.
Let R be a binary relation on a set X.
 Reflexivity: ∀x ∈ X, (x, x) ∈ R;
 Irreflexivity: ∀x ∈ X, (x, x) ̸∈ R;
 Symmetry: ∀x, y ∈ X, (x, y) ∈ R ⇒ (y, x) ∈ R;
EXAMPLE 7
Let A = {1, 2, 3, 4}, B = {a, b, c, d} and R = {(1, a), (1, c), (2, a), (2, b), (3, c)}.
Then
 R is a binary relation;
 domR = {1, 2, 3};
 ranR = {a, b, c}.
Next consider some basic properties of a binary relation that are of interest.
Let R be a binary relation on a set X.
 Reflexivity: ∀x ∈ X, (x, x) ∈ R;
 Irreflexivity: ∀x ∈ X, (x, x) ̸∈ R;
 Symmetry: ∀x, y ∈ X, (x, y) ∈ R ⇒ (y, x) ∈ R;
 Antiymmetry: ∀x, y ∈ X, (x, y), (y, x) ∈ R ⇒ x = y;
EXAMPLE 7
Let A = {1, 2, 3, 4}, B = {a, b, c, d} and R = {(1, a), (1, c), (2, a), (2, b), (3, c)}.
Then
 R is a binary relation;
 domR = {1, 2, 3};
 ranR = {a, b, c}.
Next consider some basic properties of a binary relation that are of interest.
Let R be a binary relation on a set X.
 Reflexivity: ∀x ∈ X, (x, x) ∈ R;
 Irreflexivity: ∀x ∈ X, (x, x) ̸∈ R;
 Symmetry: ∀x, y ∈ X, (x, y) ∈ R ⇒ (y, x) ∈ R;
 Antiymmetry: ∀x, y ∈ X, (x, y), (y, x) ∈ R ⇒ x = y;
 Transitivity: ∀x, y, z ∈ X, (x, y), (y, z) ∈ R ⇒ (x, z) ∈ R.
EXAMPLE 8
Let R = {(x, x2 ) : x ∈ R}. Then R is a binary relation on R.
EXAMPLE 8
Let R = {(x, x2 ) : x ∈ R}. Then R is a binary relation on R.
EXAMPLE 8
Let R = {(x, x2 ) : x ∈ R}. Then R is a binary relation on R.
R is not reflexive: ∵ (2, 2) ̸∈ R.
EXAMPLE 8
Let R = {(x, x2 ) : x ∈ R}. Then R is a binary relation on R.
R is not reflexive: ∵ (2, 2) ̸∈ R.
R is not irreflexive: ∵ (1, 1) ∈ R.
EXAMPLE 8
Let R = {(x, x2 ) : x ∈ R}. Then R is a binary relation on R.
R is not reflexive: ∵ (2, 2) ̸∈ R.
R is not irreflexive: ∵ (1, 1) ∈ R.
This shows also that reflexivity and irreflexivity are not negatives of one another;
EXAMPLE 8
Let R = {(x, x2 ) : x ∈ R}. Then R is a binary relation on R.
R is not reflexive: ∵ (2, 2) ̸∈ R.
R is not irreflexive: ∵ (1, 1) ∈ R.
This shows also that reflexivity and irreflexivity are not negatives of one another;
R is not symmetric: ∵ (2, 4) ∈ R, (4, 2) ̸∈ R;
EXAMPLE 8
Let R = {(x, x2 ) : x ∈ R}. Then R is a binary relation on R.
R is not reflexive: ∵ (2, 2) ̸∈ R.
R is not irreflexive: ∵ (1, 1) ∈ R.
This shows also that reflexivity and irreflexivity are not negatives of one another;
R is not symmetric: ∵ (2, 4) ∈ R, (4, 2) ̸∈ R;
R is antisymmetric: Suppose that (x, y), (y, x) ∈ R. Then y = x2 and x = y2 . Hence
x4 − x = 0. This is x(x3 − 1) = 0, and hence x = 0 or x = 1. If x = 0 then
y = x2 = 02 = 0 and if x = 1 then y = x2 = 12 = 1. Hence we have
(x, y), (y, x) ∈ R ⇒ x = y.
EXAMPLE 8
Let R = {(x, x2 ) : x ∈ R}. Then R is a binary relation on R.
R is not reflexive: ∵ (2, 2) ̸∈ R.
R is not irreflexive: ∵ (1, 1) ∈ R.
This shows also that reflexivity and irreflexivity are not negatives of one another;
R is not symmetric: ∵ (2, 4) ∈ R, (4, 2) ̸∈ R;
R is antisymmetric: Suppose that (x, y), (y, x) ∈ R. Then y = x2 and x = y2 . Hence
x4 − x = 0. This is x(x3 − 1) = 0, and hence x = 0 or x = 1. If x = 0 then
y = x2 = 02 = 0 and if x = 1 then y = x2 = 12 = 1. Hence we have
(x, y), (y, x) ∈ R ⇒ x = y.
R is not transitive: ∵ (2, 4), (4, 16) ∈ R, (2, 16) ̸∈ R.
EXAMPLE 9
Let R = {(x, y) : x, y ∈ Z, x < y}.
EXAMPLE 9
Let R = {(x, y) : x, y ∈ Z, x < y}.
EXAMPLE 9
Let R = {(x, y) : x, y ∈ Z, x < y}.
R is a binary relation on Z;
EXAMPLE 9
Let R = {(x, y) : x, y ∈ Z, x < y}.
R is a binary relation on Z;
R is not reflexive: ∵ ∀x ∈ Z, x ̸< x;
EXAMPLE 9
Let R = {(x, y) : x, y ∈ Z, x < y}.
R is a binary relation on Z;
R is not reflexive: ∵ ∀x ∈ Z, x ̸< x;
R is irreflexive; ∵ ∀x ∈ Z, x ̸< x;
EXAMPLE 9
Let R = {(x, y) : x, y ∈ Z, x < y}.
R is a binary relation on Z;
R is not reflexive: ∵ ∀x ∈ Z, x ̸< x;
R is irreflexive; ∵ ∀x ∈ Z, x ̸< x;
R is not symmetric; ∵ ∀x ∈ Z, if x < y then y < x is not true;
EXAMPLE 9
Let R = {(x, y) : x, y ∈ Z, x < y}.
R is a binary relation on Z;
R is not reflexive: ∵ ∀x ∈ Z, x ̸< x;
R is irreflexive; ∵ ∀x ∈ Z, x ̸< x;
R is not symmetric; ∵ ∀x ∈ Z, if x < y then y < x is not true;
R is antisymmetric: the reason is trivial that the condition is false;
EXAMPLE 9
Let R = {(x, y) : x, y ∈ Z, x < y}.
R is a binary relation on Z;
R is not reflexive: ∵ ∀x ∈ Z, x ̸< x;
R is irreflexive; ∵ ∀x ∈ Z, x ̸< x;
R is not symmetric; ∵ ∀x ∈ Z, if x < y then y < x is not true;
R is antisymmetric: the reason is trivial that the condition is false;
R is transitive: ∵ x < y, y < z ⇒ x < z.
EXAMPLE 10
Let R = {(x, y) : x, y ∈ R, x ≥ y}.
EXAMPLE 9
Let R = {(x, y) : x, y ∈ Z, x < y}.
R is a binary relation on Z;
R is not reflexive: ∵ ∀x ∈ Z, x ̸< x;
R is irreflexive; ∵ ∀x ∈ Z, x ̸< x;
R is not symmetric; ∵ ∀x ∈ Z, if x < y then y < x is not true;
R is antisymmetric: the reason is trivial that the condition is false;
R is transitive: ∵ x < y, y < z ⇒ x < z.
EXAMPLE 10
Let R = {(x, y) : x, y ∈ R, x ≥ y}.
EXAMPLE 9
Let R = {(x, y) : x, y ∈ Z, x < y}.
R is a binary relation on Z;
R is not reflexive: ∵ ∀x ∈ Z, x ̸< x;
R is irreflexive; ∵ ∀x ∈ Z, x ̸< x;
R is not symmetric; ∵ ∀x ∈ Z, if x < y then y < x is not true;
R is antisymmetric: the reason is trivial that the condition is false;
R is transitive: ∵ x < y, y < z ⇒ x < z.
EXAMPLE 10
Let R = {(x, y) : x, y ∈ R, x ≥ y}.
R is a binary relation on R;
EXAMPLE 9
Let R = {(x, y) : x, y ∈ Z, x < y}.
R is a binary relation on Z;
R is not reflexive: ∵ ∀x ∈ Z, x ̸< x;
R is irreflexive; ∵ ∀x ∈ Z, x ̸< x;
R is not symmetric; ∵ ∀x ∈ Z, if x < y then y < x is not true;
R is antisymmetric: the reason is trivial that the condition is false;
R is transitive: ∵ x < y, y < z ⇒ x < z.
EXAMPLE 10
Let R = {(x, y) : x, y ∈ R, x ≥ y}.
R is a binary relation on R;
R is reflexive: ∵ ∀x ∈ Z, x ≥ x;
EXAMPLE 9
Let R = {(x, y) : x, y ∈ Z, x < y}.
R is a binary relation on Z;
R is not reflexive: ∵ ∀x ∈ Z, x ̸< x;
R is irreflexive; ∵ ∀x ∈ Z, x ̸< x;
R is not symmetric; ∵ ∀x ∈ Z, if x < y then y < x is not true;
R is antisymmetric: the reason is trivial that the condition is false;
R is transitive: ∵ x < y, y < z ⇒ x < z.
EXAMPLE 10
Let R = {(x, y) : x, y ∈ R, x ≥ y}.
R is a binary relation on R;
R is reflexive: ∵ ∀x ∈ Z, x ≥ x;
R is not irreflexive;
EXAMPLE 9
Let R = {(x, y) : x, y ∈ Z, x < y}.
R is a binary relation on Z;
R is not reflexive: ∵ ∀x ∈ Z, x ̸< x;
R is irreflexive; ∵ ∀x ∈ Z, x ̸< x;
R is not symmetric; ∵ ∀x ∈ Z, if x < y then y < x is not true;
R is antisymmetric: the reason is trivial that the condition is false;
R is transitive: ∵ x < y, y < z ⇒ x < z.
EXAMPLE 10
Let R = {(x, y) : x, y ∈ R, x ≥ y}.
R is a binary relation on R;
R is reflexive: ∵ ∀x ∈ Z, x ≥ x;
R is not irreflexive;
R is not symmetric; ∵ (2, 1) ∈ R, (1, 2) ̸∈ R;
EXAMPLE 9
Let R = {(x, y) : x, y ∈ Z, x < y}.
R is a binary relation on Z;
R is not reflexive: ∵ ∀x ∈ Z, x ̸< x;
R is irreflexive; ∵ ∀x ∈ Z, x ̸< x;
R is not symmetric; ∵ ∀x ∈ Z, if x < y then y < x is not true;
R is antisymmetric: the reason is trivial that the condition is false;
R is transitive: ∵ x < y, y < z ⇒ x < z.
EXAMPLE 10
Let R = {(x, y) : x, y ∈ R, x ≥ y}.
R is a binary relation on R;
R is reflexive: ∵ ∀x ∈ Z, x ≥ x;
R is not irreflexive;
R is not symmetric; ∵ (2, 1) ∈ R, (1, 2) ̸∈ R;
R is antisymmetric: ∵ x ≥ y, y ≥ x ⇒ x = y;
R is transitive: ∵ x ≥ y, y ≥ z ⇒ x ≥ z.
R is transitive: ∵ x ≥ y, y ≥ z ⇒ x ≥ z.
EXAMPLE 11
Let S be a set and let X = 2S = {A : A ⊆ S}.
Define R = {(A, B) : A, B ∈ X, A ⊆ B}.
R is transitive: ∵ x ≥ y, y ≥ z ⇒ x ≥ z.
EXAMPLE 11
Let S be a set and let X = 2S = {A : A ⊆ S}.
Define R = {(A, B) : A, B ∈ X, A ⊆ B}.
R is transitive: ∵ x ≥ y, y ≥ z ⇒ x ≥ z.
EXAMPLE 11
Let S be a set and let X = 2S = {A : A ⊆ S}.
Define R = {(A, B) : A, B ∈ X, A ⊆ B}.
Then
R is transitive: ∵ x ≥ y, y ≥ z ⇒ x ≥ z.
EXAMPLE 11
Let S be a set and let X = 2S = {A : A ⊆ S}.
Define R = {(A, B) : A, B ∈ X, A ⊆ B}.
Then
R is a binary relation on X;
R is transitive: ∵ x ≥ y, y ≥ z ⇒ x ≥ z.
EXAMPLE 11
Let S be a set and let X = 2S = {A : A ⊆ S}.
Define R = {(A, B) : A, B ∈ X, A ⊆ B}.
Then
R is a binary relation on X;
R is reflexive: A ⊆ A;
R is transitive: ∵ x ≥ y, y ≥ z ⇒ x ≥ z.
EXAMPLE 11
Let S be a set and let X = 2S = {A : A ⊆ S}.
Define R = {(A, B) : A, B ∈ X, A ⊆ B}.
Then
R is a binary relation on X;
R is reflexive: A ⊆ A;
R is not irreflexive;
R is transitive: ∵ x ≥ y, y ≥ z ⇒ x ≥ z.
EXAMPLE 11
Let S be a set and let X = 2S = {A : A ⊆ S}.
Define R = {(A, B) : A, B ∈ X, A ⊆ B}.
Then
R is a binary relation on X;
R is reflexive: A ⊆ A;
R is not irreflexive;
R is not symmetric;
R is transitive: ∵ x ≥ y, y ≥ z ⇒ x ≥ z.
EXAMPLE 11
Let S be a set and let X = 2S = {A : A ⊆ S}.
Define R = {(A, B) : A, B ∈ X, A ⊆ B}.
Then
R is a binary relation on X;
R is reflexive: A ⊆ A;
R is not irreflexive;
R is not symmetric;
R is antisymmetric: by the definition of set equality;
R is transitive: ∵ x ≥ y, y ≥ z ⇒ x ≥ z.
EXAMPLE 11
Let S be a set and let X = 2S = {A : A ⊆ S}.
Define R = {(A, B) : A, B ∈ X, A ⊆ B}.
Then
R is a binary relation on X;
R is reflexive: A ⊆ A;
R is not irreflexive;
R is not symmetric;
R is antisymmetric: by the definition of set equality;
R is transitive: A ⊆ B, B ⊆ C ⇒ A ⊆ C.
EXAMPLE 12
Let R = {(x, y) : x, y ∈ Z, 2 | x − y}.
EXAMPLE 12
Let R = {(x, y) : x, y ∈ Z, 2 | x − y}.
EXAMPLE 12
Let R = {(x, y) : x, y ∈ Z, 2 | x − y}.
Then
EXAMPLE 12
Let R = {(x, y) : x, y ∈ Z, 2 | x − y}.
Then
R is a binary relation on Z;
EXAMPLE 12
Let R = {(x, y) : x, y ∈ Z, 2 | x − y}.
Then
R is a binary relation on Z;
R is reflexive: for every x ∈ Z, 2 | 0 = x − x;
EXAMPLE 12
Let R = {(x, y) : x, y ∈ Z, 2 | x − y}.
Then
R is a binary relation on Z;
R is reflexive: for every x ∈ Z, 2 | 0 = x − x;
R is not irreflexive;
EXAMPLE 12
Let R = {(x, y) : x, y ∈ Z, 2 | x − y}.
Then
R is a binary relation on Z;
R is reflexive: for every x ∈ Z, 2 | 0 = x − x;
R is not irreflexive;
R is symmetric: if 2 | x − y then 2 | y − x = −(x − y);
EXAMPLE 12
Let R = {(x, y) : x, y ∈ Z, 2 | x − y}.
Then
R is a binary relation on Z;
R is reflexive: for every x ∈ Z, 2 | 0 = x − x;
R is not irreflexive;
R is symmetric: if 2 | x − y then 2 | y − x = −(x − y);
R is not antisymmetric: 2 | 3 − 1 and 2 | 1 − 3 but 3 ̸= 1;
EXAMPLE 12
Let R = {(x, y) : x, y ∈ Z, 2 | x − y}.
Then
R is a binary relation on Z;
R is reflexive: for every x ∈ Z, 2 | 0 = x − x;
R is not irreflexive;
R is symmetric: if 2 | x − y then 2 | y − x = −(x − y);
R is not antisymmetric: 2 | 3 − 1 and 2 | 1 − 3 but 3 ̸= 1;
R is transitive: 2 | x − y, 2 | y − z ⇒ 2 | x − z = (x − y) + (y − z).
EXAMPLE 13
Let R = {(x, y) : |x − y| < 1}.
EXAMPLE 13
Let R = {(x, y) : |x − y| < 1}.
EXAMPLE 13
Let R = {(x, y) : |x − y| < 1}.
Then
EXAMPLE 13
Let R = {(x, y) : |x − y| < 1}.
Then
R is a binary relation on R;
EXAMPLE 13
Let R = {(x, y) : |x − y| < 1}.
Then
R is a binary relation on R;
R is reflexive: |x − x| = 0 < 1;
EXAMPLE 13
Let R = {(x, y) : |x − y| < 1}.
Then
R is a binary relation on R;
R is reflexive: |x − x| = 0 < 1;
R is not irreflexive;
EXAMPLE 13
Let R = {(x, y) : |x − y| < 1}.
Then
R is a binary relation on R;
R is reflexive: |x − x| = 0 < 1;
R is not irreflexive;
R is symmetric: |x − y| = |y − x|;
EXAMPLE 13
Let R = {(x, y) : |x − y| < 1}.
Then
R is a binary relation on R;
R is reflexive: |x − x| = 0 < 1;
R is not irreflexive;
R is symmetric: |x − y| = |y − x|;
R is not antisymmetric;
EXAMPLE 13
Let R = {(x, y) : |x − y| < 1}.
Then
R is a binary relation on R;
R is reflexive: |x − x| = 0 < 1;
R is not irreflexive;
R is symmetric: |x − y| = |y − x|;
R is not antisymmetric;
R is not transitive: x = 0, y = 0.9, z = 1.8.
Equivalence Relations
Definition
Equivalence Relations
Definition Let X be a set and R be a binary relation on X. If R is reflexive, symmetric and
transitive, then R is called an equivalence relation on X.
Equivalence Relations
Definition Let X be a set and R be a binary relation on X. If R is reflexive, symmetric and
transitive, then R is called an equivalence relation on X.
Subset
x̄ = [x] = {y ∈ X : (x, y) ∈ R}
is called (the) equivalence class of x.
Equivalence Relations
Definition Let X be a set and R be a binary relation on X. If R is reflexive, symmetric and
transitive, then R is called an equivalence relation on X.
Subset
x̄ = [x] = {y ∈ X : (x, y) ∈ R}
is called (the) equivalence class of x.
Denote
X/R = {x̄ : x ∈ X}.
X/R is called the quotient set of X by the equivalence relation R.
EXAMPLE 14
R = {(x, y) : 2 | x − y} is an equivalence relation on Z.
Equivalence Relations
Definition Let X be a set and R be a binary relation on X. If R is reflexive, symmetric and
transitive, then R is called an equivalence relation on X.
Subset
x̄ = [x] = {y ∈ X : (x, y) ∈ R}
is called (the) equivalence class of x.
Denote
X/R = {x̄ : x ∈ X}.
X/R is called the quotient set of X by the equivalence relation R.
EXAMPLE 14
R = {(x, y) : 2 | x − y} is an equivalence relation on Z.
Equivalence Relations
Definition Let X be a set and R be a binary relation on X. If R is reflexive, symmetric and
transitive, then R is called an equivalence relation on X.
Subset
x̄ = [x] = {y ∈ X : (x, y) ∈ R}
is called (the) equivalence class of x.
Denote
X/R = {x̄ : x ∈ X}.
X/R is called the quotient set of X by the equivalence relation R.
EXAMPLE 14
R = {(x, y) : 2 | x − y} is an equivalence relation on Z.
Other examples seen in the last section are not examples of an equivalence relation.
EXAMPLE 15
Let X be the set of all straight lines in the Euclidean plane.
EXAMPLE 15
Let X be the set of all straight lines in the Euclidean plane.
EXAMPLE 15
Let X be the set of all straight lines in the Euclidean plane.
For l, m ∈ X, if l = m or l ∥ m then we say (l, m) ∈ R. Then it may be routinely verified
that R is an equivalence relation on X.
EXAMPLE 16
Let X ⊆ Z.
EXAMPLE 15
Let X be the set of all straight lines in the Euclidean plane.
For l, m ∈ X, if l = m or l ∥ m then we say (l, m) ∈ R. Then it may be routinely verified
that R is an equivalence relation on X.
EXAMPLE 16
Let X ⊆ Z.
EXAMPLE 15
Let X be the set of all straight lines in the Euclidean plane.
For l, m ∈ X, if l = m or l ∥ m then we say (l, m) ∈ R. Then it may be routinely verified
that R is an equivalence relation on X.
EXAMPLE 16
Let X ⊆ Z. Define
R = {(x, y) : x, y ∈ X, 3 | x + 2y}.
EXAMPLE 15
Let X be the set of all straight lines in the Euclidean plane.
For l, m ∈ X, if l = m or l ∥ m then we say (l, m) ∈ R. Then it may be routinely verified
that R is an equivalence relation on X.
EXAMPLE 16
Let X ⊆ Z. Define
R = {(x, y) : x, y ∈ X, 3 | x + 2y}.

Then R is a binary relation on X. We verify

EXAMPLE 15
Let X be the set of all straight lines in the Euclidean plane.
For l, m ∈ X, if l = m or l ∥ m then we say (l, m) ∈ R. Then it may be routinely verified
that R is an equivalence relation on X.
EXAMPLE 16
Let X ⊆ Z. Define
R = {(x, y) : x, y ∈ X, 3 | x + 2y}.

Then R is a binary relation on X. We verify

R is reflexive: for every x ∈ X, 3 | 3x = x + 2x;
EXAMPLE 15
Let X be the set of all straight lines in the Euclidean plane.
For l, m ∈ X, if l = m or l ∥ m then we say (l, m) ∈ R. Then it may be routinely verified
that R is an equivalence relation on X.
EXAMPLE 16
Let X ⊆ Z. Define
R = {(x, y) : x, y ∈ X, 3 | x + 2y}.

Then R is a binary relation on X. We verify

R is reflexive: for every x ∈ X, 3 | 3x = x + 2x;
R is symmetric: for x, y ∈ X, suppose (x, y) ∈ R, that is, 3 | x + 2y; then x + 2y = 3k,
k ∈ Z; then x = 3k − 2y, and y + 2x = 3(2k − y) and hence 3 | y + 2x; hence (y, x) ∈ R;
EXAMPLE 15
Let X be the set of all straight lines in the Euclidean plane.
For l, m ∈ X, if l = m or l ∥ m then we say (l, m) ∈ R. Then it may be routinely verified
that R is an equivalence relation on X.
EXAMPLE 16
Let X ⊆ Z. Define
R = {(x, y) : x, y ∈ X, 3 | x + 2y}.

Then R is a binary relation on X. We verify

R is reflexive: for every x ∈ X, 3 | 3x = x + 2x;
R is symmetric: for x, y ∈ X, suppose (x, y) ∈ R, that is, 3 | x + 2y; then x + 2y = 3k,
k ∈ Z; then x = 3k − 2y, and y + 2x = 3(2k − y) and hence 3 | y + 2x; hence (y, x) ∈ R;
R is transitive: Let x, y, z ∈ X and suppose (x, y), (y, z) ∈ R. Then x + 2y = 3k and
y + 2z = 3l with k, l ∈ Z. Then
(x + 2y) + (y + 2z) = 3(k + l).
 (x + 2y) + (y + 2z) = 3(k + l).
Hence
x + 2z = 3(k + l − y).
 (x + 2y) + (y + 2z) = 3(k + l).
Hence
x + 2z = 3(k + l − y).
Hence 3 | x + 2z and therefore (x, z) ∈ R.
 (x + 2y) + (y + 2z) = 3(k + l).
Hence
x + 2z = 3(k + l − y).
Hence 3 | x + 2z and therefore (x, z) ∈ R.
In summary, R is an equivalence relation on X.
 (x + 2y) + (y + 2z) = 3(k + l).
Hence
x + 2z = 3(k + l − y).
Hence 3 | x + 2z and therefore (x, z) ∈ R.
In summary, R is an equivalence relation on X.
EXAMPLE 17
For the equivalence relation

R = {(x, y) : 2 | x − y}

on Z considered above, we write down 5̄.

 (x + 2y) + (y + 2z) = 3(k + l).
Hence
x + 2z = 3(k + l − y).
Hence 3 | x + 2z and therefore (x, z) ∈ R.
In summary, R is an equivalence relation on X.
EXAMPLE 17
For the equivalence relation

R = {(x, y) : 2 | x − y}

on Z considered above, we write down 5̄.

 (x + 2y) + (y + 2z) = 3(k + l).
Hence
x + 2z = 3(k + l − y).
Hence 3 | x + 2z and therefore (x, z) ∈ R.
In summary, R is an equivalence relation on X.
EXAMPLE 17
For the equivalence relation

R = {(x, y) : 2 | x − y}

on Z considered above, we write down 5̄.

By the definition of 5̄, x ∈ 5̄ if and only if 2 | x − 5.
 (x + 2y) + (y + 2z) = 3(k + l).
Hence
x + 2z = 3(k + l − y).
Hence 3 | x + 2z and therefore (x, z) ∈ R.
In summary, R is an equivalence relation on X.
EXAMPLE 17
For the equivalence relation

R = {(x, y) : 2 | x − y}

on Z considered above, we write down 5̄.

By the definition of 5̄, x ∈ 5̄ if and only if 2 | x − 5.
That is x − 5 = 2k with k ∈ Z.
 (x + 2y) + (y + 2z) = 3(k + l).
Hence
x + 2z = 3(k + l − y).
Hence 3 | x + 2z and therefore (x, z) ∈ R.
In summary, R is an equivalence relation on X.
EXAMPLE 17
For the equivalence relation

R = {(x, y) : 2 | x − y}

on Z considered above, we write down 5̄.

By the definition of 5̄, x ∈ 5̄ if and only if 2 | x − 5.
That is x − 5 = 2k with k ∈ Z.
Hence
5̄ = [5] = {2k + 5 : k ∈ Z}.
EXAMPLE 18
We also have
· · · = [−3] = [−1] = [1] = [3] = [5] = · · · .
and
X/R = {0̄, 1̄}.
EXAMPLE 18
We also have
· · · = [−3] = [−1] = [1] = [3] = [5] = · · · .
and
X/R = {0̄, 1̄}.
EXAMPLE 18
We also have
· · · = [−3] = [−1] = [1] = [3] = [5] = · · · .
and
X/R = {0̄, 1̄}.

EXAMPLE 19
Let X be the set of straight lines in the Euclidean plane and let

R = {(l, m) : l, m ∈ X, l = m or l ∥ m}.

Let l be the line y = 2x + 3.

EXAMPLE 18
We also have
· · · = [−3] = [−1] = [1] = [3] = [5] = · · · .
and
X/R = {0̄, 1̄}.

EXAMPLE 19
Let X be the set of straight lines in the Euclidean plane and let

R = {(l, m) : l, m ∈ X, l = m or l ∥ m}.

Let l be the line y = 2x + 3.

EXAMPLE 18
We also have
· · · = [−3] = [−1] = [1] = [3] = [5] = · · · .
and
X/R = {0̄, 1̄}.

EXAMPLE 19
Let X be the set of straight lines in the Euclidean plane and let

R = {(l, m) : l, m ∈ X, l = m or l ∥ m}.

Let l be the line y = 2x + 3.

We determine l̄.
EXAMPLE 18
We also have
· · · = [−3] = [−1] = [1] = [3] = [5] = · · · .
and
X/R = {0̄, 1̄}.

EXAMPLE 19
Let X be the set of straight lines in the Euclidean plane and let

R = {(l, m) : l, m ∈ X, l = m or l ∥ m}.

Let l be the line y = 2x + 3.

We determine l̄.
Two lines are parallel if and only if they are both vertical or their slopes are equal;
EXAMPLE 18
We also have
· · · = [−3] = [−1] = [1] = [3] = [5] = · · · .
and
X/R = {0̄, 1̄}.

EXAMPLE 19
Let X be the set of straight lines in the Euclidean plane and let

R = {(l, m) : l, m ∈ X, l = m or l ∥ m}.

Let l be the line y = 2x + 3.

We determine l̄.
Two lines are parallel if and only if they are both vertical or their slopes are equal;
(l, m) ∈ R if and only if m has slope 2;
Hence m has equation y = 2x + c.
Hence m has equation y = 2x + c.
Hence
[l] = {m : y = 2x + c, c ∈ R}.
Hence m has equation y = 2x + c.
Hence
[l] = {m : y = 2x + c, c ∈ R}.

EXAMPLE 20
Let X ⊆ Z and define
R = {(x, y) : x, y ∈ Z, 3 | x + 2y}.
Hence m has equation y = 2x + c.
Hence
[l] = {m : y = 2x + c, c ∈ R}.

EXAMPLE 20
Let X ⊆ Z and define
R = {(x, y) : x, y ∈ Z, 3 | x + 2y}.
Hence m has equation y = 2x + c.
Hence
[l] = {m : y = 2x + c, c ∈ R}.

EXAMPLE 20
Let X ⊆ Z and define
R = {(x, y) : x, y ∈ Z, 3 | x + 2y}.

We consider the case where

X = {−6, −5, −2, −1, 0, 1, 3, 5, 7}.

Hence m has equation y = 2x + c.
Hence
[l] = {m : y = 2x + c, c ∈ R}.

EXAMPLE 20
Let X ⊆ Z and define
R = {(x, y) : x, y ∈ Z, 3 | x + 2y}.

We consider the case where

X = {−6, −5, −2, −1, 0, 1, 3, 5, 7}.

Then
Hence m has equation y = 2x + c.
Hence
[l] = {m : y = 2x + c, c ∈ R}.

EXAMPLE 20
Let X ⊆ Z and define
R = {(x, y) : x, y ∈ Z, 3 | x + 2y}.

We consider the case where

X = {−6, −5, −2, −1, 0, 1, 3, 5, 7}.

Then
[−6] = {−6, 0, 3} = [0] = [3].
Hence m has equation y = 2x + c.
Hence
[l] = {m : y = 2x + c, c ∈ R}.

EXAMPLE 20
Let X ⊆ Z and define
R = {(x, y) : x, y ∈ Z, 3 | x + 2y}.

We consider the case where

X = {−6, −5, −2, −1, 0, 1, 3, 5, 7}.

Then
[−6] = {−6, 0, 3} = [0] = [3].
[−5] = [−2] = [1] = [7] = {−5, −2, 1, 7}.
Hence m has equation y = 2x + c.
Hence
[l] = {m : y = 2x + c, c ∈ R}.

EXAMPLE 20
Let X ⊆ Z and define
R = {(x, y) : x, y ∈ Z, 3 | x + 2y}.

We consider the case where

X = {−6, −5, −2, −1, 0, 1, 3, 5, 7}.

Then
[−6] = {−6, 0, 3} = [0] = [3].
[−5] = [−2] = [1] = [7] = {−5, −2, 1, 7}.
[−1] = {−1, 5} = [5].
THEOREM 2
Let X be a set and R be an equivalence relation on X. Then X/R is a partition of X.
THEOREM 2
Let X be a set and R be an equivalence relation on X. Then X/R is a partition of X.
THEOREM 2
Let X be a set and R be an equivalence relation on X. Then X/R is a partition of X.

Proof.
THEOREM 2
Let X be a set and R be an equivalence relation on X. Then X/R is a partition of X.

Proof. For x, y ∈ X, [x] = [y] if and only if (x, y) ∈ R.

THEOREM 2
Let X be a set and R be an equivalence relation on X. Then X/R is a partition of X.

Proof. For x, y ∈ X, [x] = [y] if and only if (x, y) ∈ R. We prove this first.
THEOREM 2
Let X be a set and R be an equivalence relation on X. Then X/R is a partition of X.

Proof. For x, y ∈ X, [x] = [y] if and only if (x, y) ∈ R. We prove this first.
If [x] = [y] then y ∈ [y] = [x] and (x, y) ∈ R.
THEOREM 2
Let X be a set and R be an equivalence relation on X. Then X/R is a partition of X.

Proof. For x, y ∈ X, [x] = [y] if and only if (x, y) ∈ R. We prove this first.
If [x] = [y] then y ∈ [y] = [x] and (x, y) ∈ R.
Suppose then that (x, y) ∈ R. Let z ∈ [x].
THEOREM 2
Let X be a set and R be an equivalence relation on X. Then X/R is a partition of X.

Proof. For x, y ∈ X, [x] = [y] if and only if (x, y) ∈ R. We prove this first.
If [x] = [y] then y ∈ [y] = [x] and (x, y) ∈ R.
Suppose then that (x, y) ∈ R. Let z ∈ [x].
Then (x, z) ∈ R. Since R is symmetric, (y, x) ∈ R.
THEOREM 2
Let X be a set and R be an equivalence relation on X. Then X/R is a partition of X.

Proof. For x, y ∈ X, [x] = [y] if and only if (x, y) ∈ R. We prove this first.
If [x] = [y] then y ∈ [y] = [x] and (x, y) ∈ R.
Suppose then that (x, y) ∈ R. Let z ∈ [x].
Then (x, z) ∈ R. Since R is symmetric, (y, x) ∈ R.
Hence by transitivity (y, z) ∈ R. Hence z ∈ [y].
THEOREM 2
Let X be a set and R be an equivalence relation on X. Then X/R is a partition of X.

Proof. For x, y ∈ X, [x] = [y] if and only if (x, y) ∈ R. We prove this first.
If [x] = [y] then y ∈ [y] = [x] and (x, y) ∈ R.
Suppose then that (x, y) ∈ R. Let z ∈ [x].
Then (x, z) ∈ R. Since R is symmetric, (y, x) ∈ R.
Hence by transitivity (y, z) ∈ R. Hence z ∈ [y].
This proves [x] ⊆ [y].
THEOREM 2
Let X be a set and R be an equivalence relation on X. Then X/R is a partition of X.

Proof. For x, y ∈ X, [x] = [y] if and only if (x, y) ∈ R. We prove this first.
If [x] = [y] then y ∈ [y] = [x] and (x, y) ∈ R.
Suppose then that (x, y) ∈ R. Let z ∈ [x].
Then (x, z) ∈ R. Since R is symmetric, (y, x) ∈ R.
Hence by transitivity (y, z) ∈ R. Hence z ∈ [y].
This proves [x] ⊆ [y].
The proof of [y] ⊆ [x] is similar.
THEOREM 2
Let X be a set and R be an equivalence relation on X. Then X/R is a partition of X.

Proof. For x, y ∈ X, [x] = [y] if and only if (x, y) ∈ R. We prove this first.
If [x] = [y] then y ∈ [y] = [x] and (x, y) ∈ R.
Suppose then that (x, y) ∈ R. Let z ∈ [x].
Then (x, z) ∈ R. Since R is symmetric, (y, x) ∈ R.
Hence by transitivity (y, z) ∈ R. Hence z ∈ [y].
This proves [x] ⊆ [y].
The proof of [y] ⊆ [x] is similar.
Hence [x] = [y].
THEOREM 2
Let X be a set and R be an equivalence relation on X. Then X/R is a partition of X.

Proof. For x, y ∈ X, [x] = [y] if and only if (x, y) ∈ R. We prove this first.
If [x] = [y] then y ∈ [y] = [x] and (x, y) ∈ R.
Suppose then that (x, y) ∈ R. Let z ∈ [x].
Then (x, z) ∈ R. Since R is symmetric, (y, x) ∈ R.
Hence by transitivity (y, z) ∈ R. Hence z ∈ [y].
This proves [x] ⊆ [y].
The proof of [y] ⊆ [x] is similar.
Hence [x] = [y].
This proves the first line.
Let x ∈ X.
Let x ∈ X.
Since x ∈ [x], [x] ̸= ∅ and x is an element of the union of equivalence classes.
Let x ∈ X.
Since xS∈ [x], [x] ̸= ∅ and x is an element
S of the union of equivalence classes.
Since [x] ⊆ X, we have X = [x].
x∈X x∈X
Let x ∈ X.
Since xS∈ [x], [x] ̸= ∅ and x is an element
S of the union of equivalence classes.
Since [x] ⊆ X, we have X = [x].
x∈X x∈X
It remains only to prove that two different equivalence classes are disjoint.
Let x ∈ X.
Since xS∈ [x], [x] ̸= ∅ and x is an element
S of the union of equivalence classes.
Since [x] ⊆ X, we have X = [x].
x∈X x∈X
It remains only to prove that two different equivalence classes are disjoint.
Suppose that [x] ∩ [y] ̸= ∅.
Let x ∈ X.
Since xS∈ [x], [x] ̸= ∅ and x is an element
S of the union of equivalence classes.
Since [x] ⊆ X, we have X = [x].
x∈X x∈X
It remains only to prove that two different equivalence classes are disjoint.
Suppose that [x] ∩ [y] ̸= ∅.
Then let z ∈ [x] ∩ [y].
Let x ∈ X.
Since xS∈ [x], [x] ̸= ∅ and x is an element
S of the union of equivalence classes.
Since [x] ⊆ X, we have X = [x].
x∈X x∈X
It remains only to prove that two different equivalence classes are disjoint.
Suppose that [x] ∩ [y] ̸= ∅.
Then let z ∈ [x] ∩ [y].
Then z ∈ [x] and z ∈ [y].
Let x ∈ X.
Since xS∈ [x], [x] ̸= ∅ and x is an element
S of the union of equivalence classes.
Since [x] ⊆ X, we have X = [x].
x∈X x∈X
It remains only to prove that two different equivalence classes are disjoint.
Suppose that [x] ∩ [y] ̸= ∅.
Then let z ∈ [x] ∩ [y].
Then z ∈ [x] and z ∈ [y].
Hence (x, z), (y, z) ∈ R.
Let x ∈ X.
Since xS∈ [x], [x] ̸= ∅ and x is an element
S of the union of equivalence classes.
Since [x] ⊆ X, we have X = [x].
x∈X x∈X
It remains only to prove that two different equivalence classes are disjoint.
Suppose that [x] ∩ [y] ̸= ∅.
Then let z ∈ [x] ∩ [y].
Then z ∈ [x] and z ∈ [y].
Hence (x, z), (y, z) ∈ R.
By symmetry, (x, z), (z, y) ∈ R.
Let x ∈ X.
Since xS∈ [x], [x] ̸= ∅ and x is an element
S of the union of equivalence classes.
Since [x] ⊆ X, we have X = [x].
x∈X x∈X
It remains only to prove that two different equivalence classes are disjoint.
Suppose that [x] ∩ [y] ̸= ∅.
Then let z ∈ [x] ∩ [y].
Then z ∈ [x] and z ∈ [y].
Hence (x, z), (y, z) ∈ R.
By symmetry, (x, z), (z, y) ∈ R.
By transitivity, (x, y) ∈ R.
Let x ∈ X.
Since xS∈ [x], [x] ̸= ∅ and x is an element
S of the union of equivalence classes.
Since [x] ⊆ X, we have X = [x].
x∈X x∈X
It remains only to prove that two different equivalence classes are disjoint.
Suppose that [x] ∩ [y] ̸= ∅.
Then let z ∈ [x] ∩ [y].
Then z ∈ [x] and z ∈ [y].
Hence (x, z), (y, z) ∈ R.
By symmetry, (x, z), (z, y) ∈ R.
By transitivity, (x, y) ∈ R.
By the first line of this proof, [x] = [y].
Let x ∈ X.
Since xS∈ [x], [x] ̸= ∅ and x is an element
S of the union of equivalence classes.
Since [x] ⊆ X, we have X = [x].
x∈X x∈X
It remains only to prove that two different equivalence classes are disjoint.
Suppose that [x] ∩ [y] ̸= ∅.
Then let z ∈ [x] ∩ [y].
Then z ∈ [x] and z ∈ [y].
Hence (x, z), (y, z) ∈ R.
By symmetry, (x, z), (z, y) ∈ R.
By transitivity, (x, y) ∈ R.
By the first line of this proof, [x] = [y].
Equivalently, if [x] ̸= [y] then [x] ∩ [y] = ∅.
Let x ∈ X.
Since xS∈ [x], [x] ̸= ∅ and x is an element
S of the union of equivalence classes.
Since [x] ⊆ X, we have X = [x].
x∈X x∈X
It remains only to prove that two different equivalence classes are disjoint.
Suppose that [x] ∩ [y] ̸= ∅.
Then let z ∈ [x] ∩ [y].
Then z ∈ [x] and z ∈ [y].
Hence (x, z), (y, z) ∈ R.
By symmetry, (x, z), (z, y) ∈ R.
By transitivity, (x, y) ∈ R.
By the first line of this proof, [x] = [y].
Equivalently, if [x] ̸= [y] then [x] ∩ [y] = ∅.
In summary, we have proved that X/R is a partition of X.
Let x ∈ X.
Since xS∈ [x], [x] ̸= ∅ and x is an element
S of the union of equivalence classes.
Since [x] ⊆ X, we have X = [x].
x∈X x∈X
It remains only to prove that two different equivalence classes are disjoint.
Suppose that [x] ∩ [y] ̸= ∅.
Then let z ∈ [x] ∩ [y].
Then z ∈ [x] and z ∈ [y].
Hence (x, z), (y, z) ∈ R.
By symmetry, (x, z), (z, y) ∈ R.
By transitivity, (x, y) ∈ R.
By the first line of this proof, [x] = [y].
Equivalently, if [x] ̸= [y] then [x] ∩ [y] = ∅.
In summary, we have proved that X/R is a partition of X. 2
THEOREM 3
Let X be a set and P be a partition of X. Then there exists a mapping f : X → Y with
P = {f −1 (y) : y ∈ Y, f −1 (y) ̸= ∅}.
THEOREM 3
Let X be a set and P be a partition of X. Then there exists a mapping f : X → Y with
P = {f −1 (y) : y ∈ Y, f −1 (y) ̸= ∅}.
THEOREM 3
Let X be a set and P be a partition of X. Then there exists a mapping f : X → Y with
P = {f −1 (y) : y ∈ Y, f −1 (y) ̸= ∅}.

Proof.
Let X be a set and P be a partition of X.
THEOREM 3
Let X be a set and P be a partition of X. Then there exists a mapping f : X → Y with
P = {f −1 (y) : y ∈ Y, f −1 (y) ̸= ∅}.

Proof.
Let X be a set and P be a partition of X.
THEOREM 3
Let X be a set and P be a partition of X. Then there exists a mapping f : X → Y with
P = {f −1 (y) : y ∈ Y, f −1 (y) ̸= ∅}.

Proof.
Let X be a set and P be a partition of X. Let Y = P and f : X → Y be defined such that
f (x) = A if A ∈ P and x ∈ A.
THEOREM 3
Let X be a set and P be a partition of X. Then there exists a mapping f : X → Y with
P = {f −1 (y) : y ∈ Y, f −1 (y) ̸= ∅}.

Proof.
Let X be a set and P be a partition of X. Let Y = P and f : X → Y be defined such that
f (x) = A if A ∈ P and x ∈ A. We show that f : X → Y is a mapping.
THEOREM 3
Let X be a set and P be a partition of X. Then there exists a mapping f : X → Y with
P = {f −1 (y) : y ∈ Y, f −1 (y) ̸= ∅}.

Proof.
Let X be a set and P be a partition of X. Let Y = P and f : X → Y be defined such that
f (x) = A if A ∈ P and x ∈ A. We show that f : X → Y is a mapping. For every x ∈ X
there exists A ∈ P with x ∈ A.
THEOREM 3
Let X be a set and P be a partition of X. Then there exists a mapping f : X → Y with
P = {f −1 (y) : y ∈ Y, f −1 (y) ̸= ∅}.

Proof.
Let X be a set and P be a partition of X. Let Y = P and f : X → Y be defined such that
f (x) = A if A ∈ P and x ∈ A. We show that f : X → Y is a mapping. For every x ∈ X
there exists A ∈ P with x ∈ A. By the definition of f , f (x) = y, y ∈ Y.
THEOREM 3
Let X be a set and P be a partition of X. Then there exists a mapping f : X → Y with
P = {f −1 (y) : y ∈ Y, f −1 (y) ̸= ∅}.

Proof.
Let X be a set and P be a partition of X. Let Y = P and f : X → Y be defined such that
f (x) = A if A ∈ P and x ∈ A. We show that f : X → Y is a mapping. For every x ∈ X
there exists A ∈ P with x ∈ A. By the definition of f , f (x) = y, y ∈ Y. Since y is
uniquely determined by f , f satisfies condition (2) in the definition of a mapping.

THEOREM 4
Let X, Y be sets and f : X → Y any mapping. Then there exists a an equivalence relation
R on X such that X/R = {f −1 (y) : y ∈ Y, f −1 (y) ̸= ∅}.
Proof.
Proof.
Let X, Y be sets and f : X → Y any mapping.
Proof.
Let X, Y be sets and f : X → Y any mapping.
Define
R = {(w, x) : ∃y ∈ Y, f (w) = f (x)}.
Proof.
Let X, Y be sets and f : X → Y any mapping.
Define
R = {(w, x) : ∃y ∈ Y, f (w) = f (x)}.

Since R ⊆ X × X, R is a binary relation on X.

Proof.
Let X, Y be sets and f : X → Y any mapping.
Define
R = {(w, x) : ∃y ∈ Y, f (w) = f (x)}.

Since R ⊆ X × X, R is a binary relation on X.

For every x ∈ X, since f (x) = f (x), we have (x, x) ∈ R and hence R is reflexive.
Proof.
Let X, Y be sets and f : X → Y any mapping.
Define
R = {(w, x) : ∃y ∈ Y, f (w) = f (x)}.

Since R ⊆ X × X, R is a binary relation on X.

For every x ∈ X, since f (x) = f (x), we have (x, x) ∈ R and hence R is reflexive.
Let u, v ∈ X and suppose that (u, v) ∈ R.
Proof.
Let X, Y be sets and f : X → Y any mapping.
Define
R = {(w, x) : ∃y ∈ Y, f (w) = f (x)}.

Since R ⊆ X × X, R is a binary relation on X.

For every x ∈ X, since f (x) = f (x), we have (x, x) ∈ R and hence R is reflexive.
Let u, v ∈ X and suppose that (u, v) ∈ R.
By the definition of R, f (u) = f (v).
Proof.
Let X, Y be sets and f : X → Y any mapping.
Define
R = {(w, x) : ∃y ∈ Y, f (w) = f (x)}.

Since R ⊆ X × X, R is a binary relation on X.

For every x ∈ X, since f (x) = f (x), we have (x, x) ∈ R and hence R is reflexive.
Let u, v ∈ X and suppose that (u, v) ∈ R.
By the definition of R, f (u) = f (v). Hence f (v) = f (u) and hence (v, u) ∈ R and R is
symmetric.
Proof.
Let X, Y be sets and f : X → Y any mapping.
Define
R = {(w, x) : ∃y ∈ Y, f (w) = f (x)}.

Since R ⊆ X × X, R is a binary relation on X.

For every x ∈ X, since f (x) = f (x), we have (x, x) ∈ R and hence R is reflexive.
Let u, v ∈ X and suppose that (u, v) ∈ R.
By the definition of R, f (u) = f (v). Hence f (v) = f (u) and hence (v, u) ∈ R and R is
symmetric.
Let u, v, w ∈ X and suppose that (u, v), (v, w) ∈ R.
Proof.
Let X, Y be sets and f : X → Y any mapping.
Define
R = {(w, x) : ∃y ∈ Y, f (w) = f (x)}.

Since R ⊆ X × X, R is a binary relation on X.

For every x ∈ X, since f (x) = f (x), we have (x, x) ∈ R and hence R is reflexive.
Let u, v ∈ X and suppose that (u, v) ∈ R.
By the definition of R, f (u) = f (v). Hence f (v) = f (u) and hence (v, u) ∈ R and R is
symmetric.
Let u, v, w ∈ X and suppose that (u, v), (v, w) ∈ R.
By the definition of R, f (u) = f (v) and f (v) = f (w).
Proof.
Let X, Y be sets and f : X → Y any mapping.
Define
R = {(w, x) : ∃y ∈ Y, f (w) = f (x)}.

Since R ⊆ X × X, R is a binary relation on X.

For every x ∈ X, since f (x) = f (x), we have (x, x) ∈ R and hence R is reflexive.
Let u, v ∈ X and suppose that (u, v) ∈ R.
By the definition of R, f (u) = f (v). Hence f (v) = f (u) and hence (v, u) ∈ R and R is
symmetric.
Let u, v, w ∈ X and suppose that (u, v), (v, w) ∈ R.
By the definition of R, f (u) = f (v) and f (v) = f (w). Hence f (u) = f (w) and hence
(u, w) ∈ R.
Proof.
Let X, Y be sets and f : X → Y any mapping.
Define
R = {(w, x) : ∃y ∈ Y, f (w) = f (x)}.

Since R ⊆ X × X, R is a binary relation on X.

For every x ∈ X, since f (x) = f (x), we have (x, x) ∈ R and hence R is reflexive.
Let u, v ∈ X and suppose that (u, v) ∈ R.
By the definition of R, f (u) = f (v). Hence f (v) = f (u) and hence (v, u) ∈ R and R is
symmetric.
Let u, v, w ∈ X and suppose that (u, v), (v, w) ∈ R.
By the definition of R, f (u) = f (v) and f (v) = f (w). Hence f (u) = f (w) and hence
(u, w) ∈ R. This shows that R is transitive.
Proof.
Let X, Y be sets and f : X → Y any mapping.
Define
R = {(w, x) : ∃y ∈ Y, f (w) = f (x)}.

Since R ⊆ X × X, R is a binary relation on X.

For every x ∈ X, since f (x) = f (x), we have (x, x) ∈ R and hence R is reflexive.
Let u, v ∈ X and suppose that (u, v) ∈ R.
By the definition of R, f (u) = f (v). Hence f (v) = f (u) and hence (v, u) ∈ R and R is
symmetric.
Let u, v, w ∈ X and suppose that (u, v), (v, w) ∈ R.
By the definition of R, f (u) = f (v) and f (v) = f (w). Hence f (u) = f (w) and hence
(u, w) ∈ R. This shows that R is transitive.
In summary, we have shown that R is an equivalence relation on X.
By the definition of R, for every x ∈ X,

[x] = f −1 (y), y ∈ Y.
By the definition of R, for every x ∈ X,

[x] = f −1 (y), y ∈ Y.

Hence
X/R = {f −1 (y) : y ∈ Y, f −1 (y) ̸= ∅}.

EXAMPLE 21 (Important)
Let n ≥ 1 be an integer. Consider

R = {(x, y) : x, y ∈ Z, n | y − x}.
By the definition of R, for every x ∈ X,

[x] = f −1 (y), y ∈ Y.

Hence
X/R = {f −1 (y) : y ∈ Y, f −1 (y) ̸= ∅}.

EXAMPLE 21 (Important)
Let n ≥ 1 be an integer. Consider

R = {(x, y) : x, y ∈ Z, n | y − x}.
By the definition of R, for every x ∈ X,

[x] = f −1 (y), y ∈ Y.

Hence
X/R = {f −1 (y) : y ∈ Y, f −1 (y) ̸= ∅}.

EXAMPLE 21 (Important)
Let n ≥ 1 be an integer. Consider

R = {(x, y) : x, y ∈ Z, n | y − x}.

We verify again that R is an equivalence relation on Z.

By the definition of R, for every x ∈ X,

[x] = f −1 (y), y ∈ Y.

Hence
X/R = {f −1 (y) : y ∈ Y, f −1 (y) ̸= ∅}.

EXAMPLE 21 (Important)
Let n ≥ 1 be an integer. Consider

R = {(x, y) : x, y ∈ Z, n | y − x}.

We verify again that R is an equivalence relation on Z.

R is reflexive: for every x ∈ Z, n | x − x;
By the definition of R, for every x ∈ X,

[x] = f −1 (y), y ∈ Y.

Hence
X/R = {f −1 (y) : y ∈ Y, f −1 (y) ̸= ∅}.

EXAMPLE 21 (Important)
Let n ≥ 1 be an integer. Consider

R = {(x, y) : x, y ∈ Z, n | y − x}.

We verify again that R is an equivalence relation on Z.

R is reflexive: for every x ∈ Z, n | x − x;
R is symmetric: if n | y − x then n | x − y = −(y − x);
By the definition of R, for every x ∈ X,

[x] = f −1 (y), y ∈ Y.

Hence
X/R = {f −1 (y) : y ∈ Y, f −1 (y) ̸= ∅}.

EXAMPLE 21 (Important)
Let n ≥ 1 be an integer. Consider

R = {(x, y) : x, y ∈ Z, n | y − x}.

We verify again that R is an equivalence relation on Z.

R is reflexive: for every x ∈ Z, n | x − x;
R is symmetric: if n | y − x then n | x − y = −(y − x);
R is transitive: if n | y − x and n | z − y, then n | z − x = (z − y) + (y − x);
By the definition of R, for every x ∈ X,

[x] = f −1 (y), y ∈ Y.

Hence
X/R = {f −1 (y) : y ∈ Y, f −1 (y) ̸= ∅}.

EXAMPLE 21 (Important)
Let n ≥ 1 be an integer. Consider

R = {(x, y) : x, y ∈ Z, n | y − x}.

We verify again that R is an equivalence relation on Z.

R is reflexive: for every x ∈ Z, n | x − x;
R is symmetric: if n | y − x then n | x − y = −(y − x);
R is transitive: if n | y − x and n | z − y, then n | z − x = (z − y) + (y − x);
The equivalence classes are residue classes:

0̄ = {kn : k ∈ Z} = {. . . , −2n, −n, 0, n, 2n, . . .}

The equivalence classes are residue classes:

0̄ = {kn : k ∈ Z} = {. . . , −2n, −n, 0, n, 2n, . . .}

1̄ = {kn + 1 : k ∈ Z} = {. . . , −n + 1, 1, n + 1, 2n + 1, . . .}
The equivalence classes are residue classes:

0̄ = {kn : k ∈ Z} = {. . . , −2n, −n, 0, n, 2n, . . .}

1̄ = {kn + 1 : k ∈ Z} = {. . . , −n + 1, 1, n + 1, 2n + 1, . . .}
2̄ = {kn + 2 : k ∈ Z} = {. . . , −n + 2, 2, n + 2, 2n + 2, . . .}
........................
The equivalence classes are residue classes:

0̄ = {kn : k ∈ Z} = {. . . , −2n, −n, 0, n, 2n, . . .}

1̄ = {kn + 1 : k ∈ Z} = {. . . , −n + 1, 1, n + 1, 2n + 1, . . .}
2̄ = {kn + 2 : k ∈ Z} = {. . . , −n + 2, 2, n + 2, 2n + 2, . . .}
........................
n − 1 = {kn − 1 : k ∈ Z} = {. . . , −n − 1, −1, n − 1, 2n − 1, . . .}.

EXAMPLE 22
For n = 2, we have an example done before with

Z = {0̄, 1̄}

where 0̄ is the set of all even integers, and 1̄ is the set of all odd integers.
For n = 3, we have
Z = {0̄, 1̄, 2̄}
where
0̄ = {3k : k ∈ Z}, 1̄ = {3k + 1 : k ∈ Z}, 2̄ = {3k + 2 : k ∈ Z}.
Questions
Questions
1. Let A = {1, 2, 3} and B = {2, 3, 4, 5}. Find
(1) A ∪ B. (2) A ∩ B. (3) A \ B.
(4) B \ A. (5) A + B. (6) A × B.
(7) B × A.
Questions
1. Let A = {1, 2, 3} and B = {2, 3, 4, 5}. Find
(1) A ∪ B. (2) A ∩ B. (3) A \ B.
(4) B \ A. (5) A + B. (6) A × B.
(7) B × A.
2. Write down that elements of the relation defined on {1, 2, 3, 4, 5} defined by
(a, b) ∈ R if |a − b| ≤ 1.
Questions
1. Let A = {1, 2, 3} and B = {2, 3, 4, 5}. Find
(1) A ∪ B. (2) A ∩ B. (3) A \ B.
(4) B \ A. (5) A + B. (6) A × B.
(7) B × A.
2. Write down that elements of the relation defined on {1, 2, 3, 4, 5} defined by
(a, b) ∈ R if |a − b| ≤ 1.
3. Determine whether given relations are reflexive, irreflexive, symmetric,
antisymmetric and transitive.
(1) R1 = {(1, 1), (1, 2), (2, 1), (3, 4), (4, 3)}.
(2) R2 = {(x, y) ∈ R2 : |x − y| ≥ 2}.
(3) R3 = {(x, y) ∈ Z2 : 2 | xy}.
Questions
1. Let A = {1, 2, 3} and B = {2, 3, 4, 5}. Find
(1) A ∪ B. (2) A ∩ B. (3) A \ B.
(4) B \ A. (5) A + B. (6) A × B.
(7) B × A.
2. Write down that elements of the relation defined on {1, 2, 3, 4, 5} defined by
(a, b) ∈ R if |a − b| ≤ 1.
3. Determine whether given relations are reflexive, irreflexive, symmetric,
antisymmetric and transitive.
(1) R1 = {(1, 1), (1, 2), (2, 1), (3, 4), (4, 3)}.
(2) R2 = {(x, y) ∈ R2 : |x − y| ≥ 2}.
(3) R3 = {(x, y) ∈ Z2 : 2 | xy}.
4. Let X ⊆ Z and R be defined by (x, y) ∈ R if and only if 2 | 3x − 5y. Prove that R is
an equivalence relation. If R is defined on X = {−5, −4, −2, 0, 1, 2, 3, 7, 9}, then
determined the equivalence classes.
Hints and Reference Answers
1. (1) {1, 2, 3, 4, 5}; (2) {2, 3}; (3) {1}; (4) {4, 5}; (5) {1, 4, 5};
(6) {(1, 2), (1, 3), (1, 4), (1, 5), (2, 2), (2, 3), (2, 4), (2, 5), (3, 2), (3, 3), (3, 4), (3, 5)}
(7) {(2, 1), (2, 2), (2, 3), (3, 1), (3, 2), (3, 3), (4, 1), (4, 2), (4, 3), (5, 1), (5, 2), (5, 3)}
Hints and Reference Answers
1. (1) {1, 2, 3, 4, 5}; (2) {2, 3}; (3) {1}; (4) {4, 5}; (5) {1, 4, 5};
(6) {(1, 2), (1, 3), (1, 4), (1, 5), (2, 2), (2, 3), (2, 4), (2, 5), (3, 2), (3, 3), (3, 4), (3, 5)}
(7) {(2, 1), (2, 2), (2, 3), (3, 1), (3, 2), (3, 3), (4, 1), (4, 2), (4, 3), (5, 1), (5, 2), (5, 3)}
2. {(1, 1), (1, 2), (2, 1), (2, 2), (2, 3), (3, 2)(3, 3), (3, 4), (4, 3), (4, 4), (4, 5), (5, 4)}.
Hints and Reference Answers
1. (1) {1, 2, 3, 4, 5}; (2) {2, 3}; (3) {1}; (4) {4, 5}; (5) {1, 4, 5};
(6) {(1, 2), (1, 3), (1, 4), (1, 5), (2, 2), (2, 3), (2, 4), (2, 5), (3, 2), (3, 3), (3, 4), (3, 5)}
(7) {(2, 1), (2, 2), (2, 3), (3, 1), (3, 2), (3, 3), (4, 1), (4, 2), (4, 3), (5, 1), (5, 2), (5, 3)}
2. {(1, 1), (1, 2), (2, 1), (2, 2), (2, 3), (3, 2)(3, 3), (3, 4), (4, 3), (4, 4), (4, 5), (5, 4)}.
3. (1) symmetric; (2) irreflexive and symmetric; (3) symmetric
Hints and Reference Answers
1. (1) {1, 2, 3, 4, 5}; (2) {2, 3}; (3) {1}; (4) {4, 5}; (5) {1, 4, 5};
(6) {(1, 2), (1, 3), (1, 4), (1, 5), (2, 2), (2, 3), (2, 4), (2, 5), (3, 2), (3, 3), (3, 4), (3, 5)}
(7) {(2, 1), (2, 2), (2, 3), (3, 1), (3, 2), (3, 3), (4, 1), (4, 2), (4, 3), (5, 1), (5, 2), (5, 3)}
2. {(1, 1), (1, 2), (2, 1), (2, 2), (2, 3), (3, 2)(3, 3), (3, 4), (4, 3), (4, 4), (4, 5), (5, 4)}.
3. (1) symmetric; (2) irreflexive and symmetric; (3) symmetric
4. X/R = {{−5, 3, 1, 7, 9}, {−4, −2, 0, 2}}.