Chapter - 4, Relations

Section - 4.6 - Equivalence Relations


Summary

  • Equivalence Relation: Suppose is a relation on a set . Then is called an equivalence relation on if it is reflexive, symmetric, and transitive.
  • Suppose is a set and . We will say that is pairwise disjoint if every pair of distinct elements of are disjoint, or in other words . is called a partition of if it has the following properties:
    • = A.
    • is pairwise disjoint.
    • .
  • Suppose is an equivalence relation on a set , and . Then the equivalence class of with respect to is the set:
    • . If is clear from context, then we can use instead of . The set of all equivalence classes of elements of is called modulo , and is denoted . Thus,
    • .
  • Suppose is an equivalence relation on a set . Then is a partition of . This is proved using following lemmas:
    • For every .
    • For every and , iff .
  • Suppose is a set and is a partition of . Then there is an equivalence relation on such that . It uses the following lemma:
    • Suppose is a set and is a partition of . Let . Then is an equivalence relation on .

Soln1

,
,
,
,
.


Soln2

For ,
For ,
For ,
For ,
For , .


Soln3

(a) Yes it is a equivalence relation. Equivalence classes = .

(b) It is not an equivalence relation.

(c) This is an equivalence relation. Equivalence classes = .


Soln4

(a) It is not a equivalence relation.

(b) It is an equivalence relation. To find equivalence classes, we know that :

  1. Difference of two rational numbers is always rational.
  2. If we have two real numbers such that one is irrational and other number is rational, then their difference will be irrational.
  3. If we have two irrational numbers then either their difference can be rational or irrational.

From the first two points, the equivalence class is all rational numbers: .

Now, from the third point which I got wrong earlier(Thanks William for pointing out. Check his comment for a better desciption), the equivalance classes in this case should be: , where is the given relation.

(c) It is an equivalence relation. Its equivalnce classes are: , where or equivalently

Thanks William for pointing out. Earlier I got this wrong: .


Soln5

We are given that .

  • :

(). Suppose . Thus there exist atleast one set , where , such that . Thus is a person must be be born on day . It follows that . Thus .

(). Suppose . Thus must/will be born on some day . Thus . It follows that . Thus .

  • , where .

Suppose . Thus there must exist atleast one person who is born on and on . But this is not possible for a person to take birth on two different dates. Thus it contradicts the assumption . Thus .

  • .

Suppose . We can assume here that there is atleast one person born on every day. Thus atleast one person is born on , . Thus .

Now see that .

Thus satisfies all the conditions of a partition.


Soln6

Suppose . Since all the angles of are equal to itself, S $$ is reflexive.

Suppose . Thus all angles of are equal to . Or we can also say that all angles of are equal to , or . Thus is symmetric.

Suppose . Thus all angles of are equal to . Also all angles of are equal to . Thus all angles of are equal to . Thus . We can conclude that is transitive.

Thus is reflexive, symmetric and transitive, we can conclude that is equivalence relation.


Soln7

To complete the proof, we need to prove that is symmetric and transitive.

Suppose . Since , it follows that there exist an such that . Thus and . Thus . It follows that . Thus . We can conclude that is symmetric.

Suppose . Thus and for some and . Thus and . Since is a partition of , it follows that . Thus only if , then and is possible. Thus . It follows that . Thus is transitive.


Soln8

Suppose .

(). Suppose . Since is equivalence relation, it follows that and . Since , it follows that . Since is equivalence relation, must exist in . Also since is a partition and and and and , it follows that . Since , it follows . Thus . Since is arbitrary, it follows that .

(). Suppose . Since is equivalence relation, it follows that and . Since , it follows that . Since is equivalence relation, must exist in . Also since is a partition and and , it follows that . Since , it follows . Thus . Since is arbitrary, it follows that .

Thus and , it follows that .


Soln9 Since is an equivalence relation on , it follows that . Since it is given that , it follows that . Thus by using the result of Soln8, we have .


Soln10

(a)

Reflexive:

Suppose is an integer. Thus , or . Thus for , . It follows that . Thus is reflexive.

Symmetric:

Suppose are integers such that . Thus where . It follows that , or . Since , it follows . Thus . It follows that is symmetric.

(b)

Equivalence classes of :

,
,

Equivalence classes of :

,
,
,

Clearly there are equivalence classes of .


Soln11

Suppose is integer, then is either even or odd. We have following cases:

Case 1: is even.
Thus , where is any integer. It follows that . Thus , where . Thus , or . Thus we can also say .

Case 2: is odd. Thus , where is any natural number. It follows that . Thus , where . Thus , or . Thus we can also say .

