Relations

In order to study the elements of a set, we compare or relate each element with others. We already know some relations such as "\(=\)" (equal), "\(<\)" (less than), "\(\subset\)" (subset), etc.  We generalize this idea. A relation is defined on a set. For example, \(<\) is (usually) used for comparing two numbers that are well-ordered. So \(<\) is defined on \(\mathbb{R}\), for example. Similarly, \(\subset\) is the subset relation, so it is defined on a set of sets.

To denote a relation in general, we often use the symbol \(\sim\). But there is nothing special about this particular symbol. We could instead use \(\bowtie\), \(\heartsuit\), \(\equiv\), etc. Or we can use any alphabets like \(A, b, \rho,\cdots\).

Instead of writing \(a < b\), we could write \(a~ \mathcal{L}~ b\) (as long as everybody agrees on this convention). It's just a matter of definition.

But what is a relation, anyway?

Definition (Relation)

A relation \(R\) on a set \(S\) is a subset of \(S\times S\). If \((a,b)\in R\), we write \(aRb\).

Example. Consider \(=\) ("equal")on \(\mathbb{N}\). We define this relation as \(\{(a, a) | a \in \mathbb{N}\}.\) That is,

\[ = \stackrel{\text{def.}}{=} \{(a, a) | a \in \mathbb{N}\}. \tag{eq:Nequal}\]

Here, the left-most "\(=\)" is the relation being defined, "\(\stackrel{\text{def.}}{=}\)" means "definition," and the right-most set is the subset of \(\mathbb{N}\times \mathbb{N}\) that defines the left-hand side. To avoid confusion, let us define the set \(E\) by

\[E = \{(a, a) | a \in \mathbb{N}\}.\]

Then, for any \(a, b\in\mathbb{N}\), "\(a = b\)" if and only if \((a,b) \in E\). In this case, we write \(aEb\), but rename "\(E\)" as "\(=\)" so we write "\(a = b\)" instead. This is what (Eq:Nequal) means.

Example. Consider "\(<\)" (less than) on \(\mathbb{Z}\). We can define this relation by

\[ < \stackrel{\text{def.}}{=} \{(a,b) | a, b \in \mathbb{Z}, \exists c\in\mathbb{N} ~ (a + c = b)\}.\]

That is, if there is some natural number \(c\) such that \(a + c = b\), then \((a, b) \in <\), or \(a < b\).

Among various relations, the following class of relations is important.

Definition (Equivalence relation)

A relation \(\sim\) on a set \(S\) is said to be an equivalence relation if it satisfies the following three conditions.

1. (Reflexivity) \(a \sim a\) for all \(a \in S\).
2. (Symmetry) For all \(a, b\in S\), if \(a \sim b\), then \(b \sim a\).
3. (Transitivity) For all \(a, b, c\in S\), if \(a \sim b\) and \(b \sim c\), then \(a \sim c\).

In this case, if \(x \sim y\), we say "\(x\) is equivalent to \(y\)," or "\(x\) and \(y\) are equivalent."

Example. \(=\) (equal) on \(\mathbb{Z}\) is an equivalence relation.

Example. \(<\) (less than) on \(\mathbb{Z}\) is not an equivalence relation. It is neither reflexive nor symmetric, although it is transitive.

Example (mod3). Let us define a relation \(\equiv\) on \(\mathbb{Z}\) as follows. For any \(a, b\in \mathbb{Z}\), \(a \equiv b\) if and only if \(a - b\) is divisible by 3. For example, \(1 \equiv 4\), \(0 \equiv 3\), \(-1 \equiv 2\), etc. We show that this is an equivalence relation. For any \(a\in\mathbb{Z}\), \(a - a = 0 = 3\cdot 0\). Hence, \(a \equiv a\). If \(a \equiv b\), then \(a - b = 3k\) for some integer \(k\). Thus, \(b - a = 3(-k)\), and hence \(b \equiv a\). Finally, if \(a \equiv b\) and \(b \equiv c\), then \(a - b = 3k\) and \(b - c = 3l\) for some \(k, l\in \mathbb{Z}\). Thus, \(a - c = (a - b) + (b - c) = 3k + 3l = 3(k+l)\). Hence, \(a \equiv b\). Thus, \(\equiv\) is an equivalence relation.

Equivalence relations are useful for classifying elements of a set. But, what do we mean by "classification"?

Definition (partition)

Let \(S\) be a set. A partition of \(S\) is a collection \(\mathcal{C}\) of subsets of \(S\) with the following properties.

