# Mathematical Proof/Relations

## Introduction[edit | edit source]

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 *ordered pairs* , where is the husband, while is the wife.

Expressing it mathematically, let and be the set of all men and women respectively.
Then, the *Cartesian product* consists of *all* pairs of people (first and second coordinate is a man and woman respectively).
After that, we know that the record in the marriage registry, , is a subset of .
If a man and a woman form an ordered pair in , say , then it means they are married. Then, it is natural to say that is *related to* .
In other words, if we find that , then it means that they are related *by this relation *.
Also, knowing what 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 as a *relation*. Let us formally define *relation* below.

## Terminologies[edit | edit source]

**Definition.**
(Relation)
A *relation* from a set to a set is a subset of , i.e., .
In particular, when , we say that is a *relation* on , and we have .
If , then we say that is *related* to by , and write .
On the other hand, if , then we say that is *not* related to by , and write .

**Example.**
Let , , and .
Since the set is a subset of , defines a relation from set to set .
Also, in this relation, is related to 1, is related to 1 and 2, is related to 3. Thus, we have and .
But, we have, say or , since .

**Exercise.**

(a) Suggest a set that is *not* a relation from set to set .

(b) Suggest a set that is a relation from set to set .

(a) (, so is not a subset of ).

(b) .

**Exercise.**
Let and be two nonempty sets. Are and relations from to ? Describe the relationships meant by these two sets.

Both and are relations from to since both are subsets of .

For , it means nothing is related, i.e., there is no relationship between elements in and elements in .

For , it means everything is related, i.e., every element in is related to every element in .

**Example.**
Let be a set of all human beings. Then, . Then, is a subset of , and defines the relation for son and (father or mother).

**Example.**
The concept of "less than" defines a relation on . To be more precise, the relation corresponding to this concept is . For instance, but .

**Example.**
The congruence of integers defines a relation on . To be more precise, the corresponding relation is ( with ). For example, when , then but .

**Exercise.**
Consider the relation on , corresponding the concept of "equal to": .

(a) Sketch in the Cartesian coordinate system.

(b) Consider also the relations on corresponding the concept of "less than" and "greater than" respectively. Sketch also and in the graph in (a).

(a) and (b):

y | y=x ########|#####/%%% ########|####/%%%% ########|###/%%%%% ########|##/%%%%%% ########|#/%%%%%%% ########|/%%%%%%%% --------*--------- x #######/|%%%%%%%%% ######/%|%%%%%%%%% #####/%%|%%%%%%%%% ####/%%%|%%%%%%%%% ###/%%%%|%%%%%%%%% *----* |####| |####| : y>x (relation T) *----* *----* |%%%%| |%%%%| : y<x (relation S) *----*

**Remark.**

- The sets give a
*partition*of . As we will see, there is a close relationship between the concept of relation and the concept of partition.

**Example.**
Let .
Define a relation on , .
Express by listing method.

*Solution*.
First, we have . So,

**Exercise.**
Let and .
Consider a relation on defined by

First, . So,

**Definition.**
(Domain and range)
Let be a relation from a set to a set . The *domain* of , denoted by is the subset of defined by

*range*of , denoted by , is the subset of defined by

**Remark.**

- You may have learnt about the
*domain*and*range*for functions. Using the same terminologies for both relations and functions is indeed not a coincidence. This is because a function is actually a relation. That is, a function is indeed just a special case of relation.

**Example.**
Let , , and .
Then, and .

**Example.**
Consider the relation on : .
Then, is the set of all even numbers, and is the set of all even numbers also.

**Exercise.**
Consider the relation on : .
Find and .

and .

**Definition.**
(Inverse relation)
Let be a relation from a set to a set . The *inverse relation* from to is

**Remark.**

- Again, you may have learnt a similar concept (and also a similar notation) for functions:
*inverse functions*. Indeed, inverse functions can be defined as the inverse relation of a function, provided that the inverse relation is also a function. - We can see that the inverse relation is obtained by "reversing" the order of elements in every ordered pair in the original relation.
- When is empty, then the inverse relation is also empty since there is no ordered pair in the empty set.

**Example.**
Let , , and .
Then, the inverse relation is .

**Exercise.**
Construct an example of sets and a nonempty relation from set to set such that .

Take , and . Then, .

## Reflexive, symmetric and transitive relations[edit | edit source]

After introducing the terminologies related to relations, we will study three properties for a relation defined *on* a set.

**Definition.**
(Reflexive, symmetric and transitive)
Let be a set and be a relation defined on . Then,

