For each of the relations provided, carry out the following steps.
Verify that the relation is an equivalence relation on the set \(A\text{.}\)
Consider a few example equivalence classes, for the specific example representative elements provided (if applicable). What other elements are in that class?
Devise a general way to describe every equivalence class, using your experience from the example classes already considered (if applicable). Make your class descriptions more meaningful than just “all elements equivalent to a specific representative element.”
List/describe all elements in the quotient \(A/\equiv\text{.}\)
(a)
Relation \(\mathord{\equiv}\) on \(A = \Z\text{,}\) where \(m \equiv n\) means \(m^2 = n^2\text{.}\) Example equivalence classes for \(1, 10, -2, 0\text{.}\)
(b)
Relation \(\mathord{\equiv}\) on \(A = \R \times \R\text{,}\) where \((x_1,y_1) \equiv (x_2,y_2)\) means \(x_1^2 + y_1^2 = x_2^2 + y_2^2\text{.}\) Example equivalence classes for \((1,1), (3,4), (\sqrt{2}/2,-\sqrt{2}/2), (0,0)\text{.}\)
(c)
Relation \(\mathord{\equiv}\) on \(A = \R \times \R\text{,}\) where \((x_1,y_1) \equiv (x_2,y_2)\) means \(y_1^2 - x_1 = y_2^2 - x_2\text{.}\) Example equivalence classes for \((0,0), (0,1), (1,-1)\text{.}\)
(d)
Relation \(\mathord{\equiv}\) on \(A = \powset{\{a,b,c,d\}}\text{,}\) where \(X \equiv Y\) means \(\abs{\cmplmnt{X}} = \abs{\cmplmnt{Y}}\text{.}\) Example equivalence classes for \(\emptyset, \{a\}, \{a,b\}, \{a,b,c\}, \{a,b,c,d\}\text{.}\)
(e)
Relation \(\mathord{\equiv}\) on the vertex set \(A = V\) of a graph \(G\text{,}\) where \(v \equiv v'\) means there exists a path in \(G\) from \(v\) to \(v'\text{.}\)
(f)
Given function \(\funcdef{f}{A}{B}\text{,}\) the relation \(\mathord{\equiv}\) on the domain \(A\text{,}\) where \(a_1 \equiv a_2\) means \(f(a_1) = f(a_2)\text{.}\)
Activity18.2.
A sequence from a set \(A\) could also be called an ordered list. For example, given distinct \(a_1,a_2 \in A\text{,}\) the finite sequences \(a_1,a_1,a_2\) and \(a_1,a_2,a_1\) are different sequences, because order matters in a sequence. However, as an unordered list, \(a_1,a_1,a_2\) is the same as \(a_1,a_2,a_1\text{.}\)
Write \(\mathscr{S}_A\) for the set of all finite sequences from \(A\text{.}\) Devise an equivalence relation \(\mathord{\equiv}\) on \(\mathscr{S}_A\) such that the quotient set \(\mathscr{S}_A / \mathord{\equiv}\) represents the set of all finite unordered lists from \(A\text{.}\)
When should two different finite sequences be considered equivalent as unordered lists?
Activity18.3.
Suppose \(\mathord{\equiv}\) and \(\mathord{\equiv}'\) are equivalence relations on a set \(A\text{.}\) Determine which of the following are also equivalence relations.