Thus from both cases, we have or .


Soln12

Suppose are integers such that and . Thus we have and . Thus and .

Thus , which means , or , where . Thus .

Similarly, we have . It follows that where . Thus .


Soln13

Clearly is a relation on .

(a)

Suppose in B. Thus . Since , and is reflexive, it follows that . Thus . Thus is reflexive.

Suppose . Since , it follows and . Since and is symmetric, it follows that . Also since , it follows . Thus . Thus . We can conclude that is symmetric.

Suppose . Thus and and . Since is transitive, it follows that . Also since , it follows that . Thus . Thus . Thus we can conclude that is transitive.

Since is reflexive, symmetric and transitive, it follows that is equivalence relation.

(b)

Suppose . Since is an equivalence relation on , it follows that .

()Suppose . It follows that . Since , , thus, . Also since , it follows that , thus, . Thus . Since is arbitrary, it follows that .

()Suppose . Thus and . Since (given), and , it follows . Thus we have and , it follows that . Thus . It follows that . Since is arbitrary, we can conclude that .

Since and . We can conclude .


Soln14

(a)

Suppose . Then clearly, . Since , it follows that . Thus is reflexive.

Suppose . Thus . Since , it follows . Thus . It follows that is symmetric.

Suppose . Suppose . Thus or . Thus we have following possible cases:

  • Case 1: and . Since , it follows . Since , it follows .

  • Case 2: and .
    Since , it follows . Since , it follows .

  • Case 3: and .
    Since , it follows . Since , it follows .

  • Case 4: and .
    Since , it follows . Since , it follows .

Thus if , then form all the possible cases above . Thus . It follows that .

Thus is symmetric.

(b)

Existence:

Suppose . Suppose . Clearly because contains only those elements which are in but not in . Now we will prove that . Suppose . Thus we have:

iff.
iff.
iff.
iff.
Since is always false.
iff.
iff.
Since is always false.

Thus if , then . Thus if , then . And we already prove that for , .

Uniqueness:

Suppose , and and and such that . First we will prove that and are not empty. Suppose is empty. Thus . But . Thus . Since is arbitrary, it follows . Since , it follows . But it contradicts with the given that . Thus is not empty. Similarly we can show that is not empty.

Since is symmetric and , thus . Since is transitive and , it follows . Thus . This is true for , but that is not that the case since we assumed . Since and are not empty, we have following possible cases: Suppose . Thus either or . Thus we have following cases:

  • Case 1:
    Thus . Since and we have from above that , it follows that .

  • Case 2:
    Thus . Since and we have from above that , it follows that .

Thus from both cases if then . Thus . But it contradicts with . Thus the assumtion that is wrong. Thus .

Thus there exist a unique such that and .


Soln15

To Prove is a partition of , we need to prove the following three things:

  • .
  • if and and , then .
  • .

Following are the proofs for each of them:

Proof of .

()Suppose . Thus there exist an such that . Since , it follows that either or . Thus we have the following cases:

  • Case 1: . Since and , it follows that . Since is a partition on , . Thus . Or we can also say .

  • Case 2: . Since and , it follows that . Since is a partition on , . Thus . Or we can also say that .

Thus if , then . Thus .

()Suppose . Since and , it follows that either or . Thus we can also say , which is equivalent to . Since was arbitrary, it follows that .

Since and , it follows that .

Proof of: if and and , then .

Suppose and and . Thus we have following possible cases:

  • Case 1: and

Since and is a partition on , it follows that .

  • Case 2: and

Since is a partition on , it follows that . Similarly since is a partition on , it follows that . Since , it follows that .

  • Case 3: and

Since and is a partition on , it follows that .

  • Case 4: and

Since is a partition on , it follows that . Similarly since is a partition on , it follows that . Since , it follows that .

Thus from all the cases above .

Proof of .

Suppose . Thus either or . If , then because is a partition on . Similarly if , since is a partition on .


Soln16

(a) Since is an equivalence relation on , it follows that is a partition of . Similarly since is an equivalence relation on , it follows that is a partition of . Thus we have is a partition of and is a partition of and are disjoint, then from the soln15, it follows that is a partition of . We know that from theorems in this section that if is a partition of , then is an equivalence relation on . Thus, since is a partition on , it follows that is an equivalence relation on .

(b)

Suppose .

()Suppose . Thus . It follows that or . Since and , it follows that . Since is a relation on and , it follows that . Thus , or . Since is arbitrary, it follows that .

