Ekvivalence a rozklady Jan Paseka Masarykova univerzita Brno Ekvivalence a rozklady ­ p.1/33 Abstrakt Ekvivalence a rozklady ­ p.2/33 Abstrakt V této kapitole připomeneme pojem (binární) relace a některé speciální relace (reflexivní, tranzitivní, symetrická, antisymetrická, ekvivalence). Ekvivalence a rozklady ­ p.2/33 Abstrakt V této kapitole připomeneme pojem (binární) relace a některé speciální relace (reflexivní, tranzitivní, symetrická, antisymetrická, ekvivalence). Pokračujeme pak pojmem jádra zobrazení jakožto relace na množině. Ekvivalence a rozklady ­ p.2/33 Abstrakt V této kapitole připomeneme pojem (binární) relace a některé speciální relace (reflexivní, tranzitivní, symetrická, antisymetrická, ekvivalence). Pokračujeme pak pojmem jádra zobrazení jakožto relace na množině. Stěžejním pojmem je pojem rozkladu množiny, který koresponduje relaci ekvivalence na množině. Ekvivalence a rozklady ­ p.2/33 Abstrakt V této kapitole připomeneme pojem (binární) relace a některé speciální relace (reflexivní, tranzitivní, symetrická, antisymetrická, ekvivalence). Pokračujeme pak pojmem jádra zobrazení jakožto relace na množině. Stěžejním pojmem je pojem rozkladu množiny, který koresponduje relaci ekvivalence na množině. Aplikací výše uvedených pojmů zkonstruujeme množinu racionálních čísel. Ekvivalence a rozklady ­ p.2/33 Obsah přednášky Ú vod Reflexivní, tranzitivní, symetrická a antisymetrická relace. Relace ekvivalence. Ekvivalence a rozklady ­ p.3/33 Obsah přednášky Ú vod Reflexivní, tranzitivní, symetrická a antisymetrická relace. Relace ekvivalence. Jádro zobrazení Rozklad množiny. Ekvivalence a rozklady ­ p.3/33 Obsah přednášky Ú vod Reflexivní, tranzitivní, symetrická a antisymetrická relace. Relace ekvivalence. Jádro zobrazení Rozklad množiny. Konstrukce racionálních čísel. Ekvivalence a rozklady ­ p.3/33 Opakování - relace Necht' A je množina a necht' n 1 je přirozené číslo. Pak libovolnou podmnožinu kartézské mocniny An nazýváme n-ární relací na množině A. Ekvivalence a rozklady ­ p.4/33 Opakování - relace Necht' A je množina a necht' n 1 je přirozené číslo. Pak libovolnou podmnožinu kartézské mocniny An nazýváme n-ární relací na množině A. Je-li n = 1, pak je podmnožinou množiny A = A1 a říkáme též, že je unární relace na A. Ekvivalence a rozklady ­ p.4/33 Opakování - relace Necht' A je množina a necht' n 1 je přirozené číslo. Pak libovolnou podmnožinu kartézské mocniny An nazýváme n-ární relací na množině A. Je-li n = 1, pak je podmnožinou množiny A = A1 a říkáme též, že je unární relace na A. Je-li n = 2, tedy je-li A2 , říkáme, že je binární relace na A. Ekvivalence a rozklady ­ p.4/33 Opakování - relace Necht' A je množina a necht' n 1 je přirozené číslo. Pak libovolnou podmnožinu kartézské mocniny An nazýváme n-ární relací na množině A. Je-li n = 1, pak je podmnožinou množiny A = A1 a říkáme též, že je unární relace na A. Je-li n = 2, tedy je-li A2 , říkáme, že je binární relace na A. Je-li n = 3, tj. A3 , říkáme, že je ternární relace na A. Ekvivalence a rozklady ­ p.4/33 Reflexivní relace Pro libovolnou množinu A je identické zobrazení idA relací na množině A, značí se též A, takže A = {(a, a) | a A}, a nazývá se diagonální relace na A. Ekvivalence a rozklady ­ p.5/33 Reflexivní relace Pro libovolnou množinu A je identické zobrazení idA relací na množině A, značí se též A, takže A = {(a, a) | a A}, a nazývá se diagonální relace na A. Relace na A se nazývá reflexivní, je-li splněno A , tedy platí-li (a A)(a a). Ekvivalence a rozklady ­ p.5/33 Reflexivní relace Pro libovolnou množinu A je identické zobrazení idA relací na množině A, značí se též A, takže A = {(a, a) | a A}, a nazývá se diagonální relace na A. Relace na A se nazývá reflexivní, je-li splněno A , tedy platí-li (a A)(a a). reflexivnost : a) každý bod je opatřen smyčkou, b) v hlavní diagonále tabulky jsou samé jedničky.Ekvivalence a rozklady ­ p.5/33 Symetrická relace Relace na A se nazývá symetrická, je-li splněno = -1 , tedy platí-li (a, b A)(a b = b a). Ekvivalence a rozklady ­ p.6/33 Symetrická relace Relace na A se nazývá symetrická, je-li splněno = -1 , tedy platí-li (a, b A)(a b = b a). symetrie : a) mezi dvěma různými body jsou bud' dvě šipky nebo žádná šipka b) tabulka je symetrická podle hlavní diagonály Ekvivalence a rozklady ­ p.6/33 Antisymetrická relace Relace na A se nazývá antisymetrická, je-li splněno -1 A, tedy platí-li (a, b A)(a b & b a = a = b). Ekvivalence a rozklady ­ p.7/33 Antisymetrická relace Relace na A se nazývá antisymetrická, je-li splněno -1 A, tedy platí-li (a, b A)(a b & b a = a = b). antisymetrie : a) mezi dvěma různými body je bud' jedna nebo žádná šipka b) dvě různá políčka symetrická po hlavní diagonály obsahují nejvýs jednu jedničku Ekvivalence a rozklady ­ p.7/33 Ú plná relace Relace na A se nazývá úplná, je-li splněno -1 A × A, tedy platí-li (a, b A)(a b b a ). Ekvivalence a rozklady ­ p.8/33 Ú plná relace Relace na A se nazývá úplná, je-li splněno -1 A × A, tedy platí-li (a, b A)(a b b a ). úplnost : a) každý bod je opatřen smyčkou a každé dva různé body jsou spojeny šipkou b) v hlavní diagonále jsou samé jedničk a dvě různá políčka symetrická podle hlavní diagonály obsahují alespoň jednu jedničku Ekvivalence a rozklady ­ p.8/33 Tranzitivní a asymetrická relace Relace na A se nazývá tranzitivní, je-li splněno , tedy platí-li (a, b, c A)(a b & b c = a c). Ekvivalence a rozklady ­ p.9/33 Tranzitivní a asymetrická relace Relace na A se nazývá tranzitivní, je-li splněno , tedy platí-li (a, b, c A)(a b & b c = a c). Relace na A se nazývá asymetrická, je-li splněno -1 = , tedy platí-li (a, b A)(a b = b /a). Ekvivalence a rozklady ­ p.9/33 Příklady relací I Příklad E 1. Necht' A = N , B = N . Pak = {(x, y) N × N | y - x je kladné číslo} je relací mezi množinami A, B. Ekvivalence a rozklady ­ p.10/33 Příklady relací I Příklad E 1. Necht' A = N , B = N . Pak = {(x, y) N × N | y - x je kladné číslo} je relací mezi množinami A, B. reflexivní ?? symetrická antisymetrická tranzitivní úplná Ekvivalence a rozklady ­ p.10/33 Příklady relací I Příklad E 1. Necht' A = N , B = N . Pak = {(x, y) N × N | y - x je kladné číslo} je relací mezi množinami A, B. reflexivní NE symetrická ?? antisymetrická tranzitivní úplná Ekvivalence a rozklady ­ p.10/33 Příklady relací I Příklad E 1. Necht' A = N , B = N . Pak = {(x, y) N × N | y - x je kladné číslo} je relací mezi množinami A, B. reflexivní NE symetrická NE antisymetrická ?? tranzitivní úplná Ekvivalence a rozklady ­ p.10/33 Příklady relací I Příklad E 1. Necht' A = N , B = N . Pak = {(x, y) N × N | y - x je kladné číslo} je relací mezi množinami A, B. reflexivní NE symetrická NE antisymetrická ANO tranzitivní ?? úplná Ekvivalence a rozklady ­ p.10/33 Příklady relací I Příklad E 1. Necht' A = N , B = N . Pak = {(x, y) N × N | y - x je kladné číslo} je relací mezi množinami A, B. reflexivní NE symetrická NE antisymetrická ANO tranzitivní ANO úplná ?? Ekvivalence a rozklady ­ p.10/33 Příklady relací I Příklad E 1. Necht' A = N , B = N . Pak = {(x, y) N × N | y - x je kladné číslo} je relací mezi množinami A, B. reflexivní NE symetrická NE antisymetrická ANO tranzitivní ANO úplná NE Ekvivalence a rozklady ­ p.10/33 Příklady relací II Příklad E 2. Necht' A je množina. Dva speciální případy relací na množině A jsou prázdná množina (relace) a univerzální relace A × A. Ekvivalence a rozklady ­ p.11/33 Příklady relací II Příklad E 2. Necht' A je množina. Dva speciální případy relací na množině A jsou prázdná množina (relace) a univerzální relace A × A. prázdná relace univerzální relace reflexivní ?? ?? symetrická antisymetrická tranzitivní úplná Ekvivalence a rozklady ­ p.11/33 Příklady relací II Příklad E 2. Necht' A je množina. Dva speciální případy relací na množině A jsou prázdná množina (relace) a univerzální relace A × A. prázdná relace univerzální relace reflexivní NE ANO symetrická ?? ?? antisymetrická tranzitivní úplná Ekvivalence a rozklady ­ p.11/33 Příklady relací II Příklad E 2. Necht' A je množina. Dva speciální případy relací na množině A jsou prázdná množina (relace) a univerzální relace A × A. prázdná relace univerzální relace reflexivní NE ANO symetrická ANO ANO antisymetrická ?? ?? tranzitivní úplná Ekvivalence a rozklady ­ p.11/33 Příklady relací II Příklad E 2. Necht' A je množina. Dva speciální případy relací na množině A jsou prázdná množina (relace) a univerzální relace A × A. prázdná relace univerzální relace reflexivní NE ANO symetrická ANO ANO antisymetrická ANO NE tranzitivní ?? ?? úplná Ekvivalence a rozklady ­ p.11/33 Příklady relací II Příklad E 2. Necht' A je množina. Dva speciální případy relací na množině A jsou prázdná množina (relace) a univerzální relace A × A. prázdná relace univerzální relace reflexivní NE ANO symetrická ANO ANO antisymetrická ANO NE tranzitivní ANO ANO úplná ?? ?? Ekvivalence a rozklady ­ p.11/33 Příklady relací II Příklad E 2. Necht' A je množina. Dva speciální případy relací na množině A jsou prázdná množina (relace) a univerzální relace A × A. prázdná relace univerzální relace reflexivní NE ANO symetrická ANO ANO antisymetrická ANO NE tranzitivní ANO ANO úplná NE ANO Ekvivalence a rozklady ­ p.11/33 Příklady relací III Příklad E 3. Bud' A množina. Uvažme relaci R = {(X, Y ) P(A) × P(A) : X Y }. Ekvivalence a rozklady ­ p.12/33 Příklady relací III Příklad E 3. Bud' A množina. Uvažme relaci R = {(X, Y ) P(A) × P(A) : X Y }. reflexivní ?? symetrická antisymetrická tranzitivní úplná Ekvivalence a rozklady ­ p.12/33 Příklady relací III Příklad E 3. Bud' A množina. Uvažme relaci R = {(X, Y ) P(A) × P(A) : X Y }. reflexivní ANO symetrická ?? antisymetrická tranzitivní úplná Ekvivalence a rozklady ­ p.12/33 Příklady relací III Příklad E 3. Bud' A množina. Uvažme relaci R = {(X, Y ) P(A) × P(A) : X Y }. reflexivní ANO symetrická NE antisymetrická ?? tranzitivní úplná Ekvivalence a rozklady ­ p.12/33 Příklady relací III Příklad E 3. Bud' A množina. Uvažme relaci R = {(X, Y ) P(A) × P(A) : X Y }. reflexivní ANO symetrická NE antisymetrická ANO tranzitivní ?? úplná Ekvivalence a rozklady ­ p.12/33 Příklady relací III Příklad E 3. Bud' A množina. Uvažme relaci R = {(X, Y ) P(A) × P(A) : X Y }. reflexivní ANO symetrická NE antisymetrická ANO tranzitivní ANO úplná ?? Ekvivalence a rozklady ­ p.12/33 Příklady relací III Příklad E 3. Bud' A množina. Uvažme relaci R = {(X, Y ) P(A) × P(A) : X Y }. reflexivní ANO symetrická NE antisymetrická ANO tranzitivní ANO úplná NE Ekvivalence a rozklady ­ p.12/33 Příklady relací IV Příklad E 4. Bud' A množina. Množina A = {(x, x) : x A} je relace rovnosti na A. Ekvivalence a rozklady ­ p.13/33 Příklady relací IV Příklad E 4. Bud' A množina. Množina A = {(x, x) : x A} je relace rovnosti na A. reflexivní ?? symetrická antisymetrická tranzitivní úplná Ekvivalence a rozklady ­ p.13/33 Příklady relací IV Příklad E 4. Bud' A množina. Množina A = {(x, x) : x A} je relace rovnosti na A. reflexivní ANO symetrická ?? antisymetrická tranzitivní úplná Ekvivalence a rozklady ­ p.13/33 Příklady relací IV Příklad E 4. Bud' A množina. Množina A = {(x, x) : x A} je relace rovnosti na A. reflexivní ANO symetrická ANO antisymetrická ?? tranzitivní úplná Ekvivalence a rozklady ­ p.13/33 Příklady relací IV Příklad E 4. Bud' A množina. Množina A = {(x, x) : x A} je relace rovnosti na A. reflexivní ANO symetrická ANO antisymetrická ANO tranzitivní ?? úplná Ekvivalence a rozklady ­ p.13/33 Příklady relací IV Příklad E 4. Bud' A množina. Množina A = {(x, x) : x A} je relace rovnosti na A. reflexivní ANO symetrická ANO antisymetrická ANO tranzitivní ANO úplná ?? Ekvivalence a rozklady ­ p.13/33 Příklady relací IV Příklad E 4. Bud' A množina. Množina A = {(x, x) : x A} je relace rovnosti na A. reflexivní ANO symetrická ANO antisymetrická ANO tranzitivní ANO úplná NE Ekvivalence a rozklady ­ p.13/33 Relace ekvivalence Relace na množině A, která je současně reflexivní, symetrická a tranzitivní, se nazývá ekvivalence na A. Ekvivalence a rozklady ­ p.14/33 Relace ekvivalence Relace na množině A, která je současně reflexivní, symetrická a tranzitivní, se nazývá ekvivalence na A. Jsou-li prvky a, b A takové, že a b, říkáme, že prvek a je ekvivalentní prvku b podle . Ekvivalence a rozklady ­ p.14/33 Relace ekvivalence Relace na množině A, která je současně reflexivní, symetrická a tranzitivní, se nazývá ekvivalence na A. Jsou-li prvky a, b A takové, že a b, říkáme, že prvek a je ekvivalentní prvku b podle . Příklady ekvivalencí na množině A - diagonální (nejmenší) a univerzální relace (největší). Ekvivalence a rozklady ­ p.14/33 Jádro zobrazení Necht' A, B jsou množiny a necht' f : A B je zobrazení. Definujme relaci ker f na A předpisem: (a, b A)((a, b) ker f f(a) = f(b)). Ekvivalence a rozklady ­ p.15/33 Jádro zobrazení Necht' A, B jsou množiny a necht' f : A B je zobrazení. Definujme relaci ker f na A předpisem: (a, b A)((a, b) ker f f(a) = f(b)). Pak ker f je ekvivalence na A a nazývá se jádro zobrazení f. Ekvivalence a rozklady ­ p.15/33 Rozklad množiny Bud' A množina a bud' R P(A) libovolný soubor podmnožin množiny A splňující podmínky: / R, ( X, Y R)(X = Y = X Y = ), R = A. Ekvivalence a rozklady ­ p.16/33 Rozklad množiny Bud' A množina a bud' R P(A) libovolný soubor podmnožin množiny A splňující podmínky: / R, ( X, Y R)(X = Y = X Y = ), R = A. Pak R se nazývá rozklad množiny A. Ekvivalence a rozklady ­ p.16/33 Rozklad množiny Bud' A množina a bud' R P(A) libovolný soubor podmnožin množiny A splňující podmínky: / R, ( X, Y R)(X = Y = X Y = ), R = A. Pak R se nazývá rozklad množiny A. Množiny, jež jsou prvky R se nazývají třídy rozkladu R. Ekvivalence a rozklady ­ p.16/33 Intuitivní představa Rozklad na množině je možné si schematicky představit tak, že množinou A je kus papíru, který nůžkami rozstříháme na kousky, což budou příslušné třídy rozkladu. Ekvivalence a rozklady ­ p.17/33 Intuitivní představa Rozklad na množině je možné si schematicky představit tak, že množinou A je kus papíru, který nůžkami rozstříháme na kousky, což budou příslušné třídy rozkladu. Názorně řečeno, rozklad R reprezentuje rozdělení množiny A na soubor neprázdných vzájemně disjunktních tříd. Ekvivalence a rozklady ­ p.17/33 Grafické znázornění rozkladu Rozklad na množině si můžeme ilustrovat náčrtkem podobného tvaru, jaký je uveden na následujícím obrázku. Ekvivalence a rozklady ­ p.18/33 Grafické znázornění rozkladu Rozklad na množině si můžeme ilustrovat náčrtkem podobného tvaru, jaký je uveden na následujícím obrázku. Ekvivalence a rozklady ­ p.18/33 Příklady rozkladů - I Příklad D.1 Necht' A, B jsou množiny a necht' f : A B je zobrazení. Pro libovolný prvek b f(A) definujme množinu f-1 (b) = {a A | b = f(a)}. Ekvivalence a rozklady ­ p.19/33 Příklady rozkladů - I Příklad D.1 Necht' A, B jsou množiny a necht' f : A B je zobrazení. Pro libovolný prvek b f(A) definujme množinu f-1 (b) = {a A | b = f(a)}. Pak soubor množin {f-1 (b) | b f(A)} tvoří rozklad množiny A. Ř íkáme, že jde o rozklad množiny A indukovaný zobrazením f. Ekvivalence a rozklady ­ p.19/33 Příklady rozkladů - II Příklad D.2 Necht' A je libovolná neprázdná množina. Pak nejjednoduššími příklady rozkladů na množině A jsou následující dva rozklady : Ekvivalence a rozklady ­ p.20/33 Příklady rozkladů - II Příklad D.2 Necht' A je libovolná neprázdná množina. Pak nejjednoduššími příklady rozkladů na množině A jsou následující dva rozklady : R = {{a} : pro každé a A} , což je rozklad, který má tolik tříd, kolik prvků má množina A , přičemž každá jeho třída obsahuje vždy právě jeden prvek Ekvivalence a rozklady ­ p.20/33 Příklady rozkladů - II Příklad D.2 Necht' A je libovolná neprázdná množina. Pak nejjednoduššími příklady rozkladů na množině A jsou následující dva rozklady : R = {{a} : pro každé a A} , což je rozklad, který má tolik tříd, kolik prvků má množina A , přičemž každá jeho třída obsahuje vždy právě jeden prvek R = {A} , což je rozklad, který má jedinou třídu, a to množinu A . Ekvivalence a rozklady ­ p.20/33 Příklady rozkladů - III Příklad D.3 Necht' A = Z . Pak množiny Ekvivalence a rozklady ­ p.21/33 Příklady rozkladů - III Příklad D.3 Necht' A = Z . Pak množiny {x Z | x -2}, Ekvivalence a rozklady ­ p.21/33 Příklady rozkladů - III Příklad D.3 Necht' A = Z . Pak množiny {x Z | x -2}, {-1, 0}, Ekvivalence a rozklady ­ p.21/33 Příklady rozkladů - III Příklad D.3 Necht' A = Z . Pak množiny {x Z | x -2}, {-1, 0}, {x Z | x je sudé, kladné}, Ekvivalence a rozklady ­ p.21/33 Příklady rozkladů - III Příklad D.3 Necht' A = Z . Pak množiny {x Z | x -2}, {-1, 0}, {x Z | x je sudé, kladné}, {x Z | x je liché, kladné} Ekvivalence a rozklady ­ p.21/33 Příklady rozkladů - III Příklad D.3 Necht' A = Z . Pak množiny {x Z | x -2}, {-1, 0}, {x Z | x je sudé, kladné}, {x Z | x je liché, kladné} tvoří rozklad na množině Z všech celých čísel. Ekvivalence a rozklady ­ p.21/33 Příklady rozkladů - III Příklad D.3 Necht' A = Z . Pak množiny {x Z | x -2}, {-1, 0}, {x Z | x je sudé, kladné}, {x Z | x je liché, kladné} tvoří rozklad na množině Z všech celých čísel. Tento rozklad má 4 třídy, z nichž tři třídy mají ne- konečně mnoho prvků a jedna třída má konečně mnoho prvků. Ekvivalence a rozklady ­ p.21/33 Příklady rozkladů - IV Příklad D.4 Necht' A = R . Ekvivalence a rozklady ­ p.22/33 Příklady rozkladů - IV Příklad D.4 Necht' A = R . Pro libovolné celé číslo k označme symbolem Ik reálný interval