Uspořádání

Technology

12 hours ago

Author

Uspořádání (přesněji neostré částečné uspořádání) je matematický pojem z teorie uspořádání. Jde o binární reflexivní, slabě antisymetrickou a tranzitivní relaci, tj. relaci, pro kterou platí následující podmínky: * ( \forall x \isin a)(xRx) - reflexivita (každý prvek je v relaci R sám se sebou) * ( \forall x,y,z \isin a)((xRy \land yRz) \implies xRz) - tranzitivita (pokud je prvek množiny v uspořádání mezi jinými dvěma prvky, jsou tyto dva rovněž srovnatelné) * ( \forall x,y \isin a)((xRy \land yRx) \implies x = y) - slabá antisymetrie (neexistují cykly v uspořádání)

Množina, na které je definováno uspořádání, se nazývá uspořádaná (nebo též poset z anglického partially ordered set). Uspořádané množiny lze graficky znázornit pomocí Hasseových diagramů.

Příklady

Relace ≤ je uspořádání na přirozených, celých, racionálních i reálných číslech. * Relace \subseteq ("být podmnožinou") je uspořádání na třídě všech množin (na univerzální třídě). +more * Relace dělitelnosti | (a dělí b) je uspořádáním na přirozených číslech. * Sémantický důsledek ⊨ je uspořádáním logických formulí ve výrokové logice i logice prvního řádu.

Naopak relace na množině osob „být potomkem“ není neostrým uspořádáním, protože nesplňuje vlastnost reflexivity. Relace je ireflexivní, asymetrická a tranzitivní, jedná se tedy o ostré uspořádání.