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.