Equivalence Relations & Partitions
What three properties must a relation \(R\) on a set \(A\) satisfy to be an Equivalence Relation?
The relation must be: 1. Reflexive 2. Symmetric 3. Transitive
Define the Equivalence Class of an element \(a\), denoted as \([a]\).
The equivalence class \([a]\) is the set of all elements \(x\) in \(A\) such that \(x\) is related to \(a\) by \(R\): \[[a] = \{x \in A \mid xRa\}\]
Let \(A = \{1, 2, 3, 4\}\) and \(R = \{(1,1), (2,2), (3,3), (4,4), (1,2), (2,1)\}\). What is the equivalence class \([1]\)?
\([1] = \{1, 2\}\) Since \(1R1\) and \(1R2\), both \(1\) and \(2\) belong to the set. Note that \([2]\) would be the exact same set.
If \(R\) is an equivalence relation on set \(A\), and \(aRb\), what is the relationship between the sets \([a]\) and \([b]\)?
The sets are identical: \([a] = [b]\). In an equivalence relation, any two elements that are related share the exact same equivalence class.
True or False: Two different equivalence classes can have exactly one element in common.
False. Equivalence classes are disjoint. Either \([a] = [b]\) or \([a] \cap [b] = \emptyset\). They never overlap partially.
Define a Partition of a set \(A\).
A partition is a collection of non-empty, disjoint subsets of \(A\) whose union is exactly \(A\).
How does an equivalence relation \(R\) relate to a partition of set \(A\)?
The set of all distinct equivalence classes of \(R\) forms a partition of \(A\). Conversely, every partition of \(A\) defines a unique equivalence relation.
Consider the relation “has the same age in years” on a group of students. Is this an equivalence relation?
Yes. * Reflexive: You are the same age as yourself. * Symmetric: If A is the same age as B, B is the same age as A. * Transitive: If A=B and B=C, then A=C.
Let \(A = \mathbb{Z}\) and \(xRy \iff x \equiv y \pmod 3\). How many distinct equivalence classes are there?
There are 3 distinct equivalence classes, corresponding to the possible remainders when dividing by 3: * \([0] = \{..., -3, 0, 3, 6, ...\}\) * \([1] = \{..., -2, 1, 4, 7, ...\}\) * \([2] = \{..., -1, 2, 5, 8, ...\}\)
If a relation is Reflexive and Symmetric but not Transitive, can it form a partition?
No. Without transitivity, you could have \(aRb\) and \(bRc\) but \(a \cancel{R} c\). This would cause the “classes” to overlap without being identical, violating the rules of a partition.
What is the equivalence class of \(0\) for the relation \(xRy \iff x^2 = y^2\) on the set of integers \(\mathbb{Z}\)?
\([0] = \{0\}\). Since \(0^2 = 0\), and no other integer squared equals 0, the class contains only the element 0. (Note: \([2]\) would be \(\{2, -2\}\)).
In the directed graph of an equivalence relation, what “shape” do the connected components form?
Each component forms a complete subgraph (or clique) where every vertex in the class has an edge to every other vertex in that same class (including self-loops).
Is the “is a sibling of” relation an equivalence relation? (Assume you are not your own sibling).
No. If we assume you are not your own sibling, it is not reflexive. Therefore, it cannot be an equivalence relation.
If \(A = \{a, b, c, d\}\) and a partition is \(\{\{a, b, c\}, \{d\}\}\), list the pairs in the corresponding equivalence relation \(R\).
\(R = \{(a,a), (b,b), (c,c), (d,d), (a,b), (b,a), (a,c), (c,a), (b,c), (c,b)\}\). Essentially, every element in a subset is related to every other element in that same subset.
If \(|A| = n\), what is the minimum number of equivalence classes an equivalence relation on \(A\) can have?
1. This occurs when every element is related to every other element (\(R = A \times A\)). All elements belong to a single, universal equivalence class.