Binární relace na množině
-
Nechť jsou neprázné množiny. Kartézský součin množin a () je množina všech uspořádaných dvojic , kde .
-
Každou podmnožinu nazveme binární relace mezi množinami a . Je-li , pak nazveme binární relace na množině
-
Binární relace na množině jsou relace , kde
Vlastnosti binární relace
-
Nechť je relace na množině :
-
Reflexivní
- Pokud pro každé platí
- Každý prvek z je v relaci sám se sebou
- Na matici to poznáme pomocí diagonály jedniček
- V orientovaném grafu je u každého vrcholu smyška
-
Symetrická
- Pokud pro každé platí
- Každé se objeví i v převrácené formě, tedy
- Na matici to poznáme, že je symetrická podle diagonály
- V orientovaném grafu se projevuje tak, že buď jsou mezi body dvě hrany, nebo žádná
-
Antisymetrická
- Pokud pro každé platí
- Vyjadřuje, že pro každé dva různé prvky z neplatí zároveň a
- Každá dvě různá pole v matice, které jsou souměrné podle diagonály, neobsahují dvě jedničky
- V orientovaném grafu mezi dvěma vrcholy vede jedna nebo žádná hrana
-
Tranzitivní
- Pokud pro každé platí
- Pokud a , pak také
- V orientovaném grafu, když vede šipka z do a z do , tak musí vést šipka i z do
-
Ireflexivní
- Pokud pro každé platí
-
Asymetrická
- Pokud pro každé platí
-
Úplná
- Pokud pro každé platí
Speciální relace
- (Prázdná relace) - symetrická, antisymetrická, tranzitivní, ireflexivní, asymetrická
- Relace identity, - reflexivní, symetrická, antisymetrická, tranzitivní (a úplná, když je )
- Kartézský součin (plná relace) - reflexivní, symetrická, tranzitivní a úplná (antisymetrická pro )
Navigace
Předchozí: Funkce (zobrazení) a jejich vlastnosti Následující: Ekvivalence a rozklady Celý okruh: 1. Teoretické základy informačních technologií