Obsah přednášky Uspořádané dvojice, n-tice Relace Rozklad podle ekvivalence Celá čísla oo ooooooo Základy matematiky a statistiky pro humanitní obory I Pavel Rychlý Vojtěch Kovář Fakulta informatiky, Masarykova univerzita Botanická 68a, 602 00 Brno, Czech Republic {pary, xkovar3}@fi.muni.cz část 5 na rozdíl od množiny záleží na pořadí prvků ■ Definice pomocí množin . (a,Z>) = {{a},{a,Z>}} ■ takto jednoznačně rozlišíme, který z prvků je první ■ jsou možné i jiné definice? Jaké? ■ Uspořádané n-tice (kde n je přirozené) ■ trojice (a, b, c) = (a, (b, c)) ■ obecně (ai, a2, a3,a„) = (ai, (a2, (a3, (..., an)...))) ■ (funguje jen pro konečné n) Pavel Rychlý, Vojtěch Kovář Základy matematiky a statistiky pro humanitní obory I Fl MU Brn( Relace Rozklad podle ekvivalence Celá čísla ooooooo Kartézský součin Obsah přednášky Kartézský součin Uspořádané dvojic 09 ■ Kartézský součin dvou množin A, B ■ A x B = {(a, b) | a e A A b £ 6} ■ —> množina uspořádaných dvojic prvků z A a B ■ Kartézský součin více množin ■ analogicky - obsahuje uspořádané n-tice ■ A x B x C = {(a, b,c) \ a eA A be B A cgC} ■ podobně pro větší n - -00,0 Pavel Rychlý, Vojtěch Kovář Základy matematiky a statistiky pro humanitní obory I Uspořádané dvojice, n-tice Relace Rozklad podle ekvivalence OO »000000 Relace ■ Motivace ■ způsob, jak v matematice svázat dvě hodnoty (případně více) ■ vyjadřujeme, že objekty (množiny) v relaci mají něco společného ■ Binární relace ■ množina uspořádaných dvojic ■ —> podmnožina kartézského součinu ■ n-ární relace ■ množina uspořádaných n-tic {N) - binární relace ■ > (N) = {{a, b) G NxN | b C a} m (podle množinové konstrukce přirozených čísel - viz minulá přednáška) Relace plus na přirozených číslech ■ +(/V) - ternární relace ■ +(/V) = {(a, b, c) G NxNxN \ a + b = c} ■ a + b = c je jen jiný zápis pro (a, b, c) £ +(N) m —> všechny operace na číslech jsou relace Pavel Rychlý, Vojtěch Kovář Základy matematiky a statistiky pro humanitní obory I - -00,0 Uspořádané dvojice, n-tice Relace Rozklad podle ekvivalence ooo»ooo Vlastnosti relací Vlastnosti binárních relací ■ Už jste se s nimi setkali jinde ■ Reflexivita ■ R(A) je reflexivní, právě tehdy, když ■ Va g A( (a, a) g R ) ■ Symetrie ■ R(A) je symetrická, právě tehdy, když ■ y a, b g A( (a, b) g R => {b, a) g R ) ■ Antisymetrie ■ R(A) je antisymetrická, právě tehdy, když ■ y a, b g A( (a, b) g R a {b, a) g R a = b Pavel Rychlý, Vojtěch Kovář Základy matematiky a statistiky pro humanitní obory I Fl MU Brn( Uspořádané dvojice, n-tice Relace Rozklad podle ekvivalence oooo»oo Vlastnosti relací Vlastnosti binárních relací (2) ■ Tranzitivita ■ R(A) je tranzitivní, právě tehdy, když ■ y a, b,ceA( (a, b) g R a {b, c) g R (a, c) g R ) ■ Ekvivalence ■ R(A) je ekvivalence, právě tehdy, když je současně reflexivní, symetrická i tranzitivní ■ Uspořádání ■ R(A) je uspořádání, právě tehdy, když je současně reflexivní, antisymetrická i tranzitivní Pavel Rychlý, Vojtěch Kovář Základy matematiky a statistiky pro humanitní obory I Uspořádané dvojice, n-tice Relace Rozklad podle ekvivalence ooooo»o Vlastnosti relací Vlastnosti binárních relací - příklady ■ Identita na libovolné množině ■ splňuje všechny výše uvedené vlastnosti ■ —> ekvivalence i uspořádání ■ Relace < na přirozených číslech ■ není symetrická ■ —> uspořádání ■ Relace < na přirozených číslech ■ není symetrická ani reflexivní ■ —> ani ekvivalence, ani uspořádání ■ Relace na prázdné množině /?(0) ■ je 0 (podmnožina 0x0) ■ —> ekvivalence i uspořádání ■ (pro všechny prvky prázdné množiny platí kde Pavel Rychlý, Vojtěch Kovář Fl MU Brno Základy matematiky a statistiky pro humanitní obory I Uspořádané dvojice, n-tice Relace Rozklad podle ekvivalence oooooo* Vlastnosti relací Další příklady relací ■ Diskutujte jejich vlastnosti ■ pro malé množiny je zkuste zakreslit ■ Relace „sedí vedle" na přítomných studentech ■ Relace „sedí ve stejné řadě jako" na přítomných studentech ■ Relace „je dělitelem" na přirozených číslech ■ Relace „krát" (*) na přirozených číslech ■ Relace „má stejný zbytek po vydělení 2" na přirozených číslech Pavel Rychlý, Vojtěch Kovář Základy matematiky a statistiky pro humanitní obory I Fl MU Brn. Uspořádané dvojice, n-tice Rozklad podle ekvivalence oo ooooooo ■ Ekvivalence na množině A ■ reflexivní, symetrická, tranzitivní ■ díky těmto vlastnostem vytvoří „ostrůvky" ■ —> podmnožiny, v nichž každý prvek je v relaci s každým ■ —> žádný prvek není v relaci s žádným prvkem z podmnožiny ■ Rozklad podle ekvivalence ■ množina těchto „ostrůvků" Pavel Rychlý, Vojtěch Kovář Základy matematiky a statistiky pro humanitní obory I Fl MU Brn( Uspořádané dvojice, n-tice Rozklad podle ekvivalence oo ooooooo Ekvivalence a rozklad ■ Třída ekvivalence ■ , jeden ostrůvek" ■ Ax = {a g A | (a,x) € R} ■ Rozklad množiny A podle ekvivalence R m A/R = {AX \ x eA} Pavel Rychlý, Vojtěch Kovář Základy matematiky a statistiky pro humanitní obory I Fl MU Brn. Obsah přednášky Uspořádané dvojice OO n-tice Relace ooooooo Rozklad podle ekvivalence Celá čísla Definice celých čísel ■ Uvažujme množinu dvojic přirozených čísel ... ■ D = {(a, b) g NxN} ■ ... spolu s ekvivalencí R m ((a, b), (c, d)) g R = a + d = b + c m Uvažujme rozklad podle této ekvivalence ■ třídy rozkladu jsou Da,b = {{x,y) | {{x,y),{a,b)) g R} m rozklad D/R odpovídá množině {Da^ \ a, b g N} ■ Tento rozklad je konstrukcí celých čísel Z ■ každá třída Da^ odpovídá číslu a — b Pavel Rychlý, Vojtěch Kovář Fl MU Brno Základy matematiky a statistiky pro humanitní obory I Obsah přednášky Uspořádané dvojice, n-tice Relace Rozklad podle ekvivalence oo ooooooo Náměty k přemýšlení ■ Jak bude vypadat definice operací + a * na celých číslech? ■ nápověda: s využitím příslušných operací nad přirozenými čísly ■ Jak bude vypadat definice operace odečítání na celých číslech? ■ nápověda: s využitím operace + ■ Jak by vypadala definice racionálních čísel ■ nápověda: použijeme podobnou konstrukci jako v případě celých čísel ■ místo sčítání bude násobení ■ příslušná třída rozkladu bude odpovídat podílu ■ opět zkuste přemýšlet o definicích operací +, *, —, / Pavel Rychlý, Vojtěch Kovář Základy matematiky a statistiky pro humanitní obory I Fl MU Brn(