()Suppose . Thus . Since , it follows that . Since , it follows . Thus . Thus we can also say that , where . Thus . Since is arbitrary, it follows that .

Since and , it follows that .

Proof of if , then is exactly similar.

(c)

()Suppose . Suppose . Since , is an equivalence relation on , it follows . Since , it follows . Thus . It follows that either or . If , then from part(b), . Similarly if , then from part(b) . Thus or . Since , it follows that either or . If , then because . Similarly if , then because . Thus . Since is arbitrary, it follows that .

()Suppose . Suppose . Thus either or . If , then , then from part(b), . Similarly if , then . Thus from both cases . Since is equivalence relation on , it follows that . Thus .

Thus from both directions, .


Soln17

Proof of .

()Suppose . Thus there exist an in such that . Thus . This follows that . Since , . Thus .

()Suppose . Since is a partition on , it follows that there exist an such that . Similarly since is a partition on , it follows that there exist a , such that . Thus , or . If , then . Since and , it follows that . Thus .

Thus from both sides, .

Proof of is pairwise disjoint.

Suppose and such that . Thus there exist and such that . Similarly there must be and such that . Since is a partition, it follows . Similarly . Suppose . Thus there exist an such that in . Thus and . Thus . Thus . This is a contradiction thus .

Proof of . This is clear from the definition of .

Thus is a partition of .


Soln18

.
.
.


Soln19

(a)

Proof of is reflexive

Suppose . Since is reflexive, it follows that . Similarly since is reflexive, it follows that . Thus . Thus is reflexive.

Proof of is symmetric

Suppose . Thus and . Since and are both symmetric, it follows that . Thus is symmetric.

Proof of is transitive

Suppose and . Thus . Since is transitive, it follows that . Similarly since and is transitive, it follows that . Thus we have . Thus is transitive.

Since is reflexive, symmetric and transitive, it follows that is equivalence relation.

(b)

Suppose .

()Suppose . Thus . Thus and . Since is equivalence relation on and and , it follows that . Similarly since is equivalence relation on and and , it follows that . Thus . Thus .

()Suppose . Thus and . Thus . Since is an equivalence relation on and and , it follows that , or . Thus .

Since and , it follows that .

(c)

Suppose . Thus we have:

. iff
. iff
Since from last part, if then , we have:
. iff
. iff
.

Since is arbitrary, it follows that .


Soln20

Proof of .

()Suppose . Thus there exist an element such that . Since , it follows that there exist an and such that . Since , . Similarly since , . Thus . Thus .

()Suppose . Thus for some set, say, , . Similarly for some set , . Thus . Thus where . Thus . Thus .

Proof of is pairwise disjoint.

Suppose and and . We will prove by contradiction. Suppose . Thus there atleast exist a pair such that and . Since , it follows that for some and , . Similarly since , it follows that for some and , . Since and , it follows that and . Similarly since , it follows that and . Thus and . Since and is a partition on , ans since exist in both and , it follows that . Similarly and , and is a partition on , it follows that . Since and , it follows that because and . This contradicts with . Thus .

Proof of .

Suppose . Thus for some and , . Since is a partition on , it follows that . Similarly since is a partition on , . Thus . Since is arbitrary, it follows that .


Soln21

.

: Bottom left quadrant.
: Top Right quadrant.
: Negative axis
: Bottom left quadrant.
: Top left quadrant.
: Positive axis
: Negative axis
: Positive axis.
: Origin


Soln22

(a)

Reflexive

Suppose . Thus and . Since is equivalence relation on , it follows that . Similarly since is equivalence relation on , it follows . Thus because and . Thus is reflexive.

Symmetric

Suppose . Thus and . Since and are symmetric, it follows that and . Thus . Thus symmetric.

Transitive

Suppose and . Thus , , , . Since and , it follows that because is transitive. Similarly since and , it follows that because is transitive. Thus . Thus is transitive.

(b)

Suppose . Suppose . Thus,

. iff
. iff
. iff
. iff
.

Since is arbitrary, it follows that .

(c)

Suppose . Thus,

. iff
. iff
Using part(b),
. iff
Since and and using the definition of .

Since is arbitrary, it follows that .


Soln23

(a)

For uniqueness proofs, we need to prove two things: Existence and Uniqueness.

We shall prove this using the following strategy: . Here denotes there is a relation such that .

To understand what it means by compatible:
Suppose such that and . Then if iff .

Existence:

Suppose .

Suppose is compatible with .

()Suppose . Thus by our definition of , . Thus and . Because is compatible with and and , it follows that . Thus .

