Relations: Equivalence Relations and Partitions

Relations: Equivalence Relations and Partitions

In mathematics, a relation is a way to associate elements of one set with elements of another set (or the same set). Relations are fundamental in various areas of mathematics, including algebra, set theory, and logic. Two important concepts related to relations are equivalence relations and partitions, which are closely connected.

---

1. Relations

A relation on a set $A$ is a subset of the Cartesian product $A \times A$. It is a collection of ordered pairs $(a, b)$ where $a, b \in A$. We write $a \sim b$ if $(a, b)$ is in the relation $R$, meaning that $a$ is related to $b$.

Notation and Definition of a Relation:

Let $A$ be a set, and let $R$ be a relation on $A$. The relation $R$ is a subset of $A \times A$, which means that:

$$R \subseteq A \times A.$$

For any two elements $a, b \in A$, we write $a \sim b$ (or $a$ is related to $b$) if $(a, b) \in R$.

Properties of Relations:

A relation $R$ on a set $A$ can have certain properties that define its behavior. These properties include:

• Reflexive: $a \sim a$ for all $a \in A$.
• Symmetric: If $a \sim b$, then $b \sim a$.
• Transitive: If $a \sim b$ and $b \sim c$, then $a \sim c$.

---

2. Equivalence Relations

An equivalence relation is a specific type of relation that satisfies three key properties:

1. Reflexive: Every element is related to itself. For all $a \in A$, $a \sim a$.
2. Symmetric: If $a$ is related to $b$, then $b$ is related to $a$. If $a \sim b$, then $b \sim a$.
3. Transitive: If $a$ is related to $b$, and $b$ is related to $c$, then $a$ is related to $c$. If $a \sim b$ and $b \sim c$, then $a \sim c$.

A relation $R$ on a set $A$ is an equivalence relation if it satisfies all three properties.

Examples of Equivalence Relations:

1. Equality: The equality relation on any set is always an equivalence relation. For any set $A$, the relation $a = b$ is reflexive, symmetric, and transitive.

2. Congruence Modulo $n$: For integers, we say $a \sim b$ (mod $n$) if $a - b$ is divisible by $n$. This relation is:

   • Reflexive: $a - a = 0$, which is divisible by $n$.
   • Symmetric: If $a - b$ is divisible by $n$, then $b - a$ is also divisible by $n$.
   • Transitive: If $a - b$ is divisible by $n$ and $b - c$ is divisible by $n$, then $a - c$ is divisible by $n$.

3. Equivalence of Geometrical Objects: Two geometric objects (e.g., two triangles) are congruent if they can be transformed into one another by rotations, translations, or reflections. This is an equivalence relation because it satisfies reflexivity, symmetry, and transitivity.

---

3. Partitions

A partition of a set $A$ is a way of dividing $A$ into disjoint, non-empty subsets such that every element of $A$ is in exactly one of these subsets. Each subset in a partition is called a block or cell of the partition.

Connection Between Equivalence Relations and Partitions:

There is a direct relationship between equivalence relations and partitions. Specifically, if $R$ is an equivalence relation on a set $A$, then the equivalence classes of $R$ form a partition of $A$.

• Equivalence Class: The equivalence class of an element $a \in A$ under the relation $R$, denoted by $[a]$, is the set of all elements in $A$ that are related to $a$ under $R$:

  $$[a] = \{ b \in A \mid a \sim b \}.$$

  The equivalence classes are the blocks of the partition of $A$.

• Partition: The set of all equivalence classes under an equivalence relation on $A$ forms a partition of $A$, because:

  1. Every element of $A$ belongs to exactly one equivalence class.
  2. The equivalence classes are disjoint (no element can be in two different classes).
  3. The union of all equivalence classes is the entire set $A$.

Example of a Partition:

Consider the set $A = \{1, 2, 3, 4, 5, 6\}$, and the equivalence relation "congruence modulo 3." This relation groups the elements of $A$ based on their remainders when divided by 3.

• The equivalence classes (or blocks) are:
  • $[0] = \{3, 6\}$ (elements congruent to 0 modulo 3),
  • $[1] = \{1, 4\}$ (elements congruent to 1 modulo 3),
  • $[2] = \{2, 5\}$ (elements congruent to 2 modulo 3).

This is a partition of $A$ because:

1. Every element of $A$ is in exactly one of the equivalence classes.
2. The equivalence classes are disjoint.
3. The union of the equivalence classes gives the set $A$.

---

4. Theorem: Equivalence Relations and Partitions

There is a fundamental result that links equivalence relations and partitions:

Theorem: The equivalence classes of an equivalence relation on a set $A$ form a partition of $A$, and conversely, every partition of $A$ corresponds to an equivalence relation.

Proof Idea:

• If $R$ is an equivalence relation on $A$, the equivalence classes of $R$ form a partition of $A$.
• If a partition of $A$ is given, an equivalence relation can be defined by declaring two elements related if and only if they belong to the same block of the partition.

---

5. Properties of Equivalence Relations and Partitions

• Equivalence Class: The equivalence class of an element $a$ under an equivalence relation $R$ on $A$ is the set of all elements that are related to $a$.
• Disjointness of Equivalence Classes: The equivalence classes are disjoint. That is, no element of $A$ belongs to two different equivalence classes.
• Partitioning: The equivalence classes form a partition of the set $A$, meaning the set $A$ is divided into non-empty, disjoint subsets, and their union is $A$.
• Reflexivity, Symmetry, and Transitivity: These properties of equivalence relations ensure that the equivalence classes behave consistently and that each element is related to itself, leading to the partition.

---

6. Summary

• Equivalence Relation: A relation $R$ on a set $A$ is an equivalence relation if it is reflexive, symmetric, and transitive.
• Equivalence Class: The equivalence class of an element $a \in A$ is the set of all elements that are related to $a$.
• Partition: A partition of a set $A$ is a division of $A$ into non-empty disjoint subsets (blocks). The equivalence classes of an equivalence relation on $A$ form a partition of $A$.
• Connection: Equivalence relations and partitions are closely related; equivalence relations define partitions, and partitions define equivalence relations.

This understanding is fundamental in various mathematical fields, including algebra, geometry, and computer science.