Friday, September 28, 2012

All about equivalence relations

Lecture notes for lecture #11 of MATH 235, normally taught by Henri Darmon, but with Miljan Brakočević temporarily filling in while Darmon is away for a week. These lecture notes are student-generated and any errors or omissions should be assumed to be the fault of the notetaker and not of the lecturer. To correct an error, you have to be registered and logged-in; alternatively, you can contact @dellsystem directly.

In this lecture, we finished section 12 and started section 13 of the notes.

1Equivalence relations¶

(Continued from last class)

1.1Disjoint unions¶

We define a disjoint union as the union of subsets that are pairwise disjoint (for all subsets $U_i$ and $U_j$ where $i \neq j$, we have that $U_i \cap U_j = \varnothing$).

If $S$ is a disjoint union of its subsets $U_i$, we can write that as

$$S = \bigsqcup_{i \in I} U_i$$

In other words, if a set can be partitioned into various distinct subsets that have no overlap, then the set can be considered a disjoint union of those subsets.

1.2Equivalence classes¶

Now we define the concept of an equivalence class. For any element $x \in S$, its equivalence class is given by

$$[x] = \{y \in S: x \sim y\}$$

1.3Lemma 12.0.6¶

We now move on to proving some things about disjoint unions and equivalence classes. From section 12.0.6 of the notes, we have the following lemma:

1. Any 2 equivalence classes are either disjoint or equal.
2. $S$ is the disjoint union of its equivalent classes.
3. If $S'$ is a disjoint union of subsets $S'_i, i \in I$, then there is a unique equivalence relation for which each $S'_i$ for $i \in I$ is an equivalence class.

We now prove each part separately:

1. Let $x, y$ be two distinct elements $\in S$. We want to prove that either $[x] \cap [y] = \varnothing$ or $[x] = [y]$ (that they are either disjoint, or equal). We assume that their intersection is not the empty set (if it is, the proof is complete), i.e., there exists a $z \in [x] \cap [y]$. This means that $x \sim z$, and that $y \sim z$. By the symmetry of equivalence relations, we also know that $z \sim y$. By transitivity, $x \sim z$ and $z \sim y$ and so $x \sim y$, which means that $[y] \subseteq [x]$. But we can use this same reasoning in the other direction to conclude that $[x] \subseteq [y]$. Consequently, it must be that for any two distinct elements $x, y \in S$, either $[x] \cap [y] = \varnothing$ or $[x] = [y]$. $\blacksquare$
2. In part 1, we proved that any two equivalence classes are pairwise disjoint. Now we just have to show that $S$ is the union of these equivalence classes, i.e., that all the elements in $S$ are contained in one equivalence class. This is trivial, for any element $x \in S$ does belong to one equivalence class, by reflexivity: its own, $[x]$. So $S$ is the disjoint union of its equivalence classes. $\blacksquare$
3. Let $\displaystyle S' = \bigsqcup_{i \in I} S'_i$. We define a relation $\sim$ as follows: $x \sim y$ if there exists a $S'_i$ that contains both $x$ and $y$ (so if $x$ and $y$ are found in the same partition). To show that this relation is an equivalence relation, we have to show that it is reflexive (r), symmetric (s), and transitive (t). (A proof of the uniqueness property was not given in class, but it seems fairly obvious from the fact that relations are completely defined by their set of ordered pairs, etc.)
   • (r): That $x \sim x$ is fairly trivial to show. $x$ is obviously in the same subset as itself.
   • (s): This is also pretty obvious, even tautological. If $x$ and $y$ are in the same subset, then so are $y$ and $x$.
   • (t): If $x \sim y$, then there exists a subset $S'_i$ such that $x, y \in S'_i$. Also, if $y \sim z$, then there exists a subset $S'_j$ such that $y, z \in S'_j$. Consequently, $y \in S'_i$ and $y \in S'_j$, and so $S'_i$ and $S'_j$ have a non-empty intersection. From the pairwise-disjoint property of subsets of a disjoint union, this implies that $S'_i = S'_j$. We conclude that $x, y$ and $z$ are all elements of $S'_i = S'_j$, and it follows trivially that $x$ and $z$ are both elements of the same subset $\therefore x \sim z$.

1.4Complete sets of representatives¶

A subset of $S$ is a complete set of representatives if it contains one¹ element from each of the equivalence class.

2Congruence relations¶

(Technically, this is a subset of equivalence relations, but it's a new section - section 13 - in the notes, so it'll be a new section here as well.)

The most basic example of a congruence relation is the modulo relation. We fix an integer $n \in \mathbb{N}$. Then, $x \sim y$ is equivalent to $n | x-y$ (where $|$ means "divides"). So $x \sim y$ means that $x$ and $y$ have the same remainder when divided by $n$.

We can use a special symbol for this relation: $\equiv$. Specifically, we say that $x \equiv y \mod n$ iff $n|x -y$ (although we can omit the $\mod n$ part if it is known from the context).

2.1Lemma 13.0.7¶

Now let's prove some things about this relation:

1. This relation defines an equivalence relation on $\mathbb{Z}$.
2. A complete set of representatives is given by $\{0, 1, \ldots, n-1\}$.

1. As before, we just have to prove reflexivity (r), symmetry (s), and transitivity (t):
   • (r): $x \equiv x$ because $x - x = 0$ and 0 is divisible by any $n \in \mathbb{N}$.
   • (s): Let $x \equiv y$. So $n | x - y$. Then $n$ also divides the negative of $x-y$, from the definition of "divides", and so $n | -(x-y) \, \therefore n | y - x$. So $y \equiv x$.
   • (t): Given that $x \equiv y$, and $\equiv z$, we have that $n | x - y$ and $n | y-z$. From something we proved in a previous lecture regarding divisors (I will find the specific link one day), we can conclude that $n| (x-y) + (y-z)$. But this simplifies to $n | x - z$, and so $x \equiv z$, which proves the transitivity property. $\blacksquare$
2. From the division algorithm, we know that we can write any integer $x$ as $x = qn + r$ where $0 \leq r < n$. Then, $x - r = qn$ which is divisible by $n$, and so $x \equiv r$. It follows that for every $r$ such that $0 \leq r < n$, i.e., $\{0, 1, \ldots, n-1\}$, there is an equivalent class, and that these equivalence classes are disjoint. (This part of the proof needs to be expanded.)