Section 5.1 Relations
339
equivalence Relations
DefInItIon equivalence Relation
A binary relation on a set S that is reflexive, symmetric, and transitive is called an
equivalence relation on S.
RemInDeR
A partial ordering is antisymmetric; an equivalence
relation is symmetric.
We have already come across the following examples of equivalence relations:
On any set S, x r y 4 x = y.
On N, x r y 4 x + y is even.
On the set of all lines in the plane, x r y 4 x is parallel to y or coincides with y.
On 50, 16, x r y 4 x = y
2
.
On 5x 0 x is a student in your class6, x r y 4 x sits in the same row as y.
On 51, 2, 36, r = 5(1, 1), (2, 2), (3, 3), (1, 2), (2, 1)6.
We can illustrate an important feature of an equivalence relation on a set
by looking at S = 5x 0 x is a student in your class6, x r y 4 “x sits in the same row
as y.” Let’s group together all those students in set S who are related to one another. We come up with Figure 5.5. We have partitioned the set S into subsets in
such a way that everyone in the class belongs to one and only one subset.
Figure 5.5
row 1
row 3
row 2
row 4
row 5
S
DefInItIon paRtition oF a Set
A partition of a set S is a collection of nonempty disjoint subsets of S whose
union equals S.
Any equivalence relation, as we will see, partitions the set on which it is
defined. The subsets making up the partition, often called the blocks of the partition, are formed by grouping together related elements, like the students in the
classroom.
For r an equivalence relation on a set S and x [ S, we let 3x 4 denote the set
of all members of S to which x is related, called the equivalence class of x. Thus,
3x 4 = 5 y 0 y [ S ` x r y6
(Because r is symmetric, we could just as well have said that 3x 4 = 5 y 0 y [ S
` y r x6.)
339
equivalence Relations
DefInItIon equivalence Relation
A binary relation on a set S that is reflexive, symmetric, and transitive is called an
equivalence relation on S.
RemInDeR
A partial ordering is antisymmetric; an equivalence
relation is symmetric.
We have already come across the following examples of equivalence relations:
On any set S, x r y 4 x = y.
On N, x r y 4 x + y is even.
On the set of all lines in the plane, x r y 4 x is parallel to y or coincides with y.
On 50, 16, x r y 4 x = y
2
.
On 5x 0 x is a student in your class6, x r y 4 x sits in the same row as y.
On 51, 2, 36, r = 5(1, 1), (2, 2), (3, 3), (1, 2), (2, 1)6.
We can illustrate an important feature of an equivalence relation on a set
by looking at S = 5x 0 x is a student in your class6, x r y 4 “x sits in the same row
as y.” Let’s group together all those students in set S who are related to one another. We come up with Figure 5.5. We have partitioned the set S into subsets in
such a way that everyone in the class belongs to one and only one subset.
Figure 5.5
row 1
row 3
row 2
row 4
row 5
S
DefInItIon paRtition oF a Set
A partition of a set S is a collection of nonempty disjoint subsets of S whose
union equals S.
Any equivalence relation, as we will see, partitions the set on which it is
defined. The subsets making up the partition, often called the blocks of the partition, are formed by grouping together related elements, like the students in the
classroom.
For r an equivalence relation on a set S and x [ S, we let 3x 4 denote the set
of all members of S to which x is related, called the equivalence class of x. Thus,
3x 4 = 5 y 0 y [ S ` x r y6
(Because r is symmetric, we could just as well have said that 3x 4 = 5 y 0 y [ S
` y r x6.)