Mathematics - Discrete Mathematics - Equivalence Relations

Introduction

Hey it's a me again @drifter1!

Today we continue with Mathematics, and more specifically the branch of "Discrete Mathematics", in order to get into Equivalence Relations.

So, without further ado, let's get straight into it!

Equivalence Relations

A relation R on set A is an equivalence relation if it satisfies all three of the following properties:

Reflexive : (x, x) ∈ R for every x ∈ A
Symmetric : (x, y) ∈ R ⟺ (y, x) ∈ R for every x ∈ A, y ∈ A
Transitive : (x, y) ∈ R and (y, z) ∈ R ⟺ (x, z) ∈ R

Operations and Properties

If R and S are two equivalence relations then:

Their intersection R ∩ S is for sure also an equivalence relation.
Their union R ∪ S might be an equivalence relation as well, but it's not certain because the transitive property may not be satisfied by their union.
The inverse relation R^-1 is also an equivalence relation. Additionally, the Domain and Range of R^-1 are equal to the Range and Domain of R, respectively.

Equivalent Elements

Such relations are very useful in both mathematics and informatics. The reason being that two elements that are related by an equivalence relation can be considered equivalent to each other. For two elements a and b, the commonly used notation for equivalence is a ~ b.

Equivalence Classes

For a given set A and equivalence relation R on A, the elements of A can be sorted into Equivalence Classes. For each element a ∈ A, the equivalence class of a is denoted by [a]. This subset of A consists of all elements of A that are equivalent to a.

Sometimes the corresponding equivalence relation is also added to the equivalence class notation, resulting in [a]_R.

Any member of the equivalence class can be used for denoting it. So, if b ~ a, then [b] would be the same class as [a].

Any two equivalent classes are thus basically either equal or disjoint.

Partitions

Any set A can be broken down into a collection of disjoint subsets C via a equivalence relation R. This collection is pair-wise disjoint and produces a so called partition of A, so that:

Congruence Classes and Relations

Congruent Classes and modular arithmetic will be covered more thoroughly in the dedicated series on Number Theory!

Let's quickly get through the basics...

Congruence classes are basically equivalence classes on a specific structure. An example of a congruence relation is the modulo n operation (mod n). Congruence is commonly denoted via the ≡ symbol.

In the case of the set of integers Z, if a, b are two integers, then a, b are congruent module n, if there exists an integer k so that a - b = kn, or a ≡ b mod n. Both numbers basically have the same remainder r with n when applying Euclidean division. The integers a and b are thus basically members of the same congruence class [r], which of course can be denoted by [a] or [b] as well.

This concept is widely used in Computer Science. For example, in the case of hash tables, which are a data structure that uses a modulo function for the purpose of sorting data.

RESOURCES:

References

Images

Mathematical equations used in this article, have been generated using quicklatex.

Block diagrams and other visualizations were made using draw.io.

Previous articles of the series

Introduction → Discrete Mathematics, Why Discrete Math, Series Outline
Sets → Set Theory, Sets (Representation, Common Notations, Cardinality, Types)
Set Operations → Venn Diagrams, Set Operations, Properties and Laws
Sets and Relations → Cartesian Product of Sets, Relation and Function Terminology (Domain, Co-Domain and Range, Types and Properties)
Relation Closures → Relation Closures (Reflexive, Symmetric, Transitive), Full-On Example