Equivalence Relations

In mathematics, a relation is a fundamental concept that describes a connection between elements of sets. When we talk about equivalence relations, we are specifically looking at relations that possess certain properties making them behave like an "equality" relation. These properties allow us to partition a set into disjoint subsets, where all elements within a subset are related to each other, and no element in one subset is related to an element in another subset.

Definition of an Equivalence Relation

Let 'A' be a non-empty set. A relation 'R' defined on set 'A' is called an equivalence relation if it satisfies the following three properties:

1. Reflexive Property: For every element 'a' in set 'A', 'a' is related to itself. Mathematically, this is written as (a, a) ∈ R for all a ∈ A.
2. Symmetric Property: If an element 'a' is related to an element 'b' in set 'A', then 'b' must also be related to 'a'. Mathematically, if (a, b) ∈ R, then (b, a) ∈ R for all a, b ∈ A.
3. Transitive Property: If an element 'a' is related to an element 'b', and 'b' is related to an element 'c' in set 'A', then 'a' must also be related to 'c'. Mathematically, if (a, b) ∈ R and (b, c) ∈ R, then (a, c) ∈ R for all a, b, c ∈ A.

Understanding the Properties with Examples

1. Reflexive Property

The reflexive property states that every element must be related to itself. Think of it like a mirror: every object is a reflection of itself.

Example 1: Let A = {1, 2, 3}. Consider the relation R = {(1, 1), (2, 2), (3, 3)}. Is this relation reflexive? Yes, because (1, 1) ∈ R, (2, 2) ∈ R, and (3, 3) ∈ R. Every element in A is related to itself.

Example 2: Let A = {a, b, c}. Consider the relation R = {(a, a), (b, b), (a, b)}. Is this relation reflexive? No, because the element 'c' in set A is not related to itself (i.e., (c, c) ∉ R).

2. Symmetric Property

The symmetric property means that if a connection exists from 'a' to 'b', then the connection must also exist from 'b' to 'a'. It's like a two-way street.

Example 1: Let A = {1, 2, 3}. Consider the relation R = {(1, 1), (2, 2), (3, 3), (1, 2), (2, 1)}. Is this relation symmetric? Let's check:

• (1, 1) ∈ R. If we swap, we get (1, 1), which is in R.
• (2, 2) ∈ R. If we swap, we get (2, 2), which is in R.
• (3, 3) ∈ R. If we swap, we get (3, 3), which is in R.
• (1, 2) ∈ R. If we swap, we get (2, 1), which is also in R.
• (2, 1) ∈ R. If we swap, we get (1, 2), which is also in R.

Yes, the relation is symmetric.

Example 2: Let A = {1, 2, 3}. Consider the relation R = {(1, 1), (2, 2), (1, 2)}. Is this relation symmetric? No. We have (1, 2) ∈ R, but (2, 1) ∉ R. The condition is not met for the pair (1, 2).

3. Transitive Property

The transitive property is about chaining connections. If 'a' is connected to 'b', and 'b' is connected to 'c', then 'a' must be connected to 'c'. Think of it as a relay race where the baton must be passed correctly.

Example 1: Let A = {1, 2, 3}. Consider the relation R = {(1, 1), (2, 2), (3, 3), (1, 2), (2, 1), (1, 3), (3, 1)}. Is this relation transitive? Let's check for all possible chains:

• We have (1, 2) ∈ R and (2, 1) ∈ R. This implies (1, 1) ∈ R, which is true.
• We have (2, 1) ∈ R and (1, 2) ∈ R. This implies (2, 2) ∈ R, which is true.
• We have (1, 3) ∈ R and (3, 1) ∈ R. This implies (1, 1) ∈ R, which is true.
• We have (3, 1) ∈ R and (1, 3) ∈ R. This implies (3, 3) ∈ R, which is true.
• Consider the chain (1, 2) ∈ R and (2, 3) ∉ R. No implication.
• Consider the chain (1, 3) ∈ R and (3, 1) ∈ R. This implies (1, 1) ∈ R, which is true.
• Consider the chain (3, 1) ∈ R and (1, 2) ∈ R. This implies (3, 2) ∉ R. Wait, this is where we need to be careful. If (a, b) ∈ R and (b, c) ∈ R, THEN (a, c) ∈ R. If there is no pair (b, c) such that (a, b) ∈ R and (b, c) ∈ R, then the condition is vacuously true for that 'a' and 'b'.

