Výzkum struktury/Relace a množiny

Z Wikiverzity
Skočit na navigaci Skočit na vyhledávání
Jak používat klasifikační nálepkuTato stránka je součástí projektu:
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[editovat]

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.

Tak vzniká binární relace, kterou lze zapsat jako

Typy relace[editovat]

  • 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í[editovat]

Čá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í .

Zato však platí tyto podmínky:

  • - reflexivita (každý prvek je v relaci R sám se sebou)
  • - tranzitivita (pokud je prvek množiny v uspořádání mezi jinými dvěma prvky, jsou tyto dva rovněž srovnatelné)
  • - slabá antisymetrie (neexistují cykly v uspořádání)


  • Pokud relace vyhovuje podmínce 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í[editovat]

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í[editovat]

Podmínka:

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

Lineární uspořádání[editovat]

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

  1. tranzitivita:
  2. antisymetrie:
  3. trichotomie: