Procházet otázky :: SZZ na MFF UK

#

- Hlavní strana
- Okruhy
- Projít
- Stáhnout
- Co je potřeba
- Chci přispět
- Kredity

Hledat:

## Prohlížení státnicových textů

## Uspořádané množiny

Definice (Kartézský součin)

Nechť a jsou množiny. Symbolem označíme množinu všech uspořádaných dvojic tvaru , kde a . Formálně zapsáno: se nazývá kartézský součin množin a .

Kartézský součin někdy značíme jako .

Definice (relace)

Relace R je množina uspořádaných dvojic. Jsou-li a množiny, nazývá se libovolná podmnožina kartézského součinu relací mezi a . Zdaleka nejdůležitější případ je . V takovém případě mluvíme o relaci na , což je tedy libovolná podmnožina .

Náleží-li relaci , tedy , říkáme, že a jsou v relaci . Značíme .

Definice (druhy relací)

Relace může být:

- reflexivní, jestliže pro každné platí
- ireflexivní, jestliže platí
- symetrická, jestliže
- tranzitivní, jestliže
- antisymetrická, jestliže

Definice (ekvivalence)

Řekneme, že relace na je ekvivalence na , jestliže je symetrická, reflexivní a tranzitivní.

Definice (uspořádání, uspořádaná množina)

Uspořádání na nějaké množině je každá relace na , která je reflexivní, tranzitivní a antisymetrická. Uspořádaná množina je dvojice , kde je množina a je uspořádání na .

Pro uspořádání se používá značení nebo . Pro každé uspořádání lze odvodit ostrou nerovnost nebo , kde platí, že .

Příklady

Uspořádané množiny:

- , kde je relace dělí
- , kde označuje množinu všech podmnožin a normální množinovou inkluzi
- orientovaný acyklický graf s relací

Definice (lineární uspořádání)

Lineární uspořádání je takové uspořádání, kde pro každé dva prvky a platí buď nebo . Někdy se také nazývá úplné uspořádání.

Uspořádání, které není úplné, nazýváme částečným uspořádáním.

Definice (bezprostřední přechůdce)

Bezprostřední předchůdce prvku je takový prvek , pro který platí , a neexistuje žádné takové , že .

Poznámka (Hasseův diagram)

Při znázorňovaní se uspořádaná množina zakresluje pomocí bodů a šipek, jako kterákoliv jiná relace. Protože těchto šipek by bylo mnoho, vychází se z tranzitivity a znázorňují se šipky pouze mezi prvky a jejich bezprostředními předchůdci. Přijmeme-li navíc konvenci, že v obrázku povedou všechny šipky nahoru, není třeba zakreslovat směr šipek, pouze spojnice bodů. Takovéto znázornění se pak nazývá Hasseův diagram.

Poznámka (uspořádání na kartézském součinu)

Mám-li dvě množiny a a na nich uspořádání a můžu definovat složené uspořádání

- po složkách -
- lexikograficky -

Definice

Říkáme, že a jsou isomorfní uspořádané množiny, pokud existuje nějaké vzájemně jednoznačné zobrazení takové, že pro každé platí právě když .

Definice (Předuspořádání)

Předuspořádání nazveme každou relaci, která je reflexivní a transitivní (nebudeme tedy požadovat antisymetrii - mohou vznikat cykly).

Poznámka

Mám-li množinu s relací , která je předuspořádání, potom relace je uspořádání na množině (rozklad podle tříd ekvivalence ), kde .

Definice

Nezávislý systém podmnožin množiny je podmnožina taková, že každé dvě množiny jsou neporovnatelné relací náležení.

Věta (Spernerova)

Libovolný nezávislý systém podmnožin -prvkové množiny má nejvýš množin.

TODO: Patří sem dobré uspořádání a Zernelova věta??? (to by znamenalo přidat sem i supremum, infimum, řetězec, nejmenší a největší prvek)