340
Relations, Functions, and Matrices
example 12
In the case where x r y 4 “x sits in the same row as y,” suppose that John, Chuck,
Jose, Judy, and Ted all sit in row 3. Then 3John4 = 5John, Chuck, Jose, Judy, Ted6.
Also 3John4 = 3Ted 4 = 3Judy4, and so on. These are not distinct classes, but the
same class with multiple names. An equivalence class can take its name from any
of the elements in it.
Now we state the result about equivalence relations and partitions. For some
practice with formal theorems and proofs, we give this result as a formal theorem,
then analyze the structure of the proof and complete part of the proof.
theoRem on equivalence RelationS and paRtitionS
An equivalence relation r on a set S determines a partition of S, and a partition of
a set S determines an equivalence relation on S.
Partial Proof : The theorem makes two separate statements:
a. An equivalence relation on S determines a partition of S.
b. A partition of S determines an equivalence relation on S.
To prove part (a), we must show that the distinct equivalence classes of members
of S under equivalence relation r satisfy the definition of a partition. To satisfy the
definition of a partition, we must show that
i. the union of these distinct classes equals S.
ii. the distinct classes are disjoint.
To prove part (a. i), we must show something about the union of the distinct
equivalence classes formed by r. Equivalence classes are sets of elements of S, so
their union is a set; let’s denote this set by U. We must show that U = S, which is
a set equality. To prove this set equality, we will prove set inclusion in each direction; in other words,
1. U # S
2. S # U
For this part of the proof, we are finally down to two small statements that are
easy to prove, as follows:
a.i.1: Let x [ U . Then x belongs to an equivalence class. Every equivalence
class is a subset of S, so x [ S.
a.i.2: Let x [ S. Then x r x (reflexivity of r); thus, x [ 3x 4, and every member
of S belongs to some equivalence class, hence to the union of classes U.
This completes the proof of part (a.i). For part (a.ii), let 3x 4 and 3z 4 be two
equivalence classes. We want to show that distinct classes are disjoint, or
3x 4 ∙ 3z 4 S 3x 4 d 3z 4 = [
(a.ii)
Relations, Functions, and Matrices
example 12
In the case where x r y 4 “x sits in the same row as y,” suppose that John, Chuck,
Jose, Judy, and Ted all sit in row 3. Then 3John4 = 5John, Chuck, Jose, Judy, Ted6.
Also 3John4 = 3Ted 4 = 3Judy4, and so on. These are not distinct classes, but the
same class with multiple names. An equivalence class can take its name from any
of the elements in it.
Now we state the result about equivalence relations and partitions. For some
practice with formal theorems and proofs, we give this result as a formal theorem,
then analyze the structure of the proof and complete part of the proof.
theoRem on equivalence RelationS and paRtitionS
An equivalence relation r on a set S determines a partition of S, and a partition of
a set S determines an equivalence relation on S.
Partial Proof : The theorem makes two separate statements:
a. An equivalence relation on S determines a partition of S.
b. A partition of S determines an equivalence relation on S.
To prove part (a), we must show that the distinct equivalence classes of members
of S under equivalence relation r satisfy the definition of a partition. To satisfy the
definition of a partition, we must show that
i. the union of these distinct classes equals S.
ii. the distinct classes are disjoint.
To prove part (a. i), we must show something about the union of the distinct
equivalence classes formed by r. Equivalence classes are sets of elements of S, so
their union is a set; let’s denote this set by U. We must show that U = S, which is
a set equality. To prove this set equality, we will prove set inclusion in each direction; in other words,
1. U # S
2. S # U
For this part of the proof, we are finally down to two small statements that are
easy to prove, as follows:
a.i.1: Let x [ U . Then x belongs to an equivalence class. Every equivalence
class is a subset of S, so x [ S.
a.i.2: Let x [ S. Then x r x (reflexivity of r); thus, x [ 3x 4, and every member
of S belongs to some equivalence class, hence to the union of classes U.
This completes the proof of part (a.i). For part (a.ii), let 3x 4 and 3z 4 be two
equivalence classes. We want to show that distinct classes are disjoint, or
3x 4 ∙ 3z 4 S 3x 4 d 3z 4 = [
(a.ii)