Definition A relation R on a set A that is reflexive, symmetric, and transitive is called an equivalence relation.

In the last section we saw several equivalence relations. We shall revisit one of them.
Let A = Z and define a binary relation R on A as follows:

" m, n Î A, m R n Û 3|(m – n).

This is called congruence modulo 3 and is an equivalence relation. We usually write

m º n (mod 3)

instead of m R n. [Recall the quotient remainder theorem: m = dq + r,
where d=3, m, q, r Î Z, 0 £ r < d. Equivalently, m º r (mod 3) and m – r = 3q or simply 3|(m – r).]

Proof: Let m, n, s Î Z be arbitrary.

1. R is reflexive. [We must show that m R m for arbitrary m Î Z.] Since 3|0 = m – m,
   m º m (mod 3) so m R m and R is reflexive.
2. R is symmetric. [We must show that if m R n then n R m.] Suppose m R n, i.e.
   m º n (mod 3). This means 3|(m – n), so m – n = 3k, for some k Î Z. [We need to show that n – m = 3k₁, for some k₁ Î Z.] Now n – m = -(m – n) = -3k = 3(-k). But –k is an integer, so n – m = k₁, where k₁ = -k. Hence, 3|(n – m) and n º m (mod 3). So R is symmetric.
3. R is transitive. Suppose m R n Ù n R s. [We must show that m R s.] Since m R n,
   3|(m – n), and since n R s, 3|(n – s). Thus $ k₁, k₂ Î Z such that m – n = 3k₁,
   and n – s = 3k₂. [We need m – s = 3k, for some k Î Z.]

So 3|(m – s) and R is transitive. \ R is an equivalence relation. //

We have 0 º 0 (mod 3), 1 º 1 (mod 3), 2 º 2 (mod 3), 3 º 0 (mod 3), 4 º 1 (mod 3),
5 º 2 (mod 3), 6 º 0 (mod 3).

Question: If m º n (mod 3), and r º s (mod 3), is m + r º n + s (mod 3)?

Yes. Proof: Let m, n, r, s Î Z, with m º n (mod 3), and r º s (mod 3). [We must show that m + r º n + s (mod 3), that is 3|[(m + r) – (n + s)] ].
Now m º n (mod 3) ® 3|(m – n), and r º s (mod 3) ® 3|(r – s).

Thus $ k₁, k₂ Î Z such that m – n = 3k₁, and r – s = 3k₂. Add these two equations:

So 3 | [(m + r) – (n + s)] and m + r º n + s (mod 3). //

Definition: Suppose A is a set and R is an equivalence relation on A. For each element a in A, the equivalence class of a, denoted [a] and called the class of a for short, is the set of all elements x in A such that x is related to a by R.

Lemma 10.3.2 (page 563) Suppose A is a set, R is an equivalence relation on A, and a and b are elements of A. If a R b, then [a] = [b].

Lemma 10.3.3 (page 564) If A is a set, R is an equivalence relation on A, and a and b are elements of A, then

either [a] Ç [b] = Æ or [a] = [b].

Theorem 10.3.4 (page 565) If A is a nonempty set and R is an equivalence relation on A, then the distinct equivalence classes of R form a partition of A; that is, the union of the equivalence classes is all of A and the intersection of any two distinct classes is empty.

What are the equivalence classes of Congruence Modulo 3? Into which of these classes do 4, -8, 7, 11 fall?

Example 10.3.9 Equivalence Classes of Digital Logic Circuits
Let S be the set of all digital logic circuits with exactly two inputs and one output. The binary relation E is defined on S as follows: for all C₁ and C₂ in S,

C₁ E C₂ « C₁ has the same input/output table as C₂.

Describe the equivalence classes of this relation. How many distinct equivalence classes are there? Write representative circuits for two members of a distinct class.

Solution
Given a circuit C, the equivalence class of C is the set of all circuits with two input signals and one output signal that have the same input/output table as C. Recall that for two inputs four rows are required to represent the four possible combinations of inputs: 11, 10, 01, and 00. There are sixteen distinct classes of logic circuits in S. Consider column 15: Ø (p Ú q) the truth table is

Two distinct representatives for this circuit are

Since these two circuits share the same truth table, they are of course equivalent. Another way to verify they are equivalent would be to apply logical equivalence, in particular De Morgan's law.

Example
Given the set H = {1, 2, 3}, Determine which of the following relations exhibit reflexive, symmetric, and/or transitive properties. Which are equivalence relations?