🔶Intro to Abstract Math Unit 4 – Equivalence Relations & Partitions

Key Concepts

• Equivalence relations are binary relations on a set that satisfy reflexivity, symmetry, and transitivity properties
• Partitions divide a set into disjoint subsets called equivalence classes
• Each element of the set belongs to exactly one equivalence class
• Equivalence relations and partitions are closely related concepts in abstract mathematics
• Understanding the properties and characteristics of equivalence relations is crucial for working with partitions
• Equivalence relations have wide-ranging applications in various branches of mathematics, including algebra, topology, and geometry
• Recognizing common mistakes and misconceptions helps deepen understanding of equivalence relations and partitions

Definition and Properties

• An equivalence relation on a set $A$ is a binary relation $\sim$ that satisfies three properties:
  • Reflexivity: $a \sim a$ for all $a \in A$
  • Symmetry: If $a \sim b$, then $b \sim a$ for all $a, b \in A$
  • Transitivity: If $a \sim b$ and $b \sim c$, then $a \sim c$ for all $a, b, c \in A$
• The notation $a \sim b$ is read as "$a$ is equivalent to $b$" under the relation $\sim$
• Equivalence relations are reflexive, meaning every element is related to itself
• Symmetry ensures that if $a$ is related to $b$, then $b$ is also related to $a$
• Transitivity guarantees that if $a$ is related to $b$ and $b$ is related to $c$, then $a$ is also related to $c$
• These properties collectively define what it means for a relation to be an equivalence relation

Examples and Non-Examples

• Example of an equivalence relation: Equality of numbers (=) on the set of real numbers
  • Reflexivity: $a = a$ for all real numbers $a$
  • Symmetry: If $a = b$, then $b = a$ for all real numbers $a$ and $b$
  • Transitivity: If $a = b$ and $b = c$, then $a = c$ for all real numbers $a$, $b$, and $c$
• Example of an equivalence relation: Congruence modulo $n$ on the set of integers
  • Two integers $a$ and $b$ are congruent modulo $n$ if their difference $a - b$ is divisible by $n$
  • Denoted as $a \equiv b \pmod{n}$
• Non-example: The "less than" relation (<) on the set of real numbers is not an equivalence relation
  • It fails reflexivity ($a < a$ is false for all $a$) and symmetry (if $a < b$, then $b < a$ is false)
• Non-example: The "divides" relation on the set of integers is not an equivalence relation
  • It fails symmetry (if $a$ divides $b$, $b$ may not divide $a$) and reflexivity ($0$ does not divide itself)

Connection to Set Theory

• Equivalence relations are closely tied to the concept of partitions in set theory
• A partition of a set $A$ is a collection of non-empty, disjoint subsets of $A$ whose union is $A$
• Each subset in a partition is called an equivalence class
• An equivalence relation on a set induces a partition of the set into equivalence classes
• Conversely, given a partition of a set, an equivalence relation can be defined where elements are related if they belong to the same subset in the partition
• This bidirectional relationship highlights the fundamental connection between equivalence relations and partitions

Equivalence Classes

• Given an equivalence relation $\sim$ on a set $A$ and an element $a \in A$, the equivalence class of $a$ is the set of all elements in $A$ that are related to $a$ under $\sim$
• Denoted as $[a] = \{x \in A : x \sim a\}$
• Equivalence classes are disjoint, meaning no two equivalence classes share any elements
• Every element of the set belongs to exactly one equivalence class
• The set of all equivalence classes forms a partition of the original set
• Equivalence classes can be used to define a new set called the quotient set, denoted as $A/\sim$
  • The quotient set consists of the equivalence classes as its elements

Partitions and Their Relationship

• A partition of a set $A$ is a collection of non-empty, pairwise disjoint subsets of $A$ whose union is $A$
• Every element of $A$ belongs to exactly one subset in the partition
• An equivalence relation on a set induces a partition of the set into equivalence classes
  • Elements in the same equivalence class are related under the equivalence relation
• Conversely, a partition of a set defines an equivalence relation on the set
  • Two elements are related if they belong to the same subset in the partition
• This one-to-one correspondence between equivalence relations and partitions is a fundamental concept in abstract mathematics
• Understanding the relationship between equivalence relations and partitions is crucial for problem-solving and analysis in various mathematical contexts

Applications in Mathematics

• Equivalence relations and partitions have numerous applications across different branches of mathematics
• In linear algebra, vector spaces can be partitioned into equivalence classes based on linear independence or span
• In group theory, cosets are equivalence classes formed by a subgroup acting on the group through multiplication
  • Cosets partition the group and are fundamental in studying quotient groups and group homomorphisms
• In topology, equivalence relations such as homotopy and homeomorphism are used to classify and study topological spaces
• In modular arithmetic, congruence modulo $n$ is an equivalence relation that partitions the integers into $n$ equivalence classes
  • This forms the basis for many applications in number theory and cryptography
• Equivalence relations are also used in the construction of quotient structures, such as quotient groups, quotient rings, and quotient spaces

Common Mistakes and Misconceptions

• Confusing equivalence relations with other types of relations, such as partial orders or total orders
  • Equivalence relations must satisfy reflexivity, symmetry, and transitivity, while other relations may have different properties
• Assuming that all relations are equivalence relations without verifying the necessary properties
  • It's essential to check reflexivity, symmetry, and transitivity to confirm a relation is an equivalence relation
• Believing that equivalence classes can overlap or share elements
  • Equivalence classes are disjoint, meaning no two equivalence classes have any elements in common
• Thinking that every partition induces a unique equivalence relation and vice versa
  • While there is a one-to-one correspondence between equivalence relations and partitions, multiple equivalence relations can induce the same partition
• Misinterpreting the meaning of equivalence in specific contexts
  • The notion of equivalence may vary depending on the mathematical context, such as algebraic structures or topological spaces
• Overlooking the importance of the quotient set and its role in studying the properties of the original set under the equivalence relation