Reading Quiz Section 7.3
1. True or False: a relation ∼ on a set X is reflexive if ∃x ∈ X such that x ∼ x.
2. Suppose that x, y, z ∈ X and ∼ is an equivalence relation on X. Express each of the following
assertions in terms of the properties satisfied by an equivalence relation.
(1) x ∈ [y] and y ∈ [z] =⇒ x ∈ [z]
(2) x ∈ [x]
(3) x ∈ [y] ⇐⇒ y ∈ [x]
(a) (1) is reflexivity, (2) is symmetry, and (3) is transitivity
(b) (1) is transitivity, (2) is symmetry, and (3) is reflexivity
(c) (1) is transitivity, (2) is reflexivity, and (3) is antisymmetry (Exercise 7.3.18)
(d) (1) is transitivity, (2) is reflexivity, and (3) is symmetry
3. Let R be an equivalence relation on a set X. Then R
−1
is an equivalence relation.
(a) never (b) sometimes (c) always
4. Which of the following statements are true? Select all that apply.
(a) If X is partitioned into the equivalence classes of some equivalence relation ∼, then each
element of X lies in some equivalence class [x].
(b) Suppose that X is partitioned into subsets and that x, y, z ∈ X. If x, y lie in the same
subset, and y, z lie in the same subset of the partition, then it is possible for x and z to lie
in different subsets.
(c)
∅, {a}, {b, c}
is a partition of {a, b, c}.
(d) Every subset in a partition of a set must have the same size.
5. Which of the following sentence are true? Select all that apply.
(a) Equivalence relations have nothing to do with partitions in general.
(b) For any set X and equivalence relation ∼ on X, the quotient set
X
∼
is a partition of X.
(c) There exists an infinite set X and a partition {A
n
} of X such that for any equivalence
relation ∼ on X, there is A ∈ {A
n
} for which A = [x] for any x ∈ X.
(d) Given any partition {A
n
} of X, there is an equivalence relation whose equivalence classes
are exactly the subsets of X in {A
n
}.
6. The set of real numbers R = Q ∪ (R \ Q) is partitioned into the subsets of rational and irrational
numbers. Describe an equivalence relation on R whose equivalence classes form this partition:
x ∼ y ⇐⇒ x − y
7. Give examples of an infinite set X and an equivalence relation ∼ on X such that
(a) ∼ has finitely many equivalence classes.
(b) ∼ has infinitely many classes, each of which have finitely many elements.
(c) ∼ has infinitely many classes, each of which have infinitely many elements.
(d) ∼ has a class of size n for each n ∈ N.
Practice Problems Section 7.3
1. Let S =
(x, y) ∈ R
2
: sin
2
x + cos
2
y = 1
.
(a) Give an example of two real numbers x, y such that x S y.
(b) Is S reflexive? symmetric? transitive? Justify your answers.
2. Define R on N
≥2
by a R b if and only if gcd(a, b) > 1. Determine whether R is reflexive,
symmetric, or transitive.
3. Let ∼ be the relation on R defined by x ∼ y if and only if x − y ∈ Z.
(a) Prove that ∼ is an equivalence relation.
(b) List three distinct elements of the equivalence class [
5
2
]. In general, what is an equivalence
class [x] as a set?
(c) Describe the quotient
R
∼
.
4. Let X be a non-empty set. Then {X} and
{x} : x ∈ X
are both partitions of X. For both
partitions, determine the equivalence relation whose equivalence classes form the subsets of
the partition.
5. Determine whether each collections {A
n
} partitions R
2
. Justify your answers and sketch sev-
eral of the sets A
n
.
(a) A
n
=
(x, y) ∈ R
2
: y = 2x + n
, for n ∈ Z.
(b) A
n
=
(x, y) ∈ R
2
: y = x
2
+ n
, for n ∈ R.
(c) A
n
=
(x, y) ∈ R
2
: y = cos(x − n)
, for n ∈ R.
6. Let X = {1, 2, 3, 4} and define a relation R on X by
R =
(1, 3), (1, 4), (2, 2), (2, 3), (3, 1), (3, 2), (4, 3), (4, 4)
Show that the subsets
A
n
= {x ∈ X : (n, x) ∈ R} (where n = 1, 2, 3, 4)
do not partition X. Also verify that R is not an equivalence relation.
