Mathematical Proof/Relations

Introduction

Intuitively, relation associates pairs of objects based on some rules and properties. That is, relation suggests some kinds of relationship or connection between two objects. Take marriage as an example. In the marriage registry, there is a record in which the names of husbands are associated with the names of their corresponding wives, to keep track of the marriages. The entries in the record can be interpreted as Template:Colored em $(a,b)$, where $a$ is the husband, while $b$ is the wife.

Expressing it mathematically, let $M$ and $W$ be the set of all men and women respectively. Then, the Template:Colored em $M\times W=\{(a,b):a\in M\text{ and }b\in W\}$ consists of Template:Colored em pairs of people (first and second coordinate is a man and woman respectively). After that, we know that the record in the marriage registry, $R$, is a subset of $M\times W$. If a man and a woman form an ordered pair in $R$, say $(m,w)$, then it means they are married. Then, it is natural to say that $m$ is Template:Colored em $w$. In other words, if we find that $(m,w)\in R$, then it means that they are related Template:Colored em. Also, knowing what $R$ exactly is (we have the record from the marriage registry) is the same as knowing all the husband and wife relationship.

Thus, it is natural to define the set $R$ as a Template:Colored em. Let us formally define Template:Colored em below.

Reflexive, symmetric and transitive relations

After introducing the terminologies related to relations, we will study three properties for a relation defined Template:Colored em a set. Template:Colored definition Template:Colored exercise Template:Colored example Template:Colored example Template:Colored exercise Template:Colored exercise

Equivalence relations and equivalence classes

After studying the three properties that a relation on a set can possess, let us focus on those relations that possess Template:Colored em properties. Template:Colored definition Template:Colored remark Template:Colored example Template:Colored example Suppose $R$ is an equivalence relation on a set $A$. Intuitively, for elements that are related by $R$, they are quite "closely related". Thus, when we consider the set consisting elements that are related to a given element of set A, the elements inside the set are "closely related", so the set, in some sense, forms a "group" of elements that are "relatives". It then appears that we can classify the elements of set $A$ into different such "groups", according to an equivalence relation. As we will see, this is roughly the case. Hence, such "group" is quite important. Now, let us formally define what the "group" is: Template:Colored definition Template:Colored example Template:Colored example Template:Colored remark Template:Colored exercise

Properties of equivalence classes

In this section, we will discuss some properties of equivalence classes. In particular, we will address these two questions:

1. When are two equivalence classes equal?
2. Can two different equivalence classes contain a common element?

The answer to question 1 is given by the following theorem. Template:Colored theorem

Proof. "$\Rightarrow$" direction: Assume $[a]=[b]$. Since $R$ is an equivalence relation, and in particular, is reflexive, we have $aRa$. Thus, we have by definition $a\in [a]$. Then, since $[a]=[b]$ by assumption, we have $a\in [b]$.

"$\Leftarrow$" direction: Assume $aRb$. First, for every $x\in A$, $$\begin{array}{ccc}x\in [a]& ⟹xRa& (\text{definition})\\ & ⟹xRb& (aRb\text{ and }\text{transitivity of }R)\\ & ⟹x\in [b].& (\text{definition})\\ \end{array}$$ So, $[a]\subseteq [b]$.

On the other hand, first, since $aRb$ by assumption, we have $bRa$ by the symmetry of $R$. Now, For every $y\in A$, $$\begin{array}{ccc}y\in [b]& ⟹yRb& (\text{definition})\\ & ⟹yRa& (bRa\text{ and transitivity of }R)\\ & ⟹y\in [a].& (\text{definition})\\ \end{array}$$ So, $[b]\subseteq [a]$.

Hence, $[a]=[b]$.

$◻$

Template:Colored remark Now, let us consider the question 2. The answer to question 2 is, indeed, "No". The following corollary justifies this answer: Template:Colored corollary

