Relation set

Equivalence relation

An equivalence relation is any relation ∼ with the properties of

1. reflexivity (∀𝑎 ∈𝑆)[𝑎 ∼𝑎]
2. symmetry (∀𝑎 ∈𝑆)(∀𝑏 ∈𝑆)[𝑎 ∼𝑏 ⟹ 𝑏 ∼𝑎]
3. transitivity (∀𝑎 ∈𝑆)(∀𝑏 ∈𝑆)(∀𝑐 ∈𝑆)[𝑎 ∼𝑏 ⟹ 𝑏 ∼𝑐 ⟹ 𝑎 ∼𝑐]

Quintessential examples include = and isomorphic objects. A structure-preserving equivalence relation is called a Congruence relation, which precedes the notion of an Algebraic quotient.

Equivalence relations may be induced by a function: Given 𝑓 :𝐴 →𝐵, then 𝑎1 ∼𝐴𝑎2 ⟺ 𝑓(𝑎1) ∼𝐵𝑓(𝑎2) defines an equivalence relation ∼𝐴 on the set 𝐴 for any equivalence relation ∼𝐵 on the set 𝐵.

Equivalence class

Every equivalence relation has a corresponding Partition of equivalence classes and vice versa.¹ An equivalence class for 𝑎 under 𝑅 is defined as

And has the following properties

• 𝑎 ∈[𝑎]𝑅
• for any 𝑥,𝑦 ∈[𝑎]𝑅, (𝑥,𝑦) ∈𝑅
• 𝑏 ∈[𝑎]𝑅 if and only if [𝑎]𝑅 =[𝑏]𝑅
• 𝑏 ∉[𝑎]𝑅 if and only if [𝑎]𝑅 ∩[𝑏]𝑅 =∅

The set of equivalence classes is called the Algebraic quotient.

Natural projection

Equivalence relations on a set 𝑋 are also characterised precisely by surjective functions called the natural projection 𝜋 :𝑋 ↠𝑆 whose fibres are equivalence classes. Then we say 𝑆 ≅𝑋/ ∼ =𝑋/𝜋, with the natural isomorphism 𝜑 :𝑆 →𝑋/ ∼ :𝑠 →𝜋−1{𝑠}. If 𝜋 is a homomorphism then the induced equivalence relation is a congruence relation.

#state/tidy | #SemBr | #lang/en