Question

state and prove fundamental theorem on equivalence relation​

Answer 1

Answer:

In mathematics, an equivalence relation is a binary relation that is reflexive, symmetric and transitive. The relation "is equal to" is the canonical example of an equivalence relation, where for any objects a, b, and c:

a = a (reflexive property),

if a = b then b = a (symmetric property), and

if a = b and b = c then a = c (transitive property).

As a consequence of the reflexive, symmetric, and transitive properties, any equivalence relation provides a partition of the underlying set into disjoint equivalence classes. Two elements of the given set are equivalent to each other if and only if they belong to the same equivalence class.

Simple example

Let the set {\displaystyle \{a,b,c\}} \{a,b,c\} have the equivalence relation {\displaystyle \{(a,a),(b,b),(c,c),(b,c),(c,b)\}} \{(a,a),(b,b),(c,c),(b,c),(c,b)\}. The following sets are equivalence classes of this relation:

{\displaystyle [a]=\{a\},~~~~[b]=[c]=\{b,c\}} [a]=\{a\},~~~~[b]=[c]=\{b,c\}.

The set of all equivalence classes for this relation is {\displaystyle \{\{a\},\{b,c\}\}} \{\{a\},\{b,c\}\}. This set is a partition of the set {\displaystyle \{a,b,c\}} \{a,b,c\}.

Equivalence relations

The following are all equivalence relations:

"Is equal to" on the set of numbers. For example, {\displaystyle {\tfrac {1}{2}}} {\tfrac {1}{2}} is equal to {\displaystyle {\tfrac {4}{8}}} {\displaystyle {\tfrac {4}{8}}}.

"Has the same birthday as" on the set of all people.

"Is similar to" on the set of all triangles.

"Is congruent to" on the set of all triangles.

"Is congruent to, modulo n" on the integers.

"Has the same image under a function" on the elements of the domain of the function.

"Has the same absolute value" on the set of real numbers

"Has the same cosine" on the set of all angles.

Answer 2

According to the fundamental theorem, any equivalence relation on a set creates a partition of the set, specifically a partition into its equivalence classes. Every partition of a set, on the other hand, establishes an equivalence relation on that set. It is the relationship in which two components are included if they are in the same division element.

For example, the relation on the set of automobiles in which two vehicles are in the connection if and only if they are of the same color yields a partition of the set of cars into equivalence classes associated with each color of cars.

Proof:

Let ∼ represent an equivalence relation on set X.  That is, the relationship is reflexive, symmetrical, and transitive.

If we define for every an∈X the set:  [a]:={x∈X∣a∼x}

then the reflexivity of ∼ tells us immediately that a∈[a].

Transitivity states that:

c∈[a] and x∈[c]⟹x∈[a]

or equivalently:

c∈[a]⟹[c]⊆[a](1)

By symmetry we find:

c∈[a]⟺a∼c ⟺ c∼a⟺∈[c]

This indicates that (1) can be substituted by the more powerful statement:

c∈[a]⟺[c]=[a](2)

So if [a] and [b] share an element c in common then (2) tells us right away that [a]=[c]=[b].  

This demonstrates that for sets [a] and [b] there are only two options: they are disjoint or they coincide.  The sets of form [a] are by definition the equivalence classes induced by ∼.  If A⊆X is such an equivalence class then A=[a] for every ∈A and an element of A is a so-called representative of the class.  

These sets, as seen above, create a partition of X.

Hence proved.