Skip to content

Equivalent Relations ​

Def

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

  • 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.

Equivalence Classes ​

Let R be an equivalence relation on a set A.

INFO

The equivalence class of an element a∈A is the set of all elements in A that are related to a.

The equivalence class of a is denoted by:

[a]R

If only one equivalence relation is being discussed, we usually write:

[a]

instead of [a]R.

Definition ​

The equivalence class of a is:

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

or equivalently:

[a]R={s∈A∣aRs}

Representative ​

If:

b∈[a]R

then b is called a representative of the equivalence class.

TIP

Any element in the class can serve as a representative.

TIP

There is nothing special about the chosen representative.

Equivalence Classes and Partitions ​

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]≠∅

INFO

(i)≡(ii)≡(iii)

Partitions ​

Let R be an equivalence relation on a set A. The union of equivalence classes of R is all of A.

⋃a∈A[a]R=A

In other words, A partition of a set S is a collection of subsets:

Ai,i∈I

such that:

Nonempty

Each subset is nonempty:

Ai≠∅

for all i∈I.

Pairwise Disjoint

Different subsets do not overlap:

Ai∩Aj=∅

whenever i≠j.

Cover the Entire Set

The union of all subsets equals the whole set:

⋃i∈IAi=S

image.png

Equivalence Partitions and Relations ​

Theorem 2

  • 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.

Intuition ​

Built with ❤️ and curiosity