Wstęp
Pierwsza rzecz jaką pewnie masz na myśli wchodząc tutaj: Czemu dwa tematy na raz? Otóż dlatego, że są w sumie jednym, o czym się zaraz przekonasz.
Dotychczas mówiąc, że elementy są sobie równe, przyjmowaliśmy to pojęcie tak na intuicję, bo nie da się jednoznacznie zdefiniować równości \(2\) elementów próbując zdefiniować podstawę, jaką jest zbiór, bo właśnie zbiór jest naszą bazą. Mając jednak aparat pojęciowy, który udało nam się dotychczas wypracować, możemy spróbować określić "równość" na podstawie jakichś wybranych przez nas kryteriów.
Do dzieła więc!
Rozwinięcie
Relacje równoważności
Zacznijmy więc od początku. Czym jest owa relacja równoważności? Otóż relacja równoważności jest to relacja "jednozbiorowa" tj. której dziedzina i przeciwdziedzina określona jest na tym samym zbiorze, oraz posiada trzy własności:
- jest zwrotna, czyli \(\text{dla każdego } a \in A \space aRa\)
- jest symetryczna, czyli \(\text{jeżeli istnieje } aRb \space \text{ to istnieje również } \space bRa, \text{gdzie } a \in A \text{ oraz } b \in A\)
- jest przechodnia, czyli \(\text{jeżeli istnieje } aRb \text{ oraz } bRc \text{ to istnieje } aRc, \text{gdzie } a \in A \text{, } b \in A \text{ oraz } c \in A\)
Tyle i aż zarazem, nie mniej w przyszłości okaże się, że całkiem sporo relacji, które będziemy roztrząsać, będzie relacją równoważności. Sztandarowym przykładem takiej relacji, jest relacja równości, czyli jeżeli wiążemy ze sobą elementy, które są sobie równe. Sprawdźmy dla przykładu:
- zwrotność:
- \(a\) w sposób oczywisty jest równe samemu sobie, tak samo jak każdy inny element
- symetria
- jeżeli \(a\) jest równe \(b\), to również w oczywisty sposób \(b\) jest równe \(a\)
- przechodniość
- jeżeli \(a\) jest równe \(b\), a \(b\) jest równe \(c\), to oczywiście, \(a\) jest równe \(c\)
Piękny dowód. Dla przećwiczenia tego zagadnienia zachęcam do odszukania i sprawdzenia również innych relacji, które posiadają owe własności.
No dobra. Mamy sobie relację równoważności, ale co ona tak na prawdę opisuje? Co ona znaczy?
Nie ma jednoznacznej, ścisłej definicji, czym tak na prawdę jest relacja równoważności, ponieważ jej definicją są właśnie jej własności, z których wynikają różne ciekawe właściwości. Można powiedzieć, ze względu na jej własności właśnie, że jest to tak trochę uogólnienie pojęcia równości. Dlaczego? Bo relacje równoważności zawsze będą odwzorowywać, w jakiś sposób, podobieństwo lub "równość" (specjalnie w cudzysłowie) właśnie. Stąd nazwa równoważność, ponieważ często używa się jej jako synonim do równości właśnie.
Innymi przykładami takiej relacji mogą być np:
- relacja posiadania urodzin w tym samym dniu: \(a R b\), czyli \(a\) ma urodziny w ten sam dzień co \(b\)
- relacja zaczynania się w tym samym punkcie wektorów: \(a R b\), czyli wektor \(a\) ma początek w tym samym punkcie co \(b\)
- relacja równości modulo: \(a R b\), czyli liczba \(a\) jest równa modulo (kongruentna) z liczbą \(b\)
- relacja równoległości prostych: \(a R b\), czyli prosta \(a\) jest równoległa z prostą \(b\)
I wiele wiele innych. Dla poćwiczenia polecam sobie wymyślić jeszcze z parę.
Ciekawą rzeczą jest fakt, że parę uporządkowaną zbioru, oraz relacji równoważności, która w nim występuje, np: \((A, R)\), nazywamy z angielskiego Setoid (polskiego odpowiednika nie znalazłem, ale można próbować zbioroid :D. Jeżeli takowy istnieje, proszę napisz do mnie czym prędzej). Ale na razie, czym dokładniej on jest i jakie ma własności, pozostanie tajemnicą.
Jedną z własności wynikających z właściwości relacji równoważności, jest fakt, że mając taką relację, możemy zbiór na którym owa relacja jest określona, podzielić na rozłączne podzbiory. Rozłączne, czyli takie, które nie mają wspólnych elementów, czyli że \(A \cap B = \emptyset\).
Dlaczego? Ponieważ definiując równość elementów, wedle tych własności (zwrotność, przechodniość, symetria), tworzymy jakby zbiory równych elementów, wedle jakiegoś kryterium. A skoro będą sobie równe, to nie będą równe innym elementom, stąd rozłączność.
Przykład.
Weźmy sobie relację posiadania urodzin w tym samym dniu, na zbiorze polskiej populacji. Wyznaczajmy kolejno zbiory osób, które mają urodziny od \(1\) stycznia, do \(31\) stycznia. Mamy więc \(31\) zbiorów, a w żadnym z nich, nie będzie osoby, która będzie miała urodziny z kimś z innego zbioru, czyli z innego dnia stycznia.
Klasa abstrakcji
Na początek, żeby nie brnąć w pojęcia, których nie mamy opisanych zacznijmy od zdefiniowania owego pojęcia od strony językowej. Czym jest klasa i czym jest abstrakcja? Opiszemy te pojęcia pobieżne, gdyż jest to temat na osobny artykuł, ale na tyle dokładnie, by wiedzieć, po co zostały użyte.
Klasa
Otóż klasa, jest to zbiór cech. Może być większy bądź mniejszy, nie mniej zbiór cech. Nic więcej.
Czym jest owa cecha? Dokładnie cechą. Taką samą jak w rozumieniu potocznym, czyli jakąś właściwością danego obiektu, np. długość włosów, wzrost, waga, materiał.
O ile klasa sama w sobie jest zbiorem, tak jej hierarchia, jest delikatnie inna niż w przypadku "normalnych" zbiorów. Pamiętamy, że podzbiór oznaczał zbiór, który zawiera się w nadzbiorze, i tak rysowaliśmy sobie tę hierarchię. Największy zbiór na samej górze, najmniejszy, na samym dole.
Problem z klasami, jest taki, że ich hierarchia występuje w odwrotnej kolejności. Można powiedzieć, że definiujemy je od dołu.
Klasa najwyżej w hierarchii będzie miała mniej cech, niż ta niżej. Niższa klasa, podklasa, będzie posiadała szerszą definicję niż nadklasa.
Przykładem takiej klasy może być najzwyklejsze w świecie zwierze. Jakie "obiekty" określamy zwierzętami? Konie, karpie, szczury, muchy itd. Różnią się one jednak od siebie, więc można je bardziej uporządkować, zbudować hierarchię.
Wszystkie te zwierzęta określimy jako zwierzęta, natomiast konie i szczury, określimy ssakami, karpia rybą, a muchę owadem.
Widzimy, że idąc od dołu, rozszerzamy zestaw cech jakimi chcemy określać te stworzonka. Wszystkie żyją (zgrubnie tak, dla przykładu), więc są zwierzętami. Konie i szczury są ssakami, więc ich wspólną cechą jest ssanie. A sam koń ma kopyta, których szczur nie ma.
Idąc w dół, więcej cech.
Powiemy więc że klasa jest pojęciem ogólnym, a poszczególne podklasy je uściślają.
Abstrakcja
Otóż abstrakcja, jest pojęciem, które definiuje jakoby podejście do zagadnienia. Dlaczego? Ponieważ abstrakcja jest to wyodrębnienie pewnych własności, które definiują jakiś zbiór obiektów, w taki sposób, żeby je uwydatnić. Mówiąc jeszcze inaczej, stworzenie sobie jakichś konstruktów, które będą zawierać tylko cechy, na których chcemy się skupić i na których chcemy operować.
Abstrakcją może być np. zbiór. Mając np. wór zboża, albo odział żołnierzy, abstrakcją, która może je obejmować jest właśnie zbiór. Pewien obiekt, mający cechy, które uwidaczniają się w tych obiektach, takie jak obecność elementów (ziaren, ludzi), lub liczność tych elementów.
Mówiąc ogólniej, mając w głowie przykład, budujemy sobie coś, tę właśnie abstrakcję, która będzie określała coś, co będziemy chcieli określać, definiować, operować na tym. Dlatego abstrakcję wyznacza się ponad czymś, np. abstrakcją ponad liczbami, jest zbiór elementów, a abstrakcją nad drogami krajowymi jest graf skierowany.
Jak już wspomnieliśmy, abstrakcję określa się zazwyczaj po to, żeby skupić się na cechach, które owa abstrakcja wynosi. Wróćmy do przykładu z drogami krajowymi.
Jeżeli chcemy znaleźć najkrótszą drogę od Radomia do Zamościa, nie potrzebujemy wiedzieć z czego drogi są, ile mają pasów, czy są kręte, jak szerokie są na określonych odcinkach. Potrzebujemy wiedzieć tylko gdzie się zaczynają, gdzie kończą, w którą stronę można na nich jechać i jakie są ich długości. Dokładnie takie własności ma graf skierowany, więc problem łatwiej jest rozwiązać operując na grafie, niż na szczegółowej mapie.
Klasa abstrakcji
Mając już zdefiniowane słowa, przejdźmy do pojęć. Na początek z buta trochę, zaczniemy od wzoru, by go później omówić. Klasą abstrakcji, lub klasą równoważności nazwiemy zbiór:
\([a]_R = \set{b \in A, \text{gdzie } aRb}\)
Czyli zbiór wszystkich elementów relacji równoważności \(b\), które, wchodzą w relację z jakimś wybranym przez nas elementem \(x\).
Pamiętamy, że relacja równoważności, oznacza w pewnym sensie, definicję równości. Skoro więc mamy jakoś tam zdefiniowaną tę równość (oczywiście cały czas w cudzysłowie), to możemy określić zbiory tych samych elementów. Mając takie zbiory, mamy wszystkie elementy, które są sobie równe.
Co z tego wynika?
Otóż klasa abstrakcji, jest to dokładnie ten zbiór.
Zbiór ten nazwany jest klasą abstrakcji, dlatego, że definiuje nam w pewien sposób właściwość zdefiniowaną poprzez te elementy. Definiuję nam klasę elementów w tym zbiorze. Pojedynczy zaś element, który będzie posiadał właściwość, którą owa klasa określa, nazwiemy reprezentantem.
Przykład:
Klasą abstrakcji w zbiorze Polaków, z relacji posiadania urodzin w tym samym dniu, będzie zbiór ludzi urodzonych \(1\) stycznia, a reprezentantem tej klasy, będzie Zygmunt I Stary.
Przestrzeń ilorazowa/Iloraz/Rozbicie zbioru/Podział
Jako że, jak już wcześniej wspomnieliśmy, mając relację równoważności, możemy określić rozłączne zbiory tych samych elementów, czyli klasy abstrakcji. Czyli wychodzi na to, że jedna relacja równoważności, powoduje podział zbioru, na którym tę relację określamy, na wiele owych klas. Zbiór tych klas, które wydzieliliśmy relacją równoważności, nazywamy ilorazem lub przestrzenią ilorazową zbioru przez relację, lub rozbiciem zbioru, lub podziałem. Np. mając zbiór \(A\) i relację równoważności \(R\), możemy wyznaczyć przestrzeń ilorazową lub iloraz \(I\) i oznaczyć to tak:
\(I = A/R\)
Odwzorowanie ilorazowe
Jako że umiemy już rozbijać zbiór w przestrzeń ilorazową, nasuwa się pytanie, czy da się każdemu elementowi, który zawiera się w każdej z klas przypisać jego klasę? No jasne że tak. Takie właśnie przypisanie, nazywamy odwzorowaniem ilorazowym.
Odwzorowanie ilorazowe, jest to nic innego, jak funkcja. Surjekcja dodatkowo, jako że każdy element będzie miał swoją klasę abstrakcji. Dziedziną tej funkcji będzie, a jakże, zbiór elementów, który rozbijamy, a przeciwdziedziną, klasy abstrakcji. Jako, że dziedziną jest cały zbiór, powiedzmy \(A\), który rozbijamy relacją, powiedzmy \(R\), będzie to odwzorowanie. Możemy więc użyć wygodnego oznaczenia:
\(A \rightarrow A/R\)
Można się spotkać czasami z pojęciem rzutowania, ale nie robiliśmy jeszcze rzutów (które swoją drogą są właśnie odwzorowaniami), więc tylko nazwiemy ten proces. A więc spotkać się można jeszcze z pojęciem rzutowania naturalnego, bądź kanonicznego, a oznaczać ono będzie dokładnie to samo, czyli odwzorowanie ilorazowe.
Niezależność
Relacja równoważności, to relacja, będzie definiowała jakąś relację "równości", jak w przykładzie z urodzinami. Relacja ta odwzorowuje nam równoważność, na podstawie jakiejś właściwości, cechy, w tym przypadku jednej, daty urodzin. Nic nie stoi jednak na przeszkodzie, żeby tych cech było wiele, w ogólności \(n\).
Skoro już wiemy, że budując relację równoważności bazujemy na cechach, to jeżeli uda nam się wyznaczyć taką cechę, która stworzy relację równoważności, powiemy że znaleźliśmy cechę lub własność dobrze określoną. Nazywamy ją także niezależną, a to dlatego, że niezależnie, które elementy ze zbioru na którym ową relację określiliśmy, będą ze sobą w relacji, będą posiadały ową właściwość właśnie. Powiemy wtedy że właściwość ta jest niezależna od wyboru reprezentanta.
Zakończenie
Wiemy już jak zdefiniować równoważność, wiemy czym są klasy abstrakcji i relacje równoważności. Wiemy czym są cechy i właściwości i jak na ich podstawie rozbijać zbiory i tworzyć z nich zbiory elementów podobnych.
Powoli zaczynamy rozumieć matematykę i jej podstawowe właściwości. To cieszy.
Tymczasem dziękuję za uwagę i do zobaczenia w następnym artykule :)
Na samym początku przy definicji własności przechodniości, na końcu powinno być "a równe c" a jest drugi raz napisane "a równe b".
Poprawione! Dziękuję za zwrócenie uwagi!
Świetnie wytłumaczone, bardzo należycie i w dobrym przystępnym dla człowieka języku.Dziękuję
Ja dziękuję, za obecność tu i ciepłe słowo :)