18.6: Activities

Activity \(\PageIndex{1}\)

For each of the relations provided, carry out the following steps.

1. Verify that the relation is an equivalence relation on the set \(A\text{.}\)
2. Consider a few example equivalence classes, for the specific example representative elements provided (if applicable). What other elements are in that class?
3. 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.”
4. List/describe all elements in the quotient \(A/\equiv\text{.}\)

 

1. Relation \(\mathord{\equiv}\) on \(A = \mathbb{Z}\text{,}\) where \(m \equiv n\) means \(m^2 = n^2\text{.}\) Example equivalence classes for \(1, 10, -2, 0\text{.}\)
2. Relation \(\mathord{\equiv}\) on \(A = \mathbb{R} \times \mathbb{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{.}\)
3. Relation \(\mathord{\equiv}\) on \(A = \mathbb{R} \times \mathbb{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{.}\)
4. Relation \(\mathord{\equiv}\) on \(A = \mathscr{P} (\{a,b,c,d\})\text{,}\) where \(X \equiv Y\) means \(\vert X^C \vert = \vert Y^C \vert\text{.}\) Example equivalence classes for \(\emptyset, \{a\}, \{a,b\}, \{a,b,c\}, \{a,b,c,d\}\text{.}\)
5. 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{.}\)
6. Given function \(f: A \rightarrow 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{.}\)

Activity \(\PageIndex{1}\)

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{.}\)

Hint.

When should two different finite sequences be considered equivalent as unordered lists?

Activity \(\PageIndex{1}\)

Suppose \(\mathord{\equiv}\) and \(\mathord{\equiv}'\) are equivalence relations on a set \(A\text{.}\) Determine which of the following are also equivalence relations.

1. \(\mathord{\equiv}^C\)
2. \(\mathord{\equiv} \cup \mathord{\equiv}'\)
3. \(\mathord{\equiv} \cap \mathord{\equiv}' \)

See Activity 17.5.4.