Skip to main content
Logo image

Exercises 18.7 Exercises

1.

Let \(\mathord{\equiv}\) represent the relation on \(\R\times\R\) where \((x_1,y_1) \equiv (x_2,y_2)\) means \(y_1 - x_1^2 = y_2 - x_2^2\text{.}\)

(a)

Verify that \(\mathord{\equiv}\) is an equivalence relation.

(b)

Describe the equivalence classes \([(0,0)]\text{,}\) \([(0,1)]\text{,}\) and \([(1,0)]\) geometrically as sets of points in the plane.

2.

Given a connected (undirected) graph \(G\text{,}\) we can define a relation on the set \(V\) of vertices in \(G\) as follows: let \(v_1 R v_2\) mean that there exists a trail within \(G\) beginning at vertex \(v_1\) and ending at vertex \(v_2\) that traverses an even number of edges.

(a)

Prove that \(R\) is an equivalence relation on \(V\text{.}\)

(b)

Determine the equivalence classes for this relation when \(G\) is the graph below.
An example graph for vertices equivalent when connected by an “even” trail.

Equivalence relations and classes.

In each of Exercises 3–12, you are given a set \(A\) and a relation \(R\) on \(A\text{.}\) Determine whether \(R\) is an equivalence relation, and, if it is, describe its equivalence classes. Try to be more descriptive than just “\(\eqclass{a}\) is the set of all elements that are equivalent to \(a\text{.}\)

3.

\(A = \{a, b, c\} \text{;}\) \(R = \{(a,a),(b,b),(c,c),(a,b),(b,a)\} \text{.}\)

4.

\(A = \{-1, 0, 1\} \text{;}\) \(R = \{(x,y) | x^2 = y^2\} \text{.}\)

5.

\(A\) is the power set of some set; \(R\) is the subset relation.

6.

\(A = \R \text{;}\) \(x_1 \mathrel{R} x_2 \) means \(f(x_1) = f(x_2) \text{,}\) where \(\funcdef{f}{\R}{\R}\) is the function \(f(x) = x^2 \text{.}\)

7.

\(A\) is some abstract set; \(a_1 \mathrel{R} a_2\) means \(f(a_1) = f(a_2)\text{,}\) where \(\funcdef{f}{A}{B}\) is an arbitrary function with domain \(A\text{.}\)

8.

\(A\) is the set of all “formal” expressions \(a/b\text{,}\) where \(a,b\) are integers and \(b\) is nonzero; \((a/b) \mathrel{R} (c/d) \) means \(ad = bc \text{.}\)
Note: Do not think of \(a/b\) as a fraction in the usual way; instead think of it as a collection of symbols consisting of two integers in a specific order with a forward slash between them.

9.

\(A\) is the power set of some finite set; \(X \mathrel{R} Y\) means \(\card{X} = \card{Y} \text{.}\)

10.

\(A\) is the set of all straight lines in the plane; \(L_1 \mathrel{R} L_2\) means \(L_1\) is parallel to \(L_2\text{.}\)

11.

\(A\) is the set of all straight lines in the plane; \(L_1 \mathrel{R} L_2\) means \(L_1\) is perpendicular to \(L_2\text{.}\)

12.

\(A = \R \cartprod \R \text{;}\) \((x_1,y_1) \mathrel{R} (x_2,y_2)\) means \(x_1^2 + y_1^2 = x_2^2 + y_2^2 \text{.}\)
Hint.
Does the expression \(x^2 + y^2\) remind you of anything from geometry?