Definition 1.3.1. A relation on a set \(A\) is a subset \(R\) of the product \(A\times A.\) If \(R\) is a relation on \(A,\) we use the notation \(xRy\) to mean that \((x,y)\in R.\) We read it “\(x\) is in the relation \(R\) to \(y.\)”
Definition 1.3.2. A relation \(\sim\) on \(A\) is an equivalence relation on \(A\) if:
- (Reflexivity) \(\forall x \in A \ (x\sim x),\)
- (Symmetry) \(\forall x,y\in A \ (x\sim y \Rightarrow y\sim x),\) and
- (Transitivity) \(\forall x,y,z\in A \ ((x\sim y \land y\sim z) \Rightarrow x\sim z).\)
Definition 1.3.3. Let a set \(A,\) an equivalence relation \(\sim\) on \(A,\) and an element \(a\) of \(A\) be given. We define the equivalence class determined by \(a\) as the set \([a]\subseteq A\) such that
\[[a] = \lbrace x\in A: x\sim a\rbrace.\]Lemma 1.3.4. Let \(a,a'\in A.\) Two equivalence classes \([a]\) and \([a']\) on \(A\) are either disjoint or equal.
Proof. Suppose that there exists \(k\in A\) such that \(k\in [a]\) and \(k\in [a'].\) Then \(k\sim a\) and \(k\sim a'\) so that \(a\sim a'.\) Thus, if \(l\in [a]\) then \(l\sim a,\) so that \(l\sim a'.\) Therefore \(l\in [a'].\) Consequently, \([a]\subseteq [a'].\) Because of the situation’s being symmetry, we have \([a']\subseteq [a]\) as well, so that \([a]=[a'].\)
Conversely, we suppose that there are no elements such that \(k\in [a]\) and \(k\in [a'].\) Then \([a]\) and \([a']\) are disjoint.
Definition 1.3.5. A collection \(\mathcal P\) is a partition of \(A\) if:
- \(\forall x\in \mathcal P\ (x\neq \varnothing \land x\subseteq A),\)
- \(\forall x, y\in \mathcal P\ (x\neq y\Rightarrow x\cap y = \varnothing ),\) and
- \(\bigcup \mathcal P = A.\)
Theorem 1.3.6. Let \(\sim\) be an equivalence relation on a set \(A,\) and let \(A/{\sim}\) the collection of all the equivalence classes determined by \(\sim.\) Then \(A/{\sim}\) is a partition of \(A.\)
Proof.
- From Definition 1.3.3 \([a]\subseteq A,\) and \(a\in [a]\) so that \([a]\neq \varnothing\) by reflexivity.
- By Lemma 1.3.4, if \([a]\neq [a']\) then \([a]\cap [a'] = \varnothing.\)
- If \(a\in A\) then \(a\in [a]\) so that \(a\in \bigcup A/{\sim}.\) Thus \(A\subseteq \bigcup A/{\sim}.\) If \(a\in \bigcup A/{\sim}\) then there exists \([a']\in A/{\sim}\) such that \(a\in [a'],\) where \(a'\in A.\) Since \([a']\subseteq A,\) if follows that \(a\in A.\) Thus \(\bigcup A/{\sim}\subseteq A.\) Consequently, \(\bigcup A/{\sim} = A.\)
From the above, the collection \(A/{\sim}\) is a partition of \(A.\)\(\square\)
Theorem 1.3.7. There exist exactly one equivalence relation corresponding to any given partition.
Proof. Let \(\mathcal P\) be any partition of a set \(A.\) We define a relation \(R\) on \(A\) by
Since \(R\) has reflexivity, symmetry, and transitivity, \(R\) is an equivalence relation on \(A.\)
Since \(\mathcal P\) is a partition of \(A,\) there exists exactly one element that contains \(a\in A.\) Denoting the unique element as \(P_a,\) it follows that
Therefore \([a]_R = P_a.\)
Let
If \([a]_R\in A/R\) then \([a]_R=P_a\in \mathcal P.\) Thus \(A/R \subseteq \mathcal P.\) If \(P\in \mathcal P,\) then, since \(P\neq 0,\) there exists \(a\in A\) such that \(a\in P.\) Hence, \(P=P_a=[a]_R,\) so that \(P\in A/R.\) Thus \(\mathcal P \subseteq A/R,\) so that \(A/R = \mathcal P.\)
We finally conclude that there exist equivalence relations corresponding to any given partition.
After that, we show the uniqueness. Suppose that \(R_1\) and \(R_2\) are two equivalence relations that give rise to \(\mathcal P.\) Let \(a\in A,\) and define \([a]_{R_1}\) and \([a]_{R_2}\) to be the equivalence classes relative to the relation \(R_1\) and \(R_2\), respectively. Then \([a]_{R_1}=P_a=[a]_{R_2}.\) Therefore \(R_1=R_2.\)\(\square\)
Definition 1.3.8. Let \(f:A\to B\) be a function. The. kernel of \(f\) is the relation \(\text{ker}(f)\) on \(A\) defined by
\[\text{ker}(f) = \lbrace (x_1,x_2) \in A \times A : f(x_1)=f(x_2)\rbrace .\]Definition 1.3.9. Let \(R\) be a relation on a set \(A,\) and \(S\) a relation on a set \(B.\) If there is a bijection \(f:A\to B\) such that for all \(x,y\in A,\) if \((x_1,x_2)\in R\) then \((f(x_1),f(x_2))\in S,\) and vice versa, then \((A,R)\) and \((B,S)\) are isomorphic. In this case, we write
\[(A,R)\cong (B,S),\]where \(\cong\) is a relation called isomorphism. Note that isomorphism is an equivalence relation on the class of relational structures.
Exercises
Exercise 1. Define two ordered pairs \((x_0,y_0)\) and \((x_1,y_1)\) of \(\mathbb R^2\) to be equivalent if \(y_0-x_0^2=y_1-x_1^2.\) Check that this is an equivalence relation and describe the equivalence classes.
Solution. It satisfies the conditions described in Definition 1.3.2, so that it is an equivalence relation. Let \((a,b)\in \mathbb R^2.\) Then we define the equivalence class determined by \((a,b)\) as follows:
Since \(y\) depends on \(x,\) we can see that \([(a,b)]\) is a rule of assignment whose domain and image are \(\mathbb R\) and \(\lbrace y\in \mathbb R : y\geq -a^2+ b\rbrace\) respectively.
Exercise 2. Let \(R\) be a relation on a set \(A.\) If \(A_0\subseteq A,\) define the restriction of \(R\) to \(A_0\) to be the relation \(R\cap (A_0\times A_0).\) Show that the restriction of an equivalence relation is an equivalence relation.
Proof. Let \(R\) be an equivalence relation on \(A\) and \(R_0=R\cap (A_0\times A_0)\) where \(A_0\subseteq A.\) Since \(R\cap (A_0\times A_0)\subseteq A_0\times A_0,\) the restriction \(R_0\) is a subset of \(A_0\times A_0.\) Suppose that \(a,b,c\in A_0.\) Since \((a,a)\in R\) and \((a,a)\in A_0\times A_0, (a,a)\in R_0.\) If \((a,b)\in R_0,\) then \((a,b)\in R\) so that \((b,a)\in R.\) Given \((b,a)\in A_0\times A_0,\) it follows that \((b,a)\in R_0.\) If \((a,b)\) and \((b,c)\) are elements of \(R_0,\) then they belongs to \(R,\) so that \((a,c)\in R.\) Since \((a,c)\in A_0\times A_0,\) \((a,c)\in R.\) Consequently, \(R_0\) is an equivalence relation on \(A_0.\) \(\square\)
Exercise 3. Here is a “proof” that every relation \(R\) that is both symmetric and transitive is
also reflexive: “Since \(R\) is symmetric, \(aRb\) implies \(bRa\). Since \(R\) is transitive,
\(aRb\) and \(bRa\) together imply \(aRa\), as desired.” Find the flaw in this argument.
Solution. The proof assumes that \(aRb\) for some \(b.\) That is, symmetry and transitivity only imply \(aRa\) for elements \(a\) that are already related to some element \(b.\) For example, on \(A=\lbrace 1,2\rbrace,\) let \(R=\lbrace (1,1)\rbrace.\) Then \(R\) is symmetric and transitive but it is not reflexive, because \((2,2)\notin R.\)
Exercise 4. Let \(f: A\to B\) be a surjective function. Let us define an equivalence relation on \(A\) by setting \(a_0 \sim a_1\) if \(f(a_0)=f(a_1).\) Let
\[A/{\sim} = \lbrace [x] : x\in A \rbrace.\]Show there is a bijective correspondence of \(A/{\sim}\) with \(B.\)
Proof. Define \(g: A/{\sim} \to B\) by
First, we show that \(g\) is well-defined. Suppose \([a_0] = [a_1].\) Then \(a_0 \sim a_1,\) so by the definition of \(\sim,\) we have \(f(a_0) = f(a_1).\) Hence \(g([a_0]) = g([a_1]).\) Therefore \(g\) is well-defined.
We now show that \(g\) is injective. Suppose \(g([a_0]) = g([a_1]).\) Then \(f(a_0) = f(a_1).\) Thus \(a_0 \sim a_1,\) and hence \([a_0] = [a_1].\) Therefore \(g\) is injective.
Finally, we show that \(g\) is surjective. Let \(b \in B.\) Since \(f\) is surjective, there exists \(a \in A\) such that \(f(a) = b.\) Then \(g([a]) = f(a) = b.\) Thus every element of \(B\) lies in the image of \(g,\) so \(g\) is surjective. Consequently, \(g\) is bijective, and hence there is a bijective correspondence between \(A/{\sim}\) and \(B.\) \(\square\)
Exercise 5. Let \(S\) be the subset of \(\mathbb R^2\) defined by
\[S =\lbrace (x,y)\in \mathbb R^2 : (y = x + 1) \land (0<x<2) \rbrace.\]Describe the equivalence relation \(T\) on \(\mathbb R\) that is the intersection of all equivalence relations on \(\mathbb R\) that contain \(S.\) Describe the equivalence classes of \(T.\)
Solution. Let \(T\) denote the intersection of all equivalence relations on \(\mathbb{R}\) that contain \(S.\) Since every equivalence relation must be reflexive, symmetric, and transitive, \(T\) is exactly the smallest equivalence relation on \(\mathbb{R}\) containing all pairs \((x, x+1)\) with \(0 < x < 2.\)
Since \(S\) contains only pairs \((x,x+1)\) with \(0<x<2,\) in the graph picture, every nontrivial edge has the endpoint \(x\) and \(x+1,\) hence lies inside the interval \((0,3).\) Therefore every \(x\notin (0,3)\) is immediately isolated, so
Once we know the relevant region is the interval \((0,3),\) we examine what kind of graph can be captured in \((0,3).\) We note that the length of an edge is short enough for us to capture two adjacent edges. Thus we find other partitions:
\[[x] = \lbrace x, x+1, x+2\rbrace \qquad (0 < x < 1).\]At this stage, we explicitly record what has been covered: as \(x\) ranges over \((0, 1)\), the elements \(x\), \(x+1\), and \(x+2\) range over \((0, 1)\), \((1, 2)\), and \((2, 3)\), respectively. Therefore the classes cover every non-integer point in \((0, 3)\). That is, only the integer points inside \((0, 3)\) remain, namely \(1\) and \(2\). From the fact that \(1\sim 2,\) but \(0\not\sim 1\) and \(2\not\sim 3,\) we find the last partition:
\[[1]=\lbrace 1,2 \rbrace.\]Equivalently, the relation \(T\) itself can be described as
\[\begin{aligned} T = {}& \Delta_{\mathbb R}\\ &\cup \lbrace (x,x+1),(x+1,x),(x+1,x+2),(x+2,x+1),(x,x+2),(x+2,x):0<x<1\rbrace \\ &\cup \lbrace (1,2),(2,1)\rbrace \end{aligned}\]where \(\Delta_{\mathbb R}\) is the diagonal in \(\mathbb R,\) defined by
\[\Delta_{\mathbb R} = \lbrace (x,x):x\in\mathbb R\rbrace.\]References
- Munkres, J. R. (2000). Topology (2nd ed.). Pearson.
- Rudin, W. (1976). Principles of mathematical analysis (3rd ed.). McGraw-Hill Education.
- Cameron, P. J. (1998). Sets, logic and categories. Springer. https://doi.org/10.1007/978-1-4471-0589-3