Let's re-evaluate the transitive property carefully. We need to check if for every pair (a, b) ∈ R and (b, c) ∈ R, the pair (a, c) is also in R. In this example, the pairs (a,b) and (b,c) that exist are: (1,1) & (1,1) -> (1,1) ∈ R (True) (1,1) & (1,2) -> (1,2) ∈ R (True) (1,1) & (1,3) -> (1,3) ∈ R (True) (1,2) & (2,1) -> (1,1) ∈ R (True) (1,3) & (3,1) -> (1,1) ∈ R (True) (2,1) & (1,1) -> (2,1) ∈ R (True) (2,1) & (1,2) -> (2,2) ∈ R (True) (2,1) & (1,3) -> (2,3) ∉ R. Ah, here is the problem. Wait, I made a mistake in listing the relation. Let's correct the example relation. Let A = {1, 2, 3}. Consider the relation R = {(1, 1), (2, 2), (3, 3), (1, 2), (2, 1), (1, 3), (3, 1), (2, 3), (3, 2)}. Pairs (a,b) and (b,c) in R: (1,2) & (2,1) -> (1,1) ∈ R (True) (1,2) & (2,3) -> (1,3) ∈ R (True) (1,3) & (3,1) -> (1,1) ∈ R (True) (1,3) & (3,2) -> (1,2) ∈ R (True) (2,1) & (1,1) -> (2,1) ∈ R (True) (2,1) & (1,2) -> (2,2) ∈ R (True) (2,1) & (1,3) -> (2,3) ∈ R (True) (2,3) & (3,1) -> (2,1) ∈ R (True) (2,3) & (3,2) -> (2,2) ∈ R (True) (3,1) & (1,1) -> (3,1) ∈ R (True) (3,1) & (1,2) -> (3,2) ∈ R (True) (3,1) & (1,3) -> (3,3) ∈ R (True) (3,2) & (2,1) -> (3,1) ∈ R (True) (3,2) & (2,3) -> (3,3) ∈ R (True) Yes, this relation is transitive. Example 2: Let A = {1, 2, 3}. Consider the relation R = {(1, 1), (2, 2), (1, 2)}. Is this relation transitive? We have (1, 1) ∈ R and (1, 2) ∈ R. This implies (1, 2) ∈ R, which is true. We have (1, 2) ∈ R. Is there any (2, x) ∈ R? Yes, (2, 2) ∈ R. So we check if (1, 2) ∈ R. Yes, it is. We have (2, 2) ∈ R. Is there any (2, x) ∈ R? Yes, (2, 2) ∈ R. So we check if (2, 2) ∈ R. Yes, it is. Let's re-examine the definition. If (a, b) ∈ R and (b, c) ∈ R, then (a, c) ∈ R. Here, we have (1, 1) ∈ R and (1, 2) ∈ R. This implies (1, 2) ∈ R, which is true. We have (1, 2) ∈ R and (2, 2) ∈ R. This implies (1, 2) ∈ R, which is true. There are no other combinations of (a, b) and (b, c) in R. So, this relation R = {(1, 1), (2, 2), (1, 2)} IS transitive.

Example 3: Let A = {1, 2, 3}. Consider the relation R = {(1, 2), (2, 3)}. Is this relation transitive? No. We have (1, 2) ∈ R and (2, 3) ∈ R. For transitivity, we must have (1, 3) ∈ R. Since (1, 3) ∉ R, the relation is not transitive.

When is a Relation an Equivalence Relation?

