344
Relations, Functions, and Matrices
The equation
x + y = qn + r, 0 ≤ r < n
symbolizes this division, where q is the quotient and r is the remainder. This
equation may be written as
(x + y) − r = qn
which shows that (x + y) − r is an integral multiple of n, or that (x + y) ≡ r
(mod n). The integer r may not be x + y, but it is in the equivalence class 3x + y 4,
and since 0 ≤ r < n, it is also in the range of integers that can be stored. (The
system may or may not issue an integer overflow message if x + y is too large to
store and addition modulo n must be used.) The situation is analogous to your car’s
odometer, which records mileage modulo 100,000; when mileage reaches 102,758,
for example, it is displayed on the odometer as 2,758.
PRaCtiCe 15 What are the equivalence classes corresponding to the relation of congruence modulo 5
on Z?
■
PRaCtiCe 16 If 4 is the maximum integer that can be stored on a (micromicro) computer, what will
be stored for the value 3 + 4 if addition modulo 5 is used?
Table 5.1 summarizes important features of partial orderings and equivalence
relations.
table 5.1
partial orderings and equivalence Relations
type of binary Relation
Reflexive Symmetric
antisymmetric
transitive
Important feature
Partial ordering
Yes
No
Yes
Yes
Predecessors and
successors
Equivalence relation
Yes
Yes
No
Yes
Determines a partition
S e c t I o n 5 . 1 Review
technIQueS
• Test an ordered pair for membership in a binary
relation.
• Test a binary relation for reflexivity, symmetry,
antisymmetry, and transitivity.
• Find the reflexive, symmetric, and transitive
closure of a relation.
• Draw the Hasse diagram for a finite partially
ordered set.
• Find least, minimal, greatest, and maximal elements
in a partially ordered set.
• Find the equivalence classes associated with an
equivalence relation.
W
W
■