Zasada abstrakcji, zasada identyfikacji elementów równoważnych – twierdzenie matematyczne mówiące, że dowolnemu rozbiciu zbioru odpowiada pewna relacja równoważności, a każda relacja równoważności ustanawia pewne rozbicie zbioru.

Twierdzenie Jeśli jest niepustym zbiorem i jest relacją równoważności w tym zbiorze, to rodzina podzbiorów określona następująco

jest rozbiciem zbioru , czyli ustala podział zbioru na niepuste i rozłączne podzbiory.

Zbiory należące do rodziny nazywane są klasami abstrakcji relacji .

Dowód Ponieważ relacja równoważności jest zwrotna, dla każdego zachodzi Stąd każdy element zbioru należy do pewnego zbioru z rodziny i żaden z tych zbiorów nie jest pusty. Ponadto, jeśli pewne dwa zbiory i nie są rozłączne, to istnieje które spełnia Wtedy z przechodniości relacji wynika, że czyli dla każdego takiego, że zachodzi również (z przechodniości). Wobec tego Analogicznie można wykazać, że zatem

Twierdzenie odwrotne Jeśli jest zbiorem niepustym i jest jego rozbiciem, to relacja określona w zbiorze wzorem

jest relacją równoważności.

Dowód Jeśli to ponieważ to dla pewnego a stąd wynika, że

Jeśli to Wynika to z oczywistej implikacji:

Niech Istnieją dla których Jednak w tym wypadku ponieważ skąd a więc .

Zastosowania mały|350px|Pary uporządkowane liczb naturalnych w kartezjańskim układzie współrzędnych. Odpowiednia relacja równoważności między takimi parami pozwala ściśle zdefiniować liczby całkowite, za pomocą konstrukcji. Pary w tej relacji zaznaczono jednakowym kolorem

Z zasady abstrakcji często korzysta się w matematyce wtedy, gdy występuje potrzeba zdefiniowania nowych typów obiektów.

Konstrukcja liczb całkowitych W zbiorze można wprowadzić taką relację równoważności że

Łatwo sprawdzić, że tak zdefiniowana relacja jest zwrotna i symetryczna. Ponadto jest ona przechodnia, ponieważ z równości

wynika co daje czyli

Na mocy zasady abstrakcji relacja dzieli zbiór na niepuste i rozłączne zbiory nazywane klasami abstrakcji. Zbiór liczb całkowitych można zdefiniować jako zbiór tych właśnie klas abstrakcji. Klasa abstrakcji, do której należą , , etc. wyznacza liczbę całkowitą Klasy, do których należą pary dla i wyznaczają liczby ujemne

Na tak określonych klasach abstrakcji określa się działania

i dowodzi się, że ich wyniki nie zależą od wyboru reprezentantów klas abstrakcji oraz, że tak określone działania mają odpowiednie własności.

Przypisy

Bibliografia

Kategoria:Relacje równoważności