9.5 Equivalence Relations

Question 1

Equivalence Relation :

when do they arise: what do they do to a set?

Answer 1

A relation on a set A is called an equivalence relation if it is reflexive, symmetric, and
transitive.

such relations split sets into disjoint classes of equivalent elements.
Equivalence relations arise
whenever we care only whether an element of a set is in a certain class of elements, instead of
caring about its particular identity.

Question 2

Definition:

notion of equivalent elements….. notation..

Answer 2

Two elements a and b that are related by an equivalence relation are called equivalent.

The
notation a ∼ b is often used to denote that a and b are equivalent elements with respect to a
particular equivalence relation.

Question 3

For the notion of equivalent elements to make sense, :

when are the times when we can say elements are equivalent

( look at the definition and reason it..)

Answer 3

For the notion of equivalent elements to make sense, every element should be equivalent to
itself, as the reflexive property guarantees for an equivalence relation. It makes sense to say
that a and b are related (not just that a is related to b) by an equivalence relation, because
when a is related to b, by the symmetric property, b is related to a. Furthermore, because an
equivalence relation is transitive, if a and b are equivalent and b and c are equivalent, it follows
that a and c are equivalent.

Question 4

Equivalence Class:

representative?

Answer 4

Let R be an equivalence relation on a set A. The set of all elements that are related to an
element a of A is called the equivalence class of a. The equivalence class of a with respect
to R is denoted by [a]R. When only one relation is under consideration, we can delete the
subscript R and write [a] for this equivalence class.

[a]R = {s ∣ (a, s) ∈ R}.

-If b ∈ [a]R, then b is called a representative of this equivalence class. Any element of a class
can be used as a representative of this class. That is, there is nothing special about the particular
element chosen as the representative of the class.

Question 5

Theorem 1

the equivalent statements for a,b belongs to A, R Eq Relation on A.

Answer 5

Let R be an equivalence relation on a set A. These statements for elements a and b of A are
equivalent:
(i) aRb (ii) [a] = [b] (iii) [a] ∩ [b] ≠ ∅

prove it, that they are all equivalent.

Question 6

partition and the theory of it:

Answer 6

The union of the equivalence classes of R is all of A, because
an element a of A is in its own equivalence class, namely, [a]R. In other words,
⋃a∈A [a]R = A.

equivalence classes are either equal or disjoint
[a]R ∩ [b]R = ∅,
when [a]R ≠ [b]R.

These two observations show that the equivalence classes form a partition of A, because they split A into disjoint subsets.
More precisely, a partition of a set S is a collection of disjoint
nonempty subsets of S that have S as their union. In other words, the collection of subsets Ai
,
i ∈ I (where I is an index set) forms a partition of S if and only if
Ai ≠ ∅ for i ∈ I,
Ai ∩ Aj = ∅ when i ≠ j,
and
⋃ Ai = S.
i∈I

Question 7

Theorem 2 summarizes the connections we have established between equivalence
relations and partitions.

Answer 7

Let R be an equivalence relation on a set S. Then the equivalence classes of R form a partition
of S.
Conversely, given a partition {Ai ∣ i ∈ I} of the set S, there is an equivalence relation R
that has the sets Ai
, i ∈ I, as its equivalence classes.

proof of converse.

Question 8

Illustration of thm 2 by congrence classes modulo m:

Answer 8

There are m
different congruence classes modulo m, corresponding to the m different remainders possible
when an integer is divided by m. These m congruence classes are denoted by [0]m, [1]m, … ,
[m − 1]m. They form a partition of the set of integers.