A relation 'R' on a set 'A' is an equivalence relation if and only if it is reflexive, symmetric, AND transitive. If even one of these properties fails, the relation is not an equivalence relation.

Examples of Equivalence Relations in Mathematics

1. Equality Relation

On any set 'A', the equality relation (where every element is related only to itself) is always an equivalence relation. Let A = {a, b, c}. R = {(a, a), (b, b), (c, c)}.

• Reflexive: (a, a), (b, b), (c, c) ∈ R. Yes.
• Symmetric: If (x, y) ∈ R, then (y, x) ∈ R. Since all pairs are of the form (x, x), swapping them gives the same pair. Yes.
• Transitive: If (x, y) ∈ R and (y, z) ∈ R, then (x, z) ∈ R. If (a, a) ∈ R and (a, a) ∈ R, then (a, a) ∈ R. Yes.

Therefore, the equality relation is an equivalence relation.

2. Congruence Modulo n

Let 'n' be a positive integer. Consider the set of integers, Z. The relation 'congruence modulo n', denoted by '≡ (mod n)', is defined as: a ≡ b (mod n) if and only if (a - b) is divisible by n. This is an equivalence relation on the set of integers Z. Let's prove it.

Reflexive: For any integer 'a', is a ≡ a (mod n)? This means (a - a) must be divisible by n. (a - a) = 0. Since 0 is divisible by any non-zero integer n, 0 is divisible by n. So, a ≡ a (mod n) is true. The relation is reflexive.

Symmetric: If a ≡ b (mod n), is b ≡ a (mod n)? If a ≡ b (mod n), then (a - b) is divisible by n. This means a - b = kn for some integer k. We need to check if (b - a) is divisible by n. b - a = -(a - b) = -(kn) = (-k)n. Since -k is also an integer, (b - a) is divisible by n. So, if a ≡ b (mod n), then b ≡ a (mod n). The relation is symmetric.

Transitive: If a ≡ b (mod n) and b ≡ c (mod n), is a ≡ c (mod n)? If a ≡ b (mod n), then (a - b) is divisible by n. So, a - b = k₁n for some integer k₁. If b ≡ c (mod n), then (b - c) is divisible by n. So, b - c = k₂n for some integer k₂. We need to check if (a - c) is divisible by n. Consider (a - c) = (a - b) + (b - c). Substitute the expressions: (a - c) = k₁n + k₂n = (k₁ + k₂)n. Since k₁ and k₂ are integers, (k₁ + k₂) is also an integer. Therefore, (a - c) is divisible by n. So, if a ≡ b (mod n) and b ≡ c (mod n), then a ≡ c (mod n). The relation is transitive.

Since congruence modulo n is reflexive, symmetric, and transitive, it is an equivalence relation.

3. Relation "has the same parity"

Consider the set of integers Z. Define a relation R on Z such that a R b if 'a' and 'b' have the same parity (both are even or both are odd). Let's check the properties:

Reflexive: Is any integer 'a' related to itself? If 'a' is even, it has the same parity as itself (even). If 'a' is odd, it has the same parity as itself (odd). So, yes, a R a for all a ∈ Z.

Symmetric: If a R b, does b R a? If a R b, it means 'a' and 'b' have the same parity. This naturally implies that 'b' and 'a' also have the same parity. So, yes, b R a.

Transitive: If a R b and b R c, does a R c? If a R b, 'a' and 'b' have the same parity. If b R c, 'b' and 'c' have the same parity. This means 'a' has the same parity as 'b', and 'b' has the same parity as 'c'. Therefore, 'a' must have the same parity as 'c'. So, yes, a R c.

Since all three properties hold, the relation "has the same parity" is an equivalence relation.

4. Relation "lives in the same city"

Consider the set of all people in the world. Define a relation R where person A is related to person B if they live in the same city.

Reflexive: Does every person live in the same city as themselves? Yes.

Symmetric: If person A lives in the same city as person B, does person B live in the same city as person A? Yes.

Transitive: If person A lives in the same city as person B, and person B lives in the same city as person C, do person A and person C live in the same city? Yes, they all live in that same city.

