Definition and Basic Properties
Formal Definition
Equivalence relation: a binary relation ~ on set S satisfying three properties: reflexive, symmetric, transitive. Notation: ∀a,b,c ∈ S, a~a, if a~b then b~a, if a~b and b~c then a~c.
Symbolic Representation
~ ⊆ S × S∀a ∈ S, (a, a) ∈ ~ (Reflexivity)∀a,b ∈ S, (a, b) ∈ ~ ⇒ (b, a) ∈ ~ (Symmetry)∀a,b,c ∈ S, (a, b) ∈ ~ ∧ (b, c) ∈ ~ ⇒ (a, c) ∈ ~ (Transitivity)Properties Overview
Equivalence relations induce equivalence classes partitioning S. Equivalence relations are symmetric relations with additional structure. Every equivalence relation corresponds to a partition.
Reflexivity
Definition
Reflexivity: ∀a ∈ S, a~a. Relation relates every element to itself.
Significance
Ensures identity-like property. Without reflexivity, relation cannot be equivalence relation.
Examples
Equality on numbers: ∀x, x = x. Congruence modulo n: a ≡ a (mod n).
Symmetry
Definition
Symmetry: ∀a,b ∈ S, if a~b then b~a. Relation is bidirectional between pairs.
Importance
Ensures mutual relatedness. Symmetry distinguishes equivalence relations from partial orders.
Examples
Equality: if x=y then y=x. Congruence modulo n is symmetric.
Transitivity
Definition
Transitivity: ∀a,b,c ∈ S, if a~b and b~c then a~c. Relation chains through elements.
Role
Ensures consistency of relation over sequences. Critical for partitioning interpretation.
Examples
Equality is transitive. Congruence modulo n is transitive.
Equivalence Classes
Definition
Equivalence class of a ∈ S: [a] = {x ∈ S | x ~ a}. All elements related to a.
Properties
Classes are mutually disjoint or identical. S = ⋃_{a∈S} [a].
Example
Modulo 3 on integers: classes [0], [1], [2].
| Equivalence Class | Elements |
|---|---|
| [0] | {..., -6, -3, 0, 3, 6, ...} |
| [1] | {..., -5, -2, 1, 4, 7, ...} |
| [2] | {..., -4, -1, 2, 5, 8, ...} |
Partitioning of Sets
Definition
Partition: collection {A_i} of nonempty disjoint subsets covering S. Equivalence classes form such a partition.
Equivalence Relation ⇔ Partition
Every equivalence relation defines a partition. Every partition corresponds to an equivalence relation.
Formal Correspondence
Given partition P = {A_i}, define ~ by:a ~ b iff ∃A_j ∈ P s.t. a,b ∈ A_jExamples of Equivalence Relations
Equality
Standard equality on any set. Reflexive, symmetric, transitive.
Congruence Modulo n
a ≡ b (mod n) iff n divides (a-b). Partitions integers into residue classes.
Similarity of Triangles
Similarity relation on triangles: same shape, possibly different size. Equivalence relation in geometry.
Non-Examples and Counterexamples
Less Than Relation
Relation < on numbers is transitive but not symmetric or reflexive.
Divides Relation
“a divides b” is reflexive and transitive but not symmetric.
Symmetric but Not Transitive
“Is friends with” relation may be symmetric but not transitive.
Operations on Equivalence Relations
Intersection
Intersection of equivalence relations on S is equivalence relation.
Union
Union generally not equivalence relation.
Composition
Composition may fail to be equivalence relation unless additional conditions hold.
| Operation | Result |
|---|---|
| Intersection | Always an equivalence relation |
| Union | Not necessarily equivalence relation |
| Composition | May fail equivalence properties |
Applications in Discrete Mathematics
Classification Problems
Equivalence relations classify objects by shared properties.
Modular Arithmetic
Foundation for number theory via congruence relations.
Graph Theory
Connected components define equivalence classes under connectivity.
Relation to Functions and Quotient Sets
Quotient Set
Set of equivalence classes, denoted S/~. Canonical projection: π: S → S/~, π(a) = [a].
Function Factorization
Functions constant on equivalence classes factor through quotient sets.
Universal Property
Quotient set satisfies universal property for mapping out of S respecting ~.
π: S → S/~∀f: S → T with a ~ b ⇒ f(a) = f(b),∃! g: S/~ → T with f = g ∘ πKey Theorems and Proofs
Equivalence Relation and Partition Theorem
Every equivalence relation on S induces a partition of S into equivalence classes, and vice versa.
Proof Outline
Use reflexivity, symmetry, transitivity to show classes are disjoint and cover S.
Additional Results
Equivalence classes are maximal subsets where relation holds. Intersection of equivalence relations yields finest common refinement.
References
- Rosen, K. H. Discrete Mathematics and Its Applications. McGraw-Hill, 7th ed., 2012, pp. 134-148.
- Grimaldi, R. P. Discrete and Combinatorial Mathematics: An Applied Introduction. Pearson, 5th ed., 2003, pp. 242-256.
- Rudin, W. Principles of Mathematical Analysis. McGraw-Hill, 3rd ed., 1976, pp. 14-19.
- Stanley, R. P. Enumerative Combinatorics. Cambridge University Press, vol. 1, 1997, pp. 12-22.
- Herstein, I. N. Topics in Algebra. Wiley, 2nd ed., 1975, pp. 65-70.