- is
*reflexive*if for every . - is
*symmetric*if for every , . - is
*transitive*if for every , .

**Exercise.**
Let be a set and be a relation defined on .
Write down the meaning of (i) is not reflexive; (ii) is not symmetric; (iii) is not transitive.

(i) There exists such that .

(ii) There exist such that but .

(iii) There exist such that and , but .

**Example.**
Let , and let a relation defined on be

**Exercise.**
Is transitive? Explain why.

is transitive since

- ;
- .

(There are no more ordered pairs and in the relation , satisfying and .)

**Example.**
The congruence of integers

**Proof.**

**Reflexive**: For every , . So, for every .

**Symmetric**: For every , where is some integer.

**Transitive**: For every ,

**Exercise.**
Which of the properties, reflexive, symmetric and transitive, does each of the following relations possesses? Prove your answer.

(a) .

(b) .

(c) .

(a) is reflexive, not symmetric, and transitive.

**Proof.**

**Reflexive**: For every , . So, .

**Not symmetric**: Take and . Then, , so . However, . So, .

**Transitive**: For every , (this actually follows from the property of "").

(b) is not reflexive, not symmetric, and transitive.

**Proof.**

**Reflexive**: Take . Then, 1 is *not* less than 1 itself. Hence, .

**Not symmetric**: Take and . Then, , so . However, . So, .

**Transitive**: For every , (this actually follows from the property of "").

(c) is reflexive, symmetric and not transitive.

**Proof.**

**Reflexive**: For every ,

**Case 1**: . Then, . So, .

**Case 2**: . Then, . So, .

**Symmetric**: For every , .

**Not transitive**: Take and . Then, and . So, and . However, since , .

**Exercise.**
Let be a relation on a set . Prove or disprove that

(a) if is reflexive, then is reflexive;

(b) if is symmetric, then is symmetric;

(c) if is transitive, then is transitive.

## Equivalence relations and equivalence classes[edit | edit source]

After studying the three properties that a relation on a set can possess, let us focus on those relations that possess *all three* properties.

**Definition.**
(Equivalence relation)
Let be a set. A relation defined on is an *equivalence relation* if it is reflexive, symmetric and transitive.

**Remark.**

- To show that a relation is
*not*an equivalence relation (i.e., to disprove that the relation is an equivalence relation), it suffices to show any one of the following: (i) it is not reflexive; (ii) it is not symmetric; (iii) it is not transitive, by considering the negation of the above definition.

**Example.**
Let . Also let a relation defined on be

**Proof.**

**Reflexive**: Since , is reflexive.

**Symmetric**: Since , , , and , is symmetric.

**Transitive**: Since for every , , is transitive.

**Exercise.**
Give another equivalence relation that is defined on .

. It can be shown to be reflexive, symmetric and transitive.

**Example.**
Since the congruence of integers defines a reflexive, symmetric and transitive relation, it defines an equivalence relation on .

Suppose is an equivalence relation on a set . Intuitively, for elements that are related by , 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 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:

**Definition.**
(Equivalence class)

Let be an equivalence relation defined on a set . For every , the set

*(equivalence) class*of by .

**Example.**
Let , and let a relation defined on be

*distinct*equivalence classes. Graphically, the situation looks like:

*----------** | . . / | | 2 3 / | | . /. | | 1 / 4 | *-----*-----* ^ ^ | | [1]=[2] [4] =[3]

**Exercise.**
Construct an equivalence relation on such that the equivalence classes are given by

. Graphically, the situation looks like:

*---*-------* | .| . | | 2 | 3 | | .\ . | | 1 \ 4 | *-----*-----* ^ ^ | | [1]=[2] [3]=[4]

**Example.**
(Integers modulo )
Recall that the congruence of integers defines an equivalence relation on . Using this equivalence relation, we can define the equivalence class for every , as follows:

- ...

We can observe that starting from , the classes are not distinct from the previous classes. Indeed, if we consider the classes "backward":

- ...

They also do not give new classes.

Hence, we conclude that there are only distinct equivalence classes, namely .
Usually, the set of these equivalence classes, , is denoted by , and is called *integers modulo *. Notice that is a finite set itself, but each of its elements is an infinite set.

**Remark.**

- We can illustrate the equivalence classes as follows (each column is an equivalence class, and the whole table is ):

*----*----*---...---*-----* | . | | | . | | . | | | . | | . | | | . | |-n |-n+1| |-2n-1| | 0 | 1 | .... | n-1 | | n |n+1 | |2n-1 | | . | | | . | | . | | | . | | . | | | . | *----*----*---...---*-----*