Proof. "$\Leftarrow$" direction: $$\begin{array}{ccc}[a]\cap [b]=\varnothing & ⟹[a]\text{ and }[b]\text{ have distinct elements}& ([a]\text{ and }[b]\text{ are nonempty})\\ & ⟹[a]\ne [b].\end{array}$$ ($[a]$ and $[b]$ are nonempty since $R$ is reflexive. So they must contain, at least, $a$ and $b$ respectively.)

"$\Rightarrow$" direction: We use proof by contrapositive. $$\begin{array}{cc}[a]\cap [b]\ne \varnothing & ⟹\mathrm{\exists }x\in [a]\cap [b]\\ & ⟹xRa\text{ and }xRb\\ & ⟹aRx\text{ and }xRb& (R\text{ is symmetric})\\ & ⟹aRb& (R\text{ is transitive})\\ & ⟹[a]=[b].& (\text{above theorem})\\ \end{array}$$

$◻$

Template:Colored remark Now we have reached a key point in studying equivalence relations (and it is probably the major reason for studying equivalence relations at all): using equivalence relation on a set to construct a partition of that set, and vice versa. Before discussing it, let us define Template:Colored em of a set: Template:Colored definition Template:Colored example Template:Colored example Template:Colored example We can observe from the previous examples that equivalence relation of a set can be used to give a partition of that set. The following theorem suggests that, in general, an equivalence relation on a set $A$ can be used to give a partition of that set. Template:Colored theorem

Proof. It suffices to show that Template:Colored em element of $A$ belongs to Template:Colored em of the distinct equivalence classes.

For every $x\in A$, since $R$ is reflexive, we have $x\in [x]$. From this, we can ensure that every element of $A$ belongs to Template:Colored em of the distinct classes. It now remains to show that every element of $A$ also belongs to Template:Colored em of the distinct classes.

Assume that $x$ also belongs to the class $[y]$. Then, we have $xRy$. Since $R$ is an equivalence relation, it means $[x]=[y]$ by a previous theorem. Thus, any two equivalence classes to which $x$ belongs are equal. This means every element of $A$ cannot belong to more than one of the distinct classes.

Hence, every $x$ in $A$ belongs to Template:Colored em of the distinct classes, and thus the set of all distinct equivalence classes by $R$ gives a partition of $A$.

$◻$

The following theorem suggests the converse of the above theorem is also true. To be more precise, we can use a partition of a set to construct an equivalence relation on that set. Before introducing the theorem, let us make some intuitive guesses on how to construct the equivalence relation in this way. First, from the previous theorem, roughly speaking, using an equivalence relation on a set, we can create several "groups" of elements in different classes, in which the elements are "relatives".

Now, given a partition of a set, it means we have several "groups" of elements. Such "grouping" intuitively indicates the elements inside the group are "relatives" in some sense. So, intuitively, a relation that relates the "relatives" seems to make the relation quite "close", and hence an equivalence relation.

The following theorem formalizes this intuition: Template:Colored theorem

Proof. It suffices to prove that $R$ defined in this way is reflexive, symmetric, and transitive.

Reflexive: By the definition of partition, for every $x\in A$, $x$ belongs to Template:Colored em of $S\in P$, so there exists $S\in P$ such that $x\in S$. Hence, $xRx$.

Symmetric: For every $x,y\in A$, $$\begin{array}{cc}xRy& ⟹\mathrm{\exists }S\in P,x,y\in S\\ & ⟹\mathrm{\exists }S\in P,y,x\in S\\ & ⟹yRx.\end{array}$$ Transitive: For every $x,y,z\in A$, assume $xRy$ and $yRz$. Then, there exist $S,T\in P$ such that $x,y\in S$ and $y,z\in T$. But by the definition of partition, $y$ belongs to Template:Colored em of the set in the partition $P$. So, we have $S=T$. Hence, there exists a set $S$ ($=T$) such that $x,z\in S$, and thus $xRz$.

$◻$