()Suppose such that . Since is an equivalence relation, we have . Thus . Thus we can also say . Thus .

Thus from both directions we have: .

Uniqueness:

Suppose that there is some relation such that . Now we will prove that for proving uniqueness. Suppose such that is true. It follows that must be true. Since and and is a equivalence relation, it follows that and . Also we know that and . Since , thus there atleast exist an element in and there exist atleast an element in such that . Thus we can also say, . But this is same as relation . Thus .

Note: Not sure about the correctness of this proof.

(b)

Suppose such that and . Thus iff . Since is equivalence relation, . Also . Thus iff . But , iff . Thus iff .


Soln24

(a)

Reflexive

Suppose in . Since is reflexive, . Thus . Thus . Thus is reflexive.

Symmetric

Suppose . Thus and . Since and are inverse of each other, and and , it follows that and . Thus , or . Thus is symmetric.


Transitive

Suppose . Thus in and in . Since is transitive, it follows in . Since is transitive, it follows that is also transitive, Thus since in , it follows . Thus . Thus is transitive.

Since is reflexive, symmetric and transitive, it follows that is an equivalence relation.

(b)

From Soln23(a), we know that if is compatible with , then there exist a unique relation such that . Thus if we prove that is compatible with , then such relation exist can be followed from Soln23(a).

Suppose such that and .

()Suppose . Since , it follows . Since , it follows that . Since \land , and is transitive, it follows that . Since , it follows . Since is transitive, it follows . Thus .

()Suppose . Then it can be proved similarly that .

Thus from both direction we have . Thus we can conclude that if , then . Thus is compatible with .

(c)

To prove partial order on , we need to prove that is reflexive, transitive and antisymmetric.

Reflexive:/u>

Suppose . Since is equivalence relation, . Suppose . Thus . Since is reflexive, it follows . Thus . Thus is reflexive.

Transitive

Suppose such that . Suppose . Thus . Since , it follows . Similarly since it follows . Since is transitive, it follows . Since it follows . Thus . Thus is transitive.

Antisymmetric

Suppose such that . Suppose . Thus and . Since , it follows . Similarly since , it follows . Since , it follows that . Thus we have and . Thus . Thus . Since is an equivalence relation, it follows that . Thus . Thus is antisymmetric.


Soln25

(a)

To prove that is preorder we need to prove that is reflexive and transitive.

Suppose . Thus since has atleast as many elements as . Thus is reflexive.

Suppose such that . Thus has atleast as many elements as . Also has atleast as many elements as . Thus has atleast as many elements as . Thus . Thus is transitive.

Since is reflexive and transitive, it follows that is preorder.

(b)

Since , it follows that .

Since is an equivalence relation as prove in Soln24, is a partition of on with every parition containing equal number of elements. Also since creates a partioton on , no set in the partition is empty. Thus we will have many paritions with each partition containing sets with equal number of elements.

Now consider , which is a partial order on . Suppose . It follows that . Thus contains atleast as many elements as . Also since all elements of have same number of elements, it follows that all the elements of will have atleast same number of elements as all elements of . Thus partial order is giving a order to these sets, with initially only those sets having one element followed by the set having two, … and so on.

Suppose . Then either or . Thus either or . Thus is a total order.

contains the maximum number of elements that can have. I am not sure about the number. As I am not sure of the notation . It seems like may contain maximum 100 elements. but need to confirm this.


Soln26

(a)

Reflexive:

Suppose . Suppose . Thus . Thus . Thus is reflexive.

Transitive:

Suppose such that and . Thus for every set , there exist a set such that . Similarly for every set , there exist a set , such that . Thus clearly it follows that for every set there exist a set , such that . Thus . Thus is transitive.

Antisymmetric:

Suppose such that and . Thus and . This is possible only if . Thus is antisymmetric.

Since is reflexive, transitive and antisymmetric, it follows that is partial order.

(b)

()Suppose . Suppose . Thus and . Suppose . Thus . Since , it follows . Thus . Since is arbitrary, it follows that . Since is arbitrary, it follows that . Thus refines .

()Suppose refine . Suppose is an arbitrary partition in . Since refines , suppose , such that . Suppose . Thus . Since , . Thus . Suppose . Thus . Since , it follows . Thus . Thus if then . Thus .

Thus from both directions, we have , iff refines .

(c)

To prove that is the greatest lower bound of the set , if we prove that is the -smallest element in the set , then it will also be the greatest lower bound.

Suppose . Thus there exist a set and such that . Thus and . Thus refines as well as refines . Thus and . Thus is the smallest element of the set . Thus is greatest lower bound of the set .