Następujące twierdzenie zwane "zasadą abstrakcji" lub "zasadą identyfikacji elementów równoważnych" ustala związek pomiędzy pojęciem podziału a relacją równoważności.

Niech [X] oznacza zbiór wszystkich klas abstrakcji relacji ∼ w zbiorze X, tzn.[X] = { [x] : x ∈ X}. Zbiór [X] jest podziałem zbioru X w sensie definicji 5.3.1 jak głosi zasada abstrakcji, bo

1. na mocy lematu 5.2.1 klasy abstrakcji należące do [X] są rozłączne,
2. wszystkie zbiory należące do [X] są niepuste, bo dla każdego y ∈ X, y ∈ [y],
3. suma wszystkich zbiorów rodziny [X] (tzn. suma wszystkich klas abstrakcji) daje cały zbiór X, bo każdy element zbioru X należy do jakiejś klasy abstrakcji (np. do tej, którą sam reprezentuje).

Jeśli dany jest podział (X_i)_{i ∈I} niepustego zbioru X , to przyjmując

x ∼ y wttw istnieje takie k ∈ I, że x ∈ X_k oraz y ∈ X_k

definiujemy pewną relację równoważności.

Własność zwrotności relacji ∼ wynika z faktu, że każdy element zbioru X należy do jakiegoś zbioru podziału (X_i)_{i ∈I}. Własność symetrii jest oczywista z samej definicji relacji ∼. Własność przechodniości wynika z faktu, że zbiory podziału są rozłączne. Gdyby więc x,y ∈ X_n, a y, z ∈ X_m, to musiałoby być n=m, czyli x i z muszą należeć do tego samego zbioru podziału.

Pytanie 5.4.1: Czy można zdefiniować tak relację równoważności w niepustym zbiorze X, by jedna z jej klas była pusta?

Przykład 5.4.1

1. Relacja równoważności określona w N wzorem
   x ∼ y wttw x mod 3 = y mod 3,
   wyznacza podział zbioru N na trzy klasy abstrakcji [0], [1], [2] takie, że [0] = {3k: k ∈ N}, [1] = {3k+1: k ∈ N}, [2] = {3k+2: k ∈ N}. Oczywiście każda liczba naturalna należy do jednej i tylko jednej z tych klas.
2. Niech ≈ oznacza relację binarną w rodzinie podzbiorów danego zbioru X określoną dla dowolnych zbiorów A, B ∈ P(X) następująco:
   A ≈ B wttw istnieje wzajemnie jednoznaczna funkcja (bijekcja) odwzorowująca A na B.
   Taka relacja jest relacją równoważności (por. lemat 4.3.2). Jeśli A jest zbiorem n elementowym, to [A] = {B ∈ P(X): zbiór B ma n elementów}. Relację ≈ nazywamy relacją równoliczności, a zbiory, które są ze sobą w tej relacji, nazywamy równolicznymi. O zbiorach równolicznych będziemy mówili dokładniej w wykładzie dziesiątym.

Pytanie 5.4.2: Rozważmy relację równoliczności ≈ w zbiorze wszystkich podzbiorów zbioru liczb naturalnych (określoną w przykładzie 5.4.1) i klasy abstrakcji tej relacji. Które z podanych zdań są prawdziwe?

(a) N ∈ [P]

(b) P ∈ [N]

(c) {2} ∈ [P]

(d) {1,2,3,4,5,6} ≈ {1,3,5,7,11,13}

Zadanie 5.4.1

Niech m będzie ustaloną liczbą naturalną różną od zera. Udowodnić, że relacja r określona dla dowolnych x, y ∈ N:

x r y wttw liczba całkowita (x-y) jest podzielna przez m,

jest relacją równoważności i wskazać jej klasy abstrakcji.

Rozwiązanie: Ponieważ 0 ( = x-x) jest podzielne przez każdą liczbę naturalną >0, więc relacja jest zwrotna. Relacja jest symetryczna, bo jeśli x-y = km, to y-x = (-k)m. Relacja r jest przechodnia, bo gdy (x-y) jest podzielne przez m i (y-z) jest podzielne przez m, to dla pewnych k i k' całkowitych mamy : x-y = km oraz y-z = k'm. Jeśli dodamy stronami te równości, to otrzymamy x-z = (k+k')m, czyli x-z jest też podzielne przez m. Relacja ta ma m klas abstrakcji postaci [i]={km+i: k ∈N} dla i=0,1,...,m-1.