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 □ S1 ► < -š Obsah přednášky Uspořádané dvojice, n-tice oo Relace ooooooo Rozklad podle ekvivalence Celá čísla Obsah přednášky Uspořádané dvojice, n-tice Relace Rozklad podle ekvivalence Celá čísla Pavel Rychlý, Vojtěch Kovář Základy matematiky a statistiky pro humanitní obory I :l MU Brno Obsah přednášky Uspořádaná dvojice Uspořádané dvojice, n-tice •o Relace ooooooo Rozklad podle ekvivalence Celá čísla Uspořádaná dvojice (a, b) má první a druhý prvek —> na rozdíl od množiny záleží na pořadí prvků Definice pomocí množin . (a,b) = {{a},{a,b}} ■ 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,an) = (ai, (a2, (a3, (..., a„)...))) ■ (funguje jen pro konečné r?) Pavel Rychlý, Vojtěch Kovář Základy matematiky a statistiky pro humanitní obory I :l MU Brno Obsah přednášky Kartézský součin Uspořádané dvojice, n-tice om Relace ooooooo Rozklad podle ekvivalence Celá čísla Kartézský součin ■ Kartézský součin dvou množin A, B ■ A x B = {(a, b) | a e A a b e B} ■ —> 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 m A x B x C = {(a, b,c)\ aeA a be B a cgC} ■ podobně pro větší n Pavel Rychlý, Vojtěch Kovář Základy matematiky a statistiky pro humanitní obory I :l MU Brno Obsah přednášky Uspořádané dvojice, n-tice Relace Rozklad podle ekvivalence Celá čísla OO «000000 Relace 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 Pavel Rychlý, Vojtěch Kovář Základy matematiky a statistiky pro humanitní obory I :l MU Brno Obsah přednášky Uspořádané dvojice, n-tice Relace Rozklad podle ekvivalence Celá čísla OO O0OOOOO Relace Relace ■ Často říkáme relace na množině A" ■ tzn. podmnožina součinu A x A ■ resp. A x A x ... x A ■ Přehledný zápis binárních relací ■ tabulkou ■ grafem Pavel Rychlý, Vojtěch Kovář Základy matematiky a statistiky pro humanitní obory I :l MU Brno Obsah přednášky Relace - příklady Uspořádané dvojice, n-tice oo Relace OO0OOOO Rozklad podle ekvivalence Celá čísla Relace - příklady Relace identity na množině A ■ ld(A) - binární relace B ld(A) = {(a, a) e AxA | a e A} Relace větší nebo rovno na přirozených číslech ■ > (A/) - binární relace ■ > (A/) = {(a,b) e NxN | b C a} ■ (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) e NxNxN \ a + b = c} ■ a + b = c je jen jiný zápis pro (a, b, c) e +(A/) ■ —> všechny operace na číslech jsou relace = Pavel Rychlý, Vojtěch Kovář Základy matematiky a statistiky pro humanitní obory I :l MU Brno Obsah přednášky Uspořádané dvojice, n-tice Relace Rozklad podle ekvivalence Celá čísla OO OOO0OOO 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ž Va, beA((a,b)eR=> (b, a) e R ) Antisymetrie ■ R(A) je antisymetrická, právě tehdy, když ■ Va, b g A{ (a, b) g R a (b, a) g /? a = b ) Pavel Rychlý, Vojtech Kovář Základy matematiky a statistiky pro humanitní obory I :l MU Brno Obsah přednášky Uspořádané dvojice, n-tice Relace Rozklad podle ekvivalence Celá čísla OO OOOO0OO Vlastnosti relací Vlastnosti binárních relací (2) ■ Tranzitivita ■ R(A) je tranzitivní, právě tehdy, když ■ Va, 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 :l MU Brno Obsah přednášky Uspořádané dvojice, n-tice Relace Rozklad podle ekvivalence Celá čísla OO OOOOO0O 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 co) Obsah přednášky Vlastnosti relací Uspořádané dvojice, n-tice oo Relace oooooo< Rozklad podle ekvivalence Celá čísla 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 „krať (*) na přirozených číslech ■ Relace „má stejný zbytek po vydělení 2" na přirozených číslech Obsah přednášky Uspořádané dvojice, n-tice oo Relace ooooooo Rozklad podle ekvivalence Celá čísla Ekvivalence a rozklad ■ 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 jiné podmnožiny ■ Rozklad podle ekvivalence ■ množina těchto ,,ostrůvků" 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 oo Relace ooooooo Rozklad podle ekvivalence Celá čísla Ekvivalence a rozklad ■ Třída ekvivalence ■ , Jeden ostrůvek" ■ Ax = {a g A | (a,x) g R} ■ Rozklad množiny A podle ekvivalence R m A/R = {Ax | x g A} Pavel Rychlý, Vojtěch Kovář Základy matematiky a statistiky pro humanitní obory I Fl MU Brno Obsah přednášky Uspořádané dvojice, n-tice oo 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)) e R = a + d Uvažujme rozklad podle této ekvivalence = b+ c ■ třídy rozkladu jsou Da>b = {{x,y) I ((x, y), (a, b)) g R} m rozklad D j R odpovídá množině {Da^ Tento rozklad je konstrukcí celých čísel a, b g N} každá třída Dat> odpovídá číslu a — b Pavel Rychlý, Vojtěch Kovář Základy matematiky a statistiky pro humanitní obory I :l MU Brno Obsah přednášky Uspořádané dvojice, n-tice oo Relace ooooooo Rozklad podle ekvivalence Celá čísla 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í +, *, —, /