Uspořádání, Hasseovy diagramy

Uspořádání

• Uspořádání je matematický protějšek pojmu hierarchie

• Binární relace $U$ na množině $A\ne \varnothing$ se nazývá uspořádání, je-li reflexivní, antisymetrická a tranzitivní.

• Vlastnosti:

  • Reflexivní - Každé $x$ z $X$ je totožné s $x$, tedy $x=x$
  • Tranzitivní - Pokud $x\le y$ a $y\le z$, pak i $x\le z$
  • Antisymetrická - Pokud $x\le y$, pak neplatí $y\le x$, kromě pokud $x=y$

• Reflexivní a tranzitivní binární relace $R$ na $X$ se nazývá kvaziuspořádání

• Antisymetrické kvaziuspořádání se nazývá uspořádání

• Úplné uspořádání se nazývá lineární uspořádání neboli řetězec

• Pokud je relace $R$ uspořádání na množině $X$, pak se $<X,R>$ nazývá uspořádaná množina

• Relaci uspořádání na $X$ obvykle značíme $\le$ a místo $<x,y>\in \le$ píšeme $x\le y$

• Uspořádání pořád ještě není formálním protějškem “uspořádání” na které jsme zvyklí při porovnání čísel, protože v uspořádané množině mohou stále existovat prvky, které jsou nesrovnatelné (značíme $x\mid \mid y$)

• V lineárním uspořádání, neboli řetězci (úplné uspořádání) jsou každé dva prvky srovnatelné, tedy můžeme lineární uspořádání chápat jako matematický protějšek k pojmu “tradiční srovnání čísel”

• Každá relace identity $i{d}_x$ je uspořádání, které nazýváme antiřetězec, v kterém každé dva různé prvky z $X$ jsou nesrovnatelné ($x\mid \mid y$). Antiřetězce jsou nejmenší uspořádání, protože každé uspořádání na $X$ obsahuje $i{d}_x$

• Relaci uspořádání “menší rovno” na číselných množinách $\mathbb{N},\mathbb{Z},\mathbb{Q},...$ nazýváme přirozené uspořádání čísel (je reflexivní, antisymetrické, tranzitivní a úplné), nejedná se však o jediné přirozené uspořádání čísel na číselných množinách

• Když $\le$ je uspořádání na $X$, pak ${\le }^{-1}$ (inverzní) je uspořádání na $X$, které označujeme $\ge$

• Princip duality = V praxi to znamená, že pokud řeknu tvrzení pro nejmenší prvek v uspořádané množině $<X,R>$, tak platí i pro největší prvek v uspořádaní množině $<X,R^{-1}>$

Znázornění uspořádání a pokrytí

• Konečnou relaci uspořádání můžeme samozřejmě znázornit maticí, nebo orientovaným grafem, ale díky speciálním vlastnostem konečných uspořádání je můžeme znázorňovat mnohem přehledněji pomocí speciálních diagramů

• Ke každému uspořádání $\le$ na $X$ lze uvažovat odvozenou relaci $\prec$ definovanou předpisem

  • $x\prec y$, právě když $x<y$ a pro každé $z\in X$ platí: $x\le z\le y$ pak $z\in \{x,y\}$
  • Znamená že $x<y$ a zároveň neexistuje žádný prvek $z\in X$, který by se nacházel “mezi $x$ a $y$.” Zachycuje tedy informaci o prvcích, které se “bezprostředně pokrývají”

• Relaci $\prec$ nazýváme pokrytí příslušné $\le$

• výraz $x\prec y$ čteme “x je pokryt y” nebo “y pokrývá x”

• $\prec \subseteq \le$, tedy relace $\prec$ je obsažena v uspořádání $\le$

• Lze původní $\le$ “zrekonstruovat” z příslušného pokrytí $\prec$ takto:

  • $\le =Tra(Ref(\prec ))$

• Relace pokrytí je:

  • Ireflexivní, Asymetrická a není tranzitivní

Hasseův diagram

• Hasseův diagram je uspořádání $\le$ na konečné množině $X$
  • Prvky $x\in X$ se znázorní jako kroužky
  • Je-li $x\le y$, nakreslíme kroužek $x$ níže než kroužek $y$
  • Je-li $x\prec y$, propojíme kroužky $x$ a $y$ úsečkou

Příklad hasseova diagramu

---

Speciální prvky v uspořádaných množinách a jejich vztahy

• Nechť $<X,\le >$ je uspořádaná množina. Prvek $x\in X$ se nazývá:

  • minimální, jestliže pro každý $y\in X$ platí: pokud $y\le x$, pak $x=y$
  • nejmenší, jestliže $x\le y$ pro každý $y\in X$ (je pouze jeden)
  • maximální, jestliže pro každý $y\in X$ platí: pokud $x\le y$, pak $x=y$
  • největší, jestliže $y\le x$ pro každý $y\in X$ (je pouze jeden)

• Nechť $<X,\le >$ je uspořádaná množina. Pak platí:

  • V $<X,\le >$ existuje nejvýše jeden největší a jeden nejmenší prvek
  • Je-li $x\in X$ největší (nejmenší) prvek, pak je také maximální (minimální) a žádné další maximální (minimální) prvky se v $X$ nevyskytují
  • Pokud je $\le$ lineární uspořádání, pak je $x\in X$ největší (nejmenší) prvek, právě když je maximální (minimální)

Horní a dolní mez

• Nechť $<X,\le >$ je uspořádaná množina a $Y\subseteq X$. Definujeme množiny

  • $L(Y)=\{x\in X\mid x\le y$ platí pro každé $y\in Y\}$
    • Nazývá se dolní kužel množiny $Y$ v $<X,\le >$
    • Vznikne uspořádaná množina $<L(Y),{\le }_{L(Y)}>$
  • $U(Y)=\{x\in X\mid x\ge y$ platí pro každé $y\in Y\}$
    • Nazývá se horní kužel množiny $Y$ v $<X,\le >$
    • Vznikne uspořádaná množina $<U(Y),{\le }_{U(Y)}>$

• V horním (dolním) kuželi můžeme najít, pokud existuje, nejmenší (největší) prvek.

• Nechť $<X,\le >$ je uspořádaná množina a $Y\subseteq X$

  • Pokud má $L(Y)$ největší prvek, pak se nazývá infimum $Y$ a označuje se $inf(Y)$
  • Pokud má $U(Y)$ nejmenší prvek, pak se nazývá supremum $Y$ a označuje se $sup(Y)$

• Na základě existence infima či suprema ke každým dvěma prvkům definujeme speciální uspořádané množiny zvané polosvazy a svazy.

• Nechť $<X,\le >$ je uspořádaná množina.

  • Pokud pro každé $x,y\in X$ existuje $inf(x,y)$, pak $<X\le >$ nazveme průsekový svaz
  • Pokud pro každé $x,y\in X$ existuje $sup(x,y)$, pak $<X,\le >$ nazveme spojový svaz
  • Je-li $<X,\le >$ průsekový i spojový polosvaz, pak $<X,\le >$ nazveme svaz

• Svaz = pro každé dva prvky existuje supremum i infimum

• Každý konečný svaz má největší a nejmenší prvek

Navigace

Předchozí: Ekvivalence a rozklady Následující: Permutace, variace, kombinace Celý okruh: 1. Teoretické základy informačních technologií