Výzkum struktury/Relace a množiny

Tato stránka je součástí projektu:

Výzkum struktury

Příslušnost: všeobecná

Relace je vztah mezi prvky různých množin. Matematický popis množin a relací je ideálním nástrojem k popisu struktur, protože uspořádání je formou relace (vtahu), jak spolu části souvisejí.

Definice binární relace

Binární relace je relace mezi dvěma množinami (uspořádaná dvojice).

Mějme množinu A, B, které jsou spolu ve vztahu tak, že vyhovují podmínce P.
$R_{i}\subseteq A\times B\{(a,b)a\in A,b\in B|P\}$
Tak vzniká binární relace, kterou lze zapsat jako $aRb$

Typy relace

• ekvivalence - prvky množin jsou vůči sobě shodné, stejné, podobné, příbuzné
• uspořádání - prvky množin jsou vůči sobě uspořádané, záleží na pořadí
• zobrazení - prvky množin jsou zobrazením jiných prvků množin a proto obvykle představují funkce, vzorce, výrazy

Částečné uspořádání

Částečným uspořádáním je neostré uspořádání. Pokud jsou prvky množin nesrovnatelné pak se jedná o částečné uspořádání, neboli neplatí $(\forall x,y\in a)(xRy\vee yRx)$.

Zato však platí tyto podmínky:

• $(\forall x\in a)(xRx)$ - reflexivita (každý prvek je v relaci R sám se sebou)
• $(\forall x,y,z\in 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\in a)((xRy\land yRx)\implies x=y)$ - slabá antisymetrie (neexistují cykly v uspořádání)

• Pokud relace vyhovuje podmínce $A\subseteq B$ jedná se o neostré uspořádání na potenční množině (množině všech podmnožin) libovolné množiny. Množiny pak nelze porovnat (částečné uspořádání).
• Pokud relace vyhovuje podmínce, že jeden z prvků „je předkem“ na množině všech prvků. Množiny pak nelze porovnat (částečné uspořádání).

Nemůžeme tedy porovnávat množiny z různých hierarchických úrovní, leda bychom je z těchto úrovní dočasně vyjmuli a postavili je dočasně na stejnou úroveň. Například nelze srovnávat atom s molekulou, ale pouze atom s atomem nebo molekulu s molekulou. Avšak můžeme atom a molekulu dočasně vnímat na stejné úrovni a porovnat počet jejich částic, předem sice víme, že molekula bude mýt dohromady více protonů, neutronů a elektronů než atom, ale můžeme aspoň zjistit o kolik. Ovšem například motor škodovky nemůžeme srovnávat s celým autem BMW, zato by mělo smysl srovnávat motor škodovky a motor BMW. Můžeme však srovnávat to co je mezi motorem a celým autem shodné a to je rozměr. Ovšem opět budeme vědět jaká je mezi nimi relace předem, protože je jasné že celé auto bude větší než motor.

Úplné uspořádání

Je takové uspořádání, kde prvky z obou množin můžeme vzájemně porovnat. Tedy kdy x je rozdílné než y.

Ostré uspořádání

Podmínka:

• ¬ (a ⊂ a) (ireflexivnost)
• (a ⊂ b) ⇒ ¬ (b ⊂ a) (asymetrie)
• a ⊂ b ∧ b ⊂ c ⇒ a ⊂ c (tranzitivita)

Lineární uspořádání

Prvky množin jsou seřazeny jedno za druhým, záleží tedy na pořadí, množiny jsou srovnatelné. Podmínka:

1. tranzitivita: $aRb\land bRc\implies aRc\,\!$
2. antisymetrie: $aRb\land bRa\implies a=b\,\!$
3. trichotomie: $aRb\vee bRa\vee a=b\,\!$