1. (Non-empty) If \(X\in \mathcal{C}\), then \(X \neq \emptyset.\)
2. (Mutually disjoint) If \(X, Y\in \mathcal{C}\) and \(X\neq Y\), then \(X\cap Y = \emptyset\).
3. (Collectively exhaustive) The union of all elements of \(\mathcal{C}\) is equal to \(S\). That is, \[\bigcup_{X\in \mathcal{C}}X = S.\]

Remark. \(\bigcup_{X\in \mathcal{C}}X\) means the union of all elements of \(\mathcal{C}\): \(X\cup Y\cup \cdots\) where \(X, Y, \cdots \in \mathcal{C}\). For example, if \(\mathcal{C}\) consists of 3 elements, \(\mathcal{C} = \{A_1, A_2, A_3\}\), then \[\bigcup_{X\in\mathcal{C}}X = A_1\cup A_2\cup A_3.\]

Definition (Equivalence class)

Let \(\sim\) be an equivalence relation on a set \(S\). For each element \(x\in S\), the subset of \(S\) defined by \[[x] = \{ y \in S | y \sim x\}\] is called the equivalence class of \(x\) by \(\sim\). In other words, the equivalence class of \(x\) by \(\sim\) is the set of all elements that are equivalent to \(x\).

Example. Consider the equivalence relation \(\equiv\) in Example (mod3) above. Then, \[\begin{eqnarray} [0] &=& \{ y \in \mathbb{Z} | y \equiv 0\} = \{\cdots, -6, -3, 0, 3, 6, 9, \cdots\}.\\ [1] &=& \{ y \in \mathbb{Z} | y \equiv 1\} = \{\cdots, -5, -2, 1, 4, 7, 10, \cdots\},\\ [2] &=& \{ y \in \mathbb{Z} | y \equiv 2\} = \{\cdots, -4, -1, 2, 5, 8, 11, \cdots\},\\ [3] &=& \{ y \in \mathbb{Z} | y \equiv 3\} = [0],\\ [4] &=& [1],\\ [5] &=& [2],\\ &\vdots& \end{eqnarray}\]

As we see in the above example, by changing the value \(x\), we may or may not have different equivalence classes. The set of all equivalence classes in \(S\) by \(\sim\) is denoted by \(S/\sim\), which is often called the quotient set of \(S\) by \(\sim\).

Example. Again, consider the equivalence relation \(\equiv\) on \(\mathbb{Z}\) in (mod3). The quotient set \(\mathbb{Z}/\equiv\) is given by

\[\begin{eqnarray} \mathbb{Z}/\equiv &=& \{\{\cdots, -6, -3, 0, 3, 6, \cdots\}, \{\cdots, -5, -2, 1, 4, 7, \cdots\}, \{\cdots, -4, -1, 2, 5, 8, \cdots\}\}\\ &=& \{\{3k | k \in \mathbb{Z}\}, \{3k + 1| k \in \mathbb{Z}\}, \{3k + 2 | k \in \mathbb{Z}\}\}. \end{eqnarray}\]

Note that integers are "classified" according to their remainder when divided by 3.

In fact, we have the following theorem.

Theorem

Let \(\sim\) be an equivalence relation on a set \(S\). Then, \(S/\sim\) is a partition of \(S\). 

Proof. We check the three properties of the partition.

1. For any \(x \in S\), we have \(x \sim x\), and hence \(x \in [x]\). Thus, each equivalence class \([x]\) is non-empty.
2. "Mutually disjoint" means that, if \([y] \neq [z]\), then \([y]\cap[z] =\emptyset\). we prove the contrapositive: if \([y]\cap[z]\neq \emptyset\), then \([y] = [z]\). Suppose \([y] \cap [z] \neq \emptyset\). Then, we may choose some \(x \in [y]\cap[z]\). Since \(x \in [y]\), we have \(x \sim y\).  Since \(x \in [z]\), we have \(x \sim z\). By symmetry and transitivity, we have \(y \sim z\). For all \(a \in [y]\), we have \(a \sim y\), hence \(a \sim z\), hence \(a \in [z]\). Therefore, \([y] \subset [z]\). Similarly, for all \(b \in [z]\), we have \(b\sim z\), hence, \(b \sim y\), hence \(b \in [y]\). Therefore, \([z] \subset [y]\). Thus, \([y] = [z]\).
3. For any \(x \in S\), we have \(x \in [x] \in S/\sim\). Thus, each \(x\in S\) belongs to precisely one of the equivalence classes. Thus, \(S/\sim\) is collectively exhaustive.

■