2. Equivalence relations

Definition. A binary relation on a set $X$ is any rule by which some pairs are declared to be related and others not related³. Some examples for $X = \mathbb{R}$ are (i) the relation $<$, (ii) the relation $\geq$, (iii) the equality relation (where elements are related only to themselves), and (iv) the $\neq$ relation. If the name of the relation is $\rho$, we can write $x \rho y$ to mean $x$ and $y$ are related by $\rho$.

Some useful properties that a relation $\rho$ can have are as follows. (As usual, it is understood that they mean for all $x$, or for all $x, y$, etc.)

(1) $x \rho x$	``$\rho$ is reflexive''
(2) $x \rho y \Rightarrow y \rho x$	``$\rho$ is symmetric''
(3) $x \rho y$ and $y \rho z \Rightarrow x \rho z$	``$\rho$ is transitive''

Problem V-15. For each of examples (i) through (iv), which of properties (1), (2), (3) hold?

Definition. A relation $\rho$ is an equivalence relation if all three of (1), (2), (3) hold.

Problem V-16. Which of the following examples (i)-(xi) are equivalence relations on $X$? (Explain why or why not.)

(v) $X = \mathbb{Z}$ and $x \rho y$ means $x - y$ is even.

(vi) $X$ is any set, $Y$ is any set, $f:X\rightarrow Y$ is any function, and $x _ 1 \rho x _ 2$ means $f(x _ 1) = f(x _ 2)$.

(vii) $X = \mathbb{R}^2$, there is a subspace $W$ of $X$, and $x \rho y$ means $x - y \in W$.

(viii) $X =$   Mats$(m \times n)$ and $A \rho B$ means that $A$ is row-equivalent to $B$; in other words, $A$ and $B$ have the same row space, which is the same as saying they have the same row-reduced echelon form.

(ix) $X =$   Mats$(n \times n)$ (square!) and $\rho$ is ``similarity'' $\sim$, where $A \sim B$ means $P^{-1} A P = B$ for some invertible $n \times n$ matrix $P$

(x) $X$ is any set and every two elements are related by $\rho$.

(xi) $X$ is any set, subsets $B _ i$ partition $X$, and $x \rho y$ means that $x$ and $y$ are in the same block.

Problem V-17. What is wrong with the following ``proof'' that a symmetric, transitive relation is reflexive? ``If $x \rho y$ then also $y \rho x$ by symmetry, and then $x \rho y$ and $y \rho x$ together imply $x \rho x$ by transitivity''.

The real purpose of equivalence relations is to be able to describe partitions easily, as in (xi) above:

Theorem. Suppose $\rho$ is an equivalence relation on a set $X$. For each $x \in X$, define the block of $x$ to be $B _ x = \{y \in X \vert x \rho y\}$. Then (i) the distinct blocks of this kind form a partition of $X$, and (ii) the equivalence relation derived from this partition as in (xi) above is $\rho$.

Thus each equivalence relation corresponds to a partition and vice-versa. Notice that in the theorem, two different elements may give the same block, but we use just one copy of each block.

A common terminology is to call the blocks ``equivalence classes'', but this conflicts with the word ``classes'' as it is used in set theory.

Problem V-18. Prove the theorem.

Problem V-19. Where possible, tie the examples of equivalence relations given above to the examples of partitions from Problem Q-2.

Problem V-20. Prove that for any integer $n > 0$, ``congruence modulo $n$'' is an equivalence relation. Specifically, $x \equiv y \pmod n$ means that $n \vert (y-x)$ (i.e., $n$ divides $y-x$, meaning that there is some $q \in \mathbb{Z}$ with $y - x = qn$). Use any reasonable properties of integer division. Remember, you can divide into 0 but not by 0.