3. Relacje równoważności i klasy abstrakcji

(Paulina Miksa)

Definicja 3:
Niech dane będą zbiory X i Y. Relacją (dwuargumentową) między elementami zbiorów X i Y nazywamy dowolny podzbiór ρ ∈ X × Y. Jeśli X = Y to mówimy, że ρ jest relacją na zbiorze X. (x,y) ∈  ρ będziemy dla uproszczenia zapisywać xρy.

Przykłady relacji:

1. Relacja mniejszości na ℝ:

xρy ⇔ x < y

Definicja 4 (rodzaje relacji):
Niech ρ będzie relacją na zbiorze X≠. Mówimy, że:
- ρ jest zwrotna, gdy ∀_xϵX x ρ x

- ρ jest symetryczna, gdy ∀_x, yϵX x ρ y = > y ρ x 
- ρ jest przechodnia, gdy ∀_{x, y, zϵX} (x ρ y  ∧  y ρ z)= >  x ρ z

Relację ρ określoną na zbiorze X, która jest zwrotna, symetryczna i przechodnia nazywamy relacją równoważności.

Przykład relacji równoważności:
a) Niech ρ będzie relacją na ℤ daną wzorem x ρ y  ⇔ 3|(x − y) dla x, y∈ℤ.

Definicja 5: Niech ρ będzie relacją równoważności określoną na zbiorze X. Klasą abstrakcji (klasą równoważności) elementu xieX względem relacji ρ nazywamy zbiór [x]_ρ = {yϵX,  y ρ x}, czyli zbiór wszystkich elementów zbioru X równoważnych z x..

Klasy są albo identycznościowe, albo rozłączne.

Definicja 6: Rodzinę klas abstrakcji danej relacji równoważności na zbiorze X nazywamy zbiorem ilorazowym i oznaczamy X/ρ = {[x]_ρ,  xϵρ}.

Zasada abstrakcji: Jeśli ρ jest relacją równoważności na zbiorze X to rodzina wszystkich klas abstrakcji relacji ρ jest podziałem zbioru X.

Definicja 8: Rodzinę klas abstrakcji danej relacji równoważności na zbiorze X nazywamy zbiorem ilorazowym i oznaczamy X|ρ.

Przykłady zastosowań klas abstrakcji:

• Konstruowanie liczb wymiernych ((p₁,q₁)ρ(p₂,q₂) ⇔ p₁q₂ = p₂q₁)