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$, $\mathrm{♡}$, $\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,

$$\begin{array}{}\text{(eq:Nequal)}& =\stackrel{\text{def.}}{=}\{(a,a)|a\in \mathbb{N}\}.\end{array}$$

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},\mathrm{\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\ne \mathrm{\varnothing }.$
2. (Mutually disjoint) If $X,Y\in \mathcal{C}$ and $X\ne Y$, then $X\cap Y=\mathrm{\varnothing }$.
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{array}{rcl}[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],\\ & ⋮& \end{array}$$

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{array}{rcl}\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{array}$$

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]\ne [z]$, then $[y]\cap [z]=\mathrm{\varnothing }$. we prove the contrapositive: if $[y]\cap [z]\ne \mathrm{\varnothing }$, then $[y]=[z]$. Suppose $[y]\cap [z]\ne \mathrm{\varnothing }$. 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.

■