Relace ekvivalence

• Ekvivalence je reflexivní, symetrická a tranzitivní relace. Příklady relací ekvivalence a jejich přirozený vztah ke "shlukování" - rozkladům nosné množiny.
• Důraz je na správné intuitivní pochopení, co to znamená relace ekvivalence (tj. že prvky v třídách jsou vždy něčím "stejné" a zároveň "různé" od ostatních tříd). 
• Je dobré trénovat i formální stránku rozkladů množin, přesně podle definice z přednášky.

• Použití rozkladu podle ekvivalence v matematice:
  • Zbytkové třídy modulo m, modulární aritmetika.
  • V Lekci 3 jsme říkali, že kartézský součin množin lze "deklarovat" jako asociativní operaci, třebaže formálně pro uspořádané dvojice/trojice platí (a,(b,c))!=((a,b),c). Pro to stačí prostě definovat relaci (a,(b,c)) ~ ((a,b),c) plus její přirozené rozšíření na uspořádané k-tice, která je ekvivalencí, a pak místo k-tic s různým závorkováním pracovat s uspořádanou k-ticí coby třídou ekvivalence určenou ~. Rázem tak na závorkách přestane záležet i v kartézském součinu.
  • Konstrukce číselných oborů - z přirozených na celá čísla coby dvojice (a,b) s "významem" a-b, stejně tak z celých na racionální čísla coby dvojice (c,d) s "významem" c/d. 

Relace uspořádání

• Relace uspořádání je reflexivní, antisymetrická a tranzitivní, vysvětlení role reflexivity jako neostré versus "ostré uspořádání". Ne všechny dvojice na uspořádané množině jsou porovnatelné - proto se někdy říká "částečné uspořádání".
• Popisy relací uspořádání - výčtem dvojic, slovním popisem, Hasseovým diagramem. Kromě slovního popisu na obecné konečné množině (jako "mezi studenty sedící v posluchárně...") se příklady soustřeďují na malé uspořádané množiny a důraz se opět klade na pochopení, jak uspořádání vypadají a jak je použít.
  • Konstrukce uspořádání po složkách a lexikografického.
  • Jiným vhodným příkladem uspořádání je dělitelnost na přirozených číslech.

• Pojmy uspořádaných množin: nejmenší/největší prvek, minimální a maximální (čím se tyto liší od nejmenších/největších!), infimum a supremum podmnožiny, atd. Tyto pojmy je nejlepší trénovat na malých Hasseovských diagramech.
• Předuspořádání - pochopit význam asociované ekvivalence a z ní získaného jádra předuspořádání.
  V mnoha praktických situacích si říkáme, že nějaké věci "uspořádáme" a přitom to je pouze předuspořádání! Vezměme si třeba "uspořádání zboží podle ceny" - co děláme s těmi, co stojí stejně?

• Lehce lze poukázat (pokud zbývá čas) na nekonečné uspořádané množiny a jejich "divné" chování, jako třeba možná neexistence minimálního či maximálního prvku atd.

Možné příklady k procvičení ekvivalencí

• Určete v každém z následujících dvou případů, zda popsaná relace mezi studenty v posluchárně je ekvivalencí:
  • Student A je v relaci s B, pokud sedí ve stejné řadě a zároveň mají stejnou barvu vlasů.
  • Student A je v relaci s B, pokud sedí ve stejné řadě nebo mají stejnou barvu vlasů.
• Binární relace R na množině {a,b,c,d,e,f,g,h,i} je dána níže uvedeným výčtem dvojic. Kolik a jakých tříd ekvivalence určuje reflexivní, symetrický a tranzitivní uzávěr relace R? (Nakreslete si tuto relaci i její uzávěr.)
  • R = {(a,b),(c,c),(c,i),(d,b),(d,g),(f,b),(f,i),(i,e)}
  • R = {(a,e),(a,h),(e,a),(f,i),(g,i),(h,a),(i,f),(i,g)}

• Na množině všech celých kladných čísel definujeme relaci ekvivalence takto: dvě čísla x,y jsou v relaci, pokud mají obě ve svém prvočíselném rozkladu stejný počet prvočísel (bez ohledu na jejich mocninu). Nejprve dokažte, že se skutečně jedná o ekvivalenci. Poté určete, jak vypadají třídy této ekvivalence v restrikci na "malá" celá kladná čísla. Například, v jaké třídě ekvivalence se nachází číslo 1 a v jaké číslo 2?

Možné příklady k procvičení uspořádaných množin

• Základní příklady jako;
  • student A je v relaci se studentem B, právě když A sedí ve stejné řadě jako B a není napravo od B,
  • student A je v relaci se studentem B, právě když B sedí v některé řadě před A (je třeba reflexivní uzávěr!).
• Vezmeme-li systém všech podmnožin dané množiny s uspořádáním inkluzí, co je pak infimem a supremem libovolné dvojice množin?
• Vezmeme-li si množinu všech přirozených čísel N uspořádaných relací dělitelnosti, co je pak infimem a supremem libovolné podmnožiny A⊂N ? Proč toto supremum a infimum vždy existuje (což je poměrně nezvyklý úkaz)?
  Pokud toto uspořádání dělitelností omezíme na nosnou množinu N\{1}, co jsou pak všechny minimální prvky?
• Multikriteriální uspořádání:
  • Lexikografické uspořádání - jak se v počítači porovnávají dva řetězce podle abecedy?
  • Uspořádání po složkách - který ze studentů má "lepší počítač" (složkami jsou třeba CPU, paměť, disk, baterie, ...)?
• Předuspořádání - viz poslední příklad porovnání počítačů. Co když dva studenti mají různé počítače, které však mají identické srovnávané hodnoty? Porušuje to antisymetrii, avšak přirozeným rozřešením je před uspořádáním "shlukovat" objekty identických parametrů do tříd ekvivalence...

(Pokud bude čas a chuť...)

Tvrzení o uspořádaných množinách k procvičení důkazů - volitelné

• Na konečné uspořádané množině je vždy alespoň jeden minimální prvek (proč na nekonečné ne?).
• Pokud je prvek nejmenší, musí to být právě jediný minimální prvek, ale naopak to platí jen na konečných množinách.
• Lexikografické uspořádání podle lineárně uspořádaných složek poskytuje opět lineární uspořádání.
• Pro každou konečnou uspořádanou množinu existuje systém konečných množin takový, že jejich množinová inkluze přesně odpovídá původnímu uspořádání (neboli každé konečné uspořádání je isomorfní nějakému uspořádání vhodných množin inkluzí).