- When we consider integers modulo and integers modulo () together, there may be some ambiguities for the elements. For example, and . However, for instance, the "" in and the "" in are different. One of them contains all even numbers, another contains all multiples of 3.

- To avoid such ambiguities, we may add a subscript to the classes. For instance, we may write and .

**Exercise.**
A relation on is defined by

(b) Express each of the equivalence classes by in terms of
(*Hint*: use the symmetric property of ).

**Proof.**

**Reflexive**: For every , since , .

**Symmetric**: For every , since .

**Transitive**: For every ,

(b)

## Properties of equivalence classes[edit | edit source]

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

- When are two equivalence classes equal?
- Can two different equivalence classes contain a common element?

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

**Theorem.**
Let be an equivalence relation defined on a set . For every ,

**Proof.**
"" direction:
Assume . Since is an equivalence relation, and in particular, is reflexive, we have . Thus, we have by definition . Then, since by assumption, we have .

"" direction: Assume . First, for every ,

On the other hand, first, since by assumption, we have by the symmetry of . Now, For every ,

Hence, .

**Remark.**

- From this theorem, we know that "" is the necessary and sufficient condition for "". Also, we have if and only if .

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

**Corollary.**
Let be an equivalence relation defined on a nonempty set . For every ,

**Proof.**
"" direction:

"" direction: We use proof by contrapositive.

**Remark.**

- From this result, we know that two equivalence classes are either equal or disjoint (since they are either equal or not equal). Hence, it is impossible for two different equivalence classes to contain a common element.

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 *partition* of a set:

**Definition.**
(Partition)
A *partition* of a nonempty set is a *set* of *nonempty* subset(s) of with the property that *every* element of belongs to *exactly one* of the subset(s).
In other words, is a collection of *pairwise disjoint* and *nonempty* subset(s) of whose *union is *.

**Example.**
Let . Then, a partition of is . Another one is .
However, is not a partition of since and are not disjoint (or the element "2" belongs to two sets).
Also, is not a partition of since the union of and is not the entire set (or the element "2" does not belong to any of the sets inside the partition).

**Exercise.**
Is a partition of ?

Yes, since every element of belongs to exactly one of the set inside the partition, namely the set .

**Example.**
Let , and let a relation defined on be

*every*element of belongs to

*exactly one*of these equivalence classes. Hence, the set gives a partition of .

Also, we can define another equivalence relation on such that the two distinct equivalence classes are given by

*every*element of belongs to

*exactly one*of these equivalence classes. hence, the set .

**Example.**
Recall that the congruence of integers defines an equivalence relation on .
Also, there are distinct equivalence classes: . By Euclid's division lemma, *every* integer belongs to *exactly one* of these equivalence classes. Thus, the integers modulo

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 can be used to give a partition of that set.

**Theorem.**
Let be an equivalence relation defined on a nonempty set . Then the set
of all distinct equivalence classes by is a partition of .

**Proof.**
It suffices to show that *every* element of belongs to *exactly one* of the distinct equivalence classes.

For every , since is reflexive, we have . From this, we can ensure that every element of belongs to *at least one* of the distinct classes.
It now remains to show that every element of also belongs to *at most one* of the distinct classes.

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

Hence, every in belongs to *exactly one* of the distinct classes, and thus the set of all distinct equivalence classes by gives a partition of .

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:

**Theorem.**
Let be a partition of a nonempty set . Define a relation on by

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

**Reflexive**: By the definition of partition, for every , belongs to *exactly one* of , so there exists such that . Hence, .

**Symmetric**: For every ,

**Transitive**: For every , assume and . Then, there exist such that and . But by the definition of partition, belongs to

*exactly one*of the set in the partition . So, we have . Hence, there exists a set () such that , and thus .

**Example.**
Let be a relation defined on by

(a) Prove that is an equivalence relation.

(b) Determine all distinct equivalence classes by and hence give a partition on .

*Solution*.

**Proof.**
**Reflexive**: For every , . So, .

**Symmetric**: For every , .

**Transitive**: For every , .

(b) First, some equivalence classes are

**Exercise.**
Let be a relation defined on by

(a) Prove that is an equivalence relation.

(b) Determine all distinct equivalence classes by , and hence give a partition on .

**Proof.**
**Reflexive**: For every , since is even, .

**Symmetric**: For every , .

**Transitive**: For every ,

(b) First, some equivalence classes are

**Remark.**

- Recall that the sum of two integers is even if and only if they have the same parity. So, this relation relates every pair of integers that have the same parity. So, intuitively, the relation can partition the integers into two "pieces": set of all odd integers and set of all even integers.