Na tym wykładzie zdefiniujemy pewien szczególny typ relacji – relację równoważności, podamy przykłady i własności tych relacji. Pojawi się pojęcie klasy abstrakcji i zbioru ilorazowego. Warto przypomnieć sobie własności relacji, zwłaszcza Definicje 62, 66, 72.
\(\bullet \) Niech \(X=\mathbb {N}\cup \{0\}\). Zadajmy relację \(\relR \) warunkiem \(x\relR y\iff 2|(x+y)\). Faktycznie, jest to relacja równoważności: jest zwrotna bo \(2|2x\), symetryczna bo \(2|(x+y)\Longrightarrow 2|(y+x)\), oraz przechodnia – bo jeśli \(2|(x+y)\wedge 2|(y+z) \) to \(x+y=2s\), \(y+z=2t\) dla pewnych \(s,t \) naturalnych, zatem \(x+2y+z=2(s+t)\), czyli \(x+z=2(s+t-y)\), zatem \(2|(x+z)\).
\(\bullet \) Relacja równoległości w zbiorze prostych na płaszczyźnie jest relacją równoważności (ćwiczenie).
\(\bullet \) Relacja podobieństwa w zbiorze trójkątów na płaszczyźnie też jest relacją równoważności (ćwiczenie).
\(\bullet \) Relacja podzielności w zbiorze \(\mathbb {N}\) nie jest relacją równoważności (bo nie jest symetryczna).
Uwaga 116. Zauważmy, że klasa abstrakcji elementu \(x\in X\) jest zawsze zbiorem niepustym. Ponieważ relacja równoważności jest zwrotna, to zawsze \(x\relR x\), a zatem \(x\in [x]_R\).
Rozważmy teraz relacje równoważności z Przykładu 114.
\(\bullet \) Pierwsza relacja ma dwie klasy abstrakcji – jedną są wszystkie liczby parzyste, a drugą wszystkie nieparzyste (bo dwie liczby są ze sobą w relacji gdy mają tę samą resztę z dzielenia przez dwa).
\(\bullet \) W relacji równoległości w zbiorze prostych na płaszczyźnie klasą abstrakcji danej prostej są wszystkie proste równoległe do danej prostej.
\(\bullet \) Klasą abstrakcji danego trójkąta w relacji podobieństwa w zbiorze trójkątów na płaszczyźnie jest zbiór wszystkich trójkątów podobnych do danego.
Zdefiniujemy teraz pojęcie podziału zbioru.
\(\bullet \) Mówimy, że rodzina zbiorów \(\{A_j\}_{j\in J}\) pokrywa zbiór \(X\) jeśli \(X=\bigcup _{j\in J}A_j\). Mówimy też, że rodzina \(\{A_j\}_{j\in J}\) jest pokryciem zbioru \(X\).
\(\bullet \) Rodzina zbiorów \(\{A_j\}_{j\in J}\) nazywa się podziałem zbioru \(X\) jeśli
(a) Rodzina \(\{A_j\}_{j\in J}\) jest pokryciem \(X\),
(b) Zbiory \(A_j\) są parami rozłączne: \(A_i\cap A_j=\emptyset \), \(\forall _{i,j\in J} : i\neq j\),
(c) Zbiory \(A_j\) są niepuste: \(A_j\neq \emptyset \ \forall j\in J.\)
Uwaga 119. Nietrudno sprawdzić że klasy abstrakcji z Przykładu 117 tworzą podział zbioru, na którym dana relacja jest określona. Nie jest to przypadek, jak zobaczymy w poniższym twierdzeniu.
Dowód.
1. Zauważmy, że dla dowolnego \(x\in X\) zachodzi (ze zwrotności relacji \(R\)) \(x\in [x]_R\). Wynika stąd, że wszystkie klasy abstrakcji są zbiorami niepustymi, zatem warunek (c) definicji podziału jest spełniony.
2. Ponieważ \(x\in [x]_R\), to \(\{x\}\subset [x]_R\), a zatem, skoro mamy \(\bigcup _{x\in X}[x]_R\subset X\) (bo klasy abstrakcji są wszystkie podzbiorami \(X\)) oraz mamy \(X=\bigcup _{x\in X}\{x\}\subset \bigcup _{x\in X}[x]_R\), a więc \(\{[x]_R\}_{x\in X}\) jest pokryciem \(X\), warunek (a) jest zatem spełniony.
3. Pozostaje sprawdzić warunek (b). Wykażemy najpierw lemat.
Dowód Lematu 121. (\(\Longrightarrow \)): \([x_1]_R=[x_2]_R\Longrightarrow x_1\in [x_2]_R\Longrightarrow x_1R x_2\).
(\(\Longleftarrow \)): Przypuśćmy, że \([x_1]_R\neq [x_2]_R\). Zatem, możemy bez zmniejszenia ogólności, przypuścić, że istnieje \(y\in [x_1]_R\), takie, że \(y\notin [x_2]_R\). Skoro \(y\in
[x_1]_R\), to \(y\relR x_1\). Zarazem, z założenia, \(x_1\relR x_2\). Z przechodniości relacji \(R\) mamy, że \(y\relR x_2\), czyli \(y\in [x_2]_R\), sprzeczność. □
Kolejny fakt również sformułujemy jako lemat.
Ostatni lemat pokazuje, że warunek (b) z Definicji 118 jest spełniony (dwie różne klasy abstrakcji są rozłączne), a zatem klasy abstrakcji dają podział zbioru \(X\). □
Wykażemy teraz stwierdzenie w pewnym sensie odwrotne do Twierdzenia 120, mianowicie mówiące, że jeśli mamy dany podział zbioru, to istnieje relacja równoważności, której klasy abstrakcji są dokładnie zbiorami z tego podziału.
Dowód. Zdefiniujmy relację \(R_A\) w taki sposób:
\[\forall x_1,x_2\in X, x_1\relRA x_2\iff \exists j\in J: x_1\in A_j\wedge x_2\in A_j.\]
Aby zakończyć dowód wystarczy sprawdzić, że \(R_A\) jest relacją równoważności (wtedy zbiory \(A_j\) są jej klasami abstrakcji).
Relacja \(R_A\) jest zwrotna, bo dla dowolnego \(x\in X\), skoro \(X=\bigcup _{j\in J}A_j\), mamy istnienie \(j_0\) takiego, że \(x\in A_{j_0}\), a zatem \(x\relRA x\).
Relacja \(R_A\) jest oczywiście symetryczna, bo \(x\relRA y\iff \exists _{j\in J} : x, y\in A_j \iff \exists _{j\in J} : y, x\in A_j\iff y\relRA x\).
Sprawdzimy teraz przechodniość relacji \(R_A\). Niech \(x\relRA y\) i \(y\relRA z\), dla pewnych \(x,y,z\in X\). Z definicji \(R_A\) mamy istnienie \(j_1\) takiego, że \(x,y\in A_{j_1}\) i istnienie \(j_2\) takiego, że \(y, z\in A_{j_2}\). Zatem \(y\in A_{j_1}\cap A_{j_2}\), ale dla \(j_1\neq j_2\) z definicji podziału mamy \(A_{j_1}\cap A_{j_2}=\emptyset \), zatem musi być \(j_1=j_2\). Stąd, \(x,y,z\in A_{j_1}\), a zatem \(x\relRA z\). □
Zdefiniujemy teraz pojęcie zbioru ilorazowego.
Niech \(X\) będzie zbiorem niepustym a \(R\) relacją równoważności na tym zbiorze.
Definicja 124. Zbiorem ilorazowym relacji \(R\) (albo ilorazem zbioru \(X\) przez relację \(R\)) nazywamy zbiór wszystkich klas abstrakcji tej relacji.
\[X/R=\{ [x]_R: x\in X \}.\]
\(\bullet \) Niech \(X=\mathbb {N}\times \mathbb {N}\). Zdefiniujmy relację \(R\) następująco. Dla dowolnych \((m_1,n_1), (m_2,n_2)\in X\)
\[(m_1,n_1)\relR (m_2,n_2)\iff m_1+n_2=m_2+n_1.\]
Jako ćwiczenie zostawiamy sprawdzenie, że \(R\) jest faktycznie relacją równoważności, a zbiór klas abstrakcji tej relacji można utożsamiać ze zbiorem liczb całkowitych (Wskazówka: \(z~= m_1-n_1\)).
\(\bullet \) Niech \(X=\mathbb {Z}\times \mathbb {N^*}\). Zdefiniujmy relację \(R\) następująco. Dla dowolnych \((m_1,n_1), (m_2,n_2)\in X\)
\[(m_1,n_1)\relR (m_2,n_2)\iff m_1\cdot n_2=m_2\cdot n_1.\]
Jako ćwiczenie zostawiamy tu też sprawdzenie, że \(R\) jest faktycznie relacją równoważności, a zbiór klas abstrakcji tej relacji można utożsamiać ze zbiorem liczb wymiernych (Wskazówka: \(q=~\frac {m_1}{n_1}\)).
Na zakończenie tego wykładu powiemy kilka słów o zgodności funkcji z relacją równoważności.
Definicja 126.
\(\bullet \) Jeśli mamy relację równoważności \(\relR \) na zbiorze \(X\) i funkcję \(f:X\to X\), to mówimy, że ta funkcja \(f\) jest zgodna z relacją \(\relR \) jeśli dla dowolnych \(x, y\in X\) zachodzi \(x\relR y\Longrightarrow f(x)\relR f(y)\).
\(\bullet \) Podobnie, jeśli mamy relację równoważności \(\relR \) na zbiorze \(X\) i funkcję \(f:X\times X\to X\), to mówimy, że ta funkcja \(f\) jest zgodna z relacją \(\relR \) jeśli dla dowolnych \(x, y, x_1,y_1\in X\) zachodzi \(x\relR x_1\wedge y\relR y_1 \Longrightarrow f(x,y)\relR f(x_1,y_1)\).
Przykład 127. (Dodawanie liczb całkowitych). Niech \([(m,n)]_R\) będzie klasą abstrakcji w relacji \(R\) zdefiniowanej w pierwszym punkcie Przykładu 125, zatem liczbą całkowitą. Zdefiniujmy funkcję dodawania \(f: X\times X\to X\) następująco: \(f((m,n),(a,b))=(m+a,n+b).\) Sprawdzimy, że tak zdefiniowane dodawanie jest zgodne z relacją \(\relR \). Jeśli \((m,n)\relR (m_1,n_1)\) to z definicji \(\relR \) mamy \(m+n_1=n+m_1\), tak samo \((a,b)\relR (a_1,b_1)\) gdy \(a+b_1=a_1+b\). Zatem: \(m+n_1+a+b_1=n+m_1+a_1+b\) czyli w relacji są pary \((m+a,n+b), (m_1+a_1,n_1+b_1)\), czyli tak określone dodawanie jest zgodne z relacją definiującą liczby całkowite.