Suppose that \(\approx\) is an equivalence relation on a set \(S\).

1. For every \(x \in S\) and \(y \in S\), \([x] = [y]\) if \(x \approx y\) and \([x] \cap [y] = \emptyset\) otherwise.
2. \(\bigcup_{x \in S} [x] = S\).

Suppose that \(\mathscr{S}\) is a collection of non-empty sets that partition a given set \(S\). The relation defined below is an equivalence relation on \(S\):

\[ x \approx y \text{ if and only if } x \in A \text{ and } y \in A \text{ for some } A \in \mathscr{S} \]

The process of forming a partition from an equivalence relation, and the process of forming an equivalence relation from a partition are inverses of each other.

1. If we start with an equivalence relation \(\approx\) on \(S\), form the associated partition, and then construct the equivalence relation associated with the partition, then we end up with the original equivalence relation. In modular notation, \(S / (S / \approx) = \; \approx\).
2. If we start with a partition \(\mathscr{S}\) of \(S\), form the associated equivalence relation, and then form the partition associated with the equivalence relation, then we end up with the original partition. In modular notation, \(S / (S / \mathscr{S}) = \mathscr{S}\).

Suppose that \(S\) is a nonempty set.

1. Equality (\(=\)) is an equivalence relation on \(S\) and that \([x] = \{x\}\) for each \(x \in S\)
2. The trivial relation \(\approx\) on \(S\) is defined by \(x \approx y\) for all \(x, \; y \in S\). The relation \(\approx\) is an equivalence relation on \(S\) with only one equivalence class, namely \(S\) itself.

Suppose that \(f: S \to T\). Define a relation \(\approx\) on \(S\) by \(t \approx x\) if and only if \(f(t) = f(x)\).

1. The relation \(\approx\) is an equivalence relation on \(S\).
2. The set of equivalences classes is \(\mathscr{S} = \{f^{-1}\{y\}: y \in \text{range}(f)\}\).
3. Define the function \(F: \mathscr{S} \to T\) by \(F([x]) = f(x)\). Then \(F\) is well-defined and is one-to-one.

Suppose again that \(f: S \to T\).

1. If \(f\) is one-to-one then the equivalence relation associated with \(f\) is the equality relation, and hence \([x] = \{x\}\) for each \(x \in S\).
2. If \(f\) is a constant function then the equivalence relation associated with \(f\) is the trivial relation, and hence \(S\) is the only equivalence class.

Give the equivalence classes explicitly for the functions from \(\R\) into \(\R\) defined below:

1. \(f(x) = x^2\).
2. \(g(x) = \lfloor x \rfloor\).
3. \(h(x) = \sin(x)\).

Suppose that \(I\) is a fixed interval of \(\R\), and that \(S\) is the set of differentiable functions from \(I\) into \(\R\). Consider the equivalence relation associated with the derivative operator \(D\) on \(S\), so that \(D(f) = f^{\prime}\). For \(f \in S\), give a simple description of \([f]\).

Let \(d\) be a positive integer. Define the relation \(\equiv_d\) on the set of integers \(\Z\) by \(m \; \equiv_d \; n\) if and only if \(d \mid (n - m)\).

1. The relation \(\equiv_d\) is an equivalence relation.
2. The set of distinct equivalence classes is \(\{\{k + n\,d: n \in \Z\}: k \in \{0, 1, \ldots, d - 1\}\).
3. Let \(r: \Z \to \{0, 1, \ldots, d - 1\}\) be defined so that \(r(n)\) is the remainder when \(n\) is divided by \(d\). The relation \(\equiv_d\) is the equivalence relation associated with the function \(r\).

The equivalence relation \(\equiv_d\) is known as congruence modulo \(d\).

Suppose that \(\approx\) is an equivalence relation on a set \(S\). Define \(f: S \to \mathscr{P}(S)\) by \(f(x) = [x]\). Then \(\approx\) is the equivalence relation associated with \(f\).

Suppose that \(\approx\) and \(\cong\) are equivalence relations on a set \(S\). Let \(\equiv\) denote the intersection of \(\approx\) and \(\cong\) (thought of as subsets of \(S \times S\)). Equivalently, \(x \equiv y\) if and only if \(x \approx y\) and \(x \cong y\).

1. \(\equiv\) is an equivalence relation on \(S\).
2. \([x]_\equiv = [x]_\approx \cap [x]_\cong\).

Suppose that \(\preceq\) is a relation on a set \(S\) that is reflexive and transitive. Define the relation \(\approx\) on \(S\) by \(x \approx y\) if and only if \(x \preceq y\) and \(y \preceq x\).

1. The relation \(\approx\) is an equivalence relation on \(S\).
2. Suppose that \(A\) and \(B\) are equivalence classes. If \(x \preceq y\) for some \(x \in A\) and \(y \in B\), then \(u \preceq v\) for all \(u \in A\) and \(v \in B\).
3. Now define a relation \(\preceq\) on the collection of equivalence classes \(\mathscr{S}\) by \(A \preceq B\) if and only if \(x \preceq y\) for some (and hence all) \(x \in A\) and \(y \in B\). Then \(\preceq\) is a partial order on \(\mathscr{S}\).

Suppose that \(S\) and \(T\) are sets and that \(\preceq_T\) is a partial order on \(T\). Suppose also that \(f: S \to T\). Define the relation \(\preceq_S\) on \(S\) by \(x \; \preceq_S \; y\) if and only if \(f(x) \; \preceq_T \; f(y)\). The relation \(\preceq_S\) is reflexive and transitive. The equivalence relation on \(S\) constructed in the previous exercise is the equivalence relation associated with the function \(f\). Hence the relation \(\preceq_S\) can be extended to a partial order on the equivalence classes corresponding to \(f\).

Row equivalence is an equivalence relation on \(\R^{m \times n}\).

Proof.

Note that each row operation can be reversed by another row operation.

Similarity is an equivalence relation on \(\R^{n \times n}\).

Define a relation \(\approx\) on \(\Z \times \N_+\) by \((j, k) \approx (m, n)\) if and only if \(j\,n = k\,m\).

1. The relation \(\approx\) is an equivalence relation.
2. Now define \(\frac{m}{n}\) to be the equivalence class generated by \((m, n)\), for \(m \in \Z\) and \(n \in \N_+\). This definition agrees with the usual notion of equality of rational numbers.
3. The usual definitions for addition and multiplication of rational numbers are consistent. That is, these definitions are independent of the particular representatives used for the equivalence classes.