Relace a zobrazení
Teorie k relacím a zobrazení, tedy opět diskrétní matematika.
Relace
je vztah prvků jedné množiny k prvkům množiny druhé.
DEF.: Binární relace je uspořádána trojice [A, B, R], kde A a B jsou libovolné množiny a R je podmnožina kartézského součinu . Množině A se říká definiční obor, množině B obor hodnot a množinu R nazýváme graf relace.
-
Značíme:
- Jako uspořádanou dvojici [x,y]
- Jako (x R y) ; kde x
A, y
B
-
Druhy:
- Symetrická - pokud (x R y), pak i (y R x). I prázdná relace je symetrická
- Tranzitivní - platí-li (x R y) a zároveň (y R z), potom platí i (x R z)
- Reflexivní - "je stejný", platí (x R x), kde x
A, x
B
- Antisymetrická - pokud (x R y) potom
(y R x)
Relaci, která je reflexivní, symetrická, a tranzitivní nazýváme relace ekvivalence.
Relaci, která je reflexivní, antisymetrická a tranzitivní nazýváme částečné uspořádání.