This is an equivalence relation.

Equivalence Classes

One of the most important consequences of an equivalence relation is that it partitions the set into disjoint subsets called equivalence classes.

Let 'R' be an equivalence relation on a set 'A'. For any element 'a' ∈ A, the equivalence class of 'a', denoted by [a] or E_a, is the set of all elements in 'A' that are related to 'a'. Formally, [a] = {x ∈ A | x R a}.

Key properties of equivalence classes:

• Every element 'a' belongs to its own equivalence class: a ∈ [a]. (Due to reflexivity)
• If 'a' and 'b' are in the same equivalence class, then [a] = [b]. This means if R is an equivalence relation, then for any a, b ∈ A, either [a] = [b] or [a] ∩ [b] = ∅.
• The set of all equivalence classes forms a partition of the set 'A'. This means the union of all equivalence classes is the entire set A, and the intersection of any two distinct equivalence classes is empty.

Example: Equivalence Classes of Congruence Modulo 3

Let's consider the set of integers Z and the equivalence relation "congruence modulo 3" (a ≡ b (mod 3)). The relation means that (a - b) is divisible by 3.

What are the equivalence classes?

Equivalence Class of 0: [0] = {x ∈ Z | x ≡ 0 (mod 3)} This means (x - 0) is divisible by 3, so x is divisible by 3. [0] = {..., -6, -3, 0, 3, 6, 9, ...} = {3k | k ∈ Z} This is the set of all multiples of 3.

Equivalence Class of 1: [1] = {x ∈ Z | x ≡ 1 (mod 3)} This means (x - 1) is divisible by 3. So, x - 1 = 3k for some integer k, which means x = 3k + 1. [1] = {..., -5, -2, 1, 4, 7, 10, ...} = {3k + 1 | k ∈ Z} These are integers that leave a remainder of 1 when divided by 3.

Equivalence Class of 2: [2] = {x ∈ Z | x ≡ 2 (mod 3)} This means (x - 2) is divisible by 3. So, x - 2 = 3k for some integer k, which means x = 3k + 2. [2] = {..., -4, -1, 2, 5, 8, 11, ...} = {3k + 2 | k ∈ Z} These are integers that leave a remainder of 2 when divided by 3.

Notice that any integer will fall into exactly one of these three classes. For example, 5 is in [2] because 5 = 3(1) + 2. -4 is in [2] because -4 = 3(-2) + 2. If we take any other integer, say 4, its equivalence class is [4]. [4] = {x ∈ Z | x ≡ 4 (mod 3)}. Since 4 ≡ 1 (mod 3) (because 4 - 1 = 3, which is divisible by 3), the equivalence class [4] is the same as [1]. [4] = {..., -2, 1, 4, 7, ...} = [1].

So, for congruence modulo 3, there are exactly three distinct equivalence classes: [0], [1], and [2]. These three classes partition the set of integers Z. Z = [0] ∪ [1] ∪ [2] [0] ∩ [1] = ∅ [0] ∩ [2] = ∅ [1] ∩ [2] = ∅

The set of these equivalence classes is called the quotient set, denoted by Z/3Z or Z₃. Z/3Z = {[0], [1], [2]}

Summary of Equivalence Relations

An equivalence relation is a powerful mathematical tool that allows us to group elements of a set based on a shared property. The three defining characteristics – reflexivity, symmetry, and transitivity – ensure that these groupings are consistent and well-behaved. The concept of equivalence classes provides a way to understand the structure induced by such relations, leading to partitions of the set. Understanding these concepts is crucial for various areas of mathematics, including abstract algebra, number theory, and topology.

Common Pitfalls to Avoid:

• Confusing the symmetric and transitive properties. Remember, symmetry is about reversing pairs, while transitivity is about chaining pairs.
• Forgetting to check all three properties. A relation must satisfy ALL three to be an equivalence relation.
• Incorrectly identifying equivalence classes. Ensure every element belongs to exactly one class.