1. Mějme množinu \( A = \{1, 2, 3, 4\} \) a relaci \( R = \{(1,1),(2,2),(3,3),(4,4),(1,2),(2,1),(3,4),(4,3)\} \). Určete, zda je \( R \) relací ekvivalence.
Řešení příkladu 1:
Relace \( R \) je ekvivalence právě tehdy, když je reflexivní, symetrická a tranzitivní.
Reflexivita znamená, že pro každý prvek \( a \in A \) platí \( (a,a) \in R \). Ve zadané relaci jsou všechny dvojice \( (1,1), (2,2), (3,3), (4,4) \), takže reflexivita platí.
Symetrie znamená, že pokud je \( (a,b) \in R \), pak i \( (b,a) \in R \). V relaci je \( (1,2) \) a zároveň \( (2,1) \), stejně tak \( (3,4) \) a \( (4,3) \). Symetrie tedy platí.
Tranzitivita znamená, že pokud jsou v relaci \( (a,b) \) a \( (b,c) \), pak musí být i \( (a,c) \). Zkontrolujeme:
Pro \( (1,2) \) a \( (2,1) \) musí být \( (1,1) \) – což je pravda.
Pro \( (3,4) \) a \( (4,3) \) musí být \( (3,3) \) – což je pravda.
Žádné jiné kombinace nesplňují podmínku porušení tranzitivity. Tedy tranzitivita platí.
Všechny podmínky jsou splněny, relace \( R \) je tedy relace ekvivalence.
2. Mějme množinu \( B = \{a, b, c\} \) a relaci \( S = \{(a,a), (b,b), (c,c), (a,b), (b,c)\} \). Je relace \( S \) částečným uspořádáním?
Řešení příkladu 2:
Částečné uspořádání je relace, která je reflexivní, antisymetrická a tranzitivní.
Reflexivita: V relaci jsou \( (a,a), (b,b), (c,c) \), reflexivita tedy platí.
Antisymetrie: Pro antisymetrii platí, že pokud \( (x,y) \) a \( (y,x) \) jsou v relaci, potom \( x = y \). V relaci je \( (a,b) \), ale není \( (b,a) \), a \( (b,c) \), ale není \( (c,b) \). Žádná dvojice nesporně porušuje antisymetrii, tudíž antisymetrie platí.
Tranzitivita: Zkontrolujeme, zda z \( (a,b) \) a \( (b,c) \) plyne \( (a,c) \). Dvojice \( (a,c) \) však v relaci není, tranzitivita tedy neplatí.
Protože relace není tranzitivní, není částečným uspořádáním.
3. Na množině \( C = \{1, 2, 3, 4, 5\} \) je definována relace \( T = \{(1,1),(2,2),(3,3),(4,4),(5,5),(1,2),(2,3),(3,4),(4,5)\} \). Je \( T \) částečným uspořádáním?
Řešení příkladu 3:
Částečné uspořádání vyžaduje reflexivitu, antisymetrii a tranzitivitu.
Reflexivita: Relace obsahuje všechny \( (a,a) \) pro \( a \in C \), reflexivita tedy platí.
Antisymetrie: Zkontrolujeme, zda neexistují \( (a,b) \) a \( (b,a) \) pro \( a \neq b \). Ve zadané relaci žádné takové dvojice nejsou, antisymetrie tedy platí.
Tranzitivita: Zkontrolujeme, zda platí, že pokud \( (a,b) \in T \) a \( (b,c) \in T \), tak \( (a,c) \in T \).
Máme \( (1,2) \) a \( (2,3) \), je \( (1,3) \in T \)? Ne, není.
Máme \( (2,3) \) a \( (3,4) \), je \( (2,4) \in T \)? Ne, není.
Máme \( (3,4) \) a \( (4,5) \), je \( (3,5) \in T \)? Ne, není.
Relace není tranzitivní, takže není částečným uspořádáním.
4. Na množině \( D = \{x, y, z\} \) je relace \( U = \{(x,x),(y,y),(z,z),(x,y),(y,z),(x,z)\} \). Je relace \( U \) částečným uspořádáním?
Řešení příkladu 4:
Reflexivita: Jsou zde všechny \( (a,a) \) pro \( a \in D \), reflexivita platí.
Antisymetrie: Zkontrolujeme, zda neexistují \( (a,b) \) a \( (b,a) \) s \( a \neq b \). V relaci je \( (x,y), (y,z), (x,z) \), ale ne jejich inverzní dvojice. Antisymetrie tedy platí.
Tranzitivita: Zkontrolujeme, zda pokud \( (a,b) \) a \( (b,c) \) jsou v relaci, je i \( (a,c) \).
Z \( (x,y) \) a \( (y,z) \) plyne \( (x,z) \), které je v relaci.
Relace je reflexivní, antisymetrická i tranzitivní, takže je částečným uspořádáním.
5. Mějme množinu \( E = \{1, 2, 3\} \) a relaci \( V = \{(1,1),(2,2),(3,3),(1,2),(2,3),(1,3),(2,1)\} \). Je relace \( V \) uspořádáním?
Řešení příkladu 5:
Reflexivita: Jsou zde všechny \( (a,a) \) pro \( a \in E \), reflexivita tedy platí.
Antisymetrie: Je-li v relaci \( (1,2) \) i \( (2,1) \), přičemž \( 1 \neq 2 \), antisymetrie je porušena.
Relace není antisymetrická, proto není uspořádáním.
6. Mějme množinu \( F = \{a, b, c, d\} \) a relaci \( W = \{(a,a),(b,b),(c,c),(d,d),(a,b),(b,c),(c,d),(a,c),(a,d),(b,d)\} \). Je \( W \) částečným uspořádáním?
Řešení příkladu 6:
Reflexivita: Obsahuje všechny \( (x,x) \) pro \( x \in F \), reflexivita platí.
Antisymetrie: Neobsahuje žádné inverzní dvojice kromě stejných prvků, antisymetrie platí.
Tranzitivita: Všechny tranzitivní dvojice jsou obsaženy, např. z \( (a,b) \) a \( (b,c) \) je \( (a,c) \) v relaci, z \( (b,c) \) a \( (c,d) \) je \( (b,d) \) v relaci, z \( (a,c) \) a \( (c,d) \) je \( (a,d) \) v relaci.
Relace je reflexivní, antisymetrická i tranzitivní, tedy částečným uspořádáním.
7. Mějme množinu \( G = \{1, 2, 3\} \) a relaci \( X = \{(1,1),(2,2),(3,3),(1,2),(2,3),(3,1)\} \). Je relace \( X \) ekvivalencí?
Řešení příkladu 7:
Reflexivita: Obsahuje \( (1,1), (2,2), (3,3) \), reflexivita platí.
Symetrie: Obsahuje \( (1,2) \), ale neobsahuje \( (2,1) \), symetrie neplatí.
Relace není symetrická, tedy není ekvivalencí.
8. Mějme množinu \( H = \{x, y, z\} \) a relaci \( Y = \{(x,x), (y,y), (z,z), (x,y), (y,x), (y,z), (z,y)\} \). Je \( Y \) relace ekvivalence?
Řešení příkladu 8:
Reflexivita: Obsahuje \( (x,x), (y,y), (z,z) \), reflexivita platí.
Symetrie: Pro každou dvojici \( (a,b) \) je i \( (b,a) \), symetrie platí.
Tranzitivita: Zkontrolujme všechny kombinace:
Z \( (x,y) \) a \( (y,x) \) plyne \( (x,x) \) – je v relaci.
Z \( (y,z) \) a \( (z,y) \) plyne \( (y,y) \) – je v relaci.
Z \( (x,y) \) a \( (y,z) \) by mělo plynout \( (x,z) \), ale \( (x,z) \) není v relaci, tranzitivita neplatí.
Relace není tranzitivní, tudíž není relací ekvivalence.
9. Mějme množinu \( I = \{1, 2, 3, 4\} \) a relaci \( Z = \{(1,1), (2,2), (3,3), (4,4), (1,2), (2,3), (3,4), (1,3), (2,4), (1,4)\} \). Je relace \( Z \) částečným uspořádáním?
Řešení příkladu 9:
Relace musí být reflexivní, antisymetrická a tranzitivní.
Reflexivita: Jsou všechny \( (a,a) \), reflexivita platí.
Antisymetrie: V relaci nejsou žádné páry \( (a,b) \) a \( (b,a) \) s \( a \neq b \), antisymetrie platí.
Tranzitivita: Zkontrolujeme, zda platí, že pokud \( (a,b) \) a \( (b,c) \) jsou v relaci, pak i \( (a,c) \) je v relaci.
Z \( (1,2) \) a \( (2,3) \) je \( (1,3) \) v relaci.
Z \( (2,3) \) a \( (3,4) \) je \( (2,4) \) v relaci.
Z \( (1,3) \) a \( (3,4) \) je \( (1,4) \) v relaci.
Tranzitivita platí, takže relace je částečným uspořádáním.
10. Na množině \( J = \{x,y,z\} \) je relace \( Q = \{(x,x),(y,y),(z,z),(x,y),(y,z),(x,z)\} \). Je \( Q \) částečné uspořádání?
Řešení příkladu 10:
Reflexivita: Obsahuje všechny \( (a,a) \), reflexivita platí.
Antisymetrie: Neexistují dvojice \( (a,b) \) a \( (b,a) \) s \( a \neq b \), antisymetrie platí.
Tranzitivita: Z \( (x,y) \) a \( (y,z) \) plyne \( (x,z) \), které je v relaci.
Relace je tedy částečné uspořádání.
11. Nechť \( A = \{1,2,3,4,6\} \) a definujme relaci \( R \subseteq A \times A \) tak, že \((x,y) \in R\) právě když \(x\) dělí \(y\) (tj. \(x \mid y\)). Určete, zda je \(R\) částečným uspořádáním a zdůvodněte.
Řešení příkladu 11:
Reflexivita: Každé číslo dělí samo sebe, tedy \(\forall x \in A: x \mid x\). Reflexivita platí.
Antisymetrie: Pokud \(x \mid y\) a \(y \mid x\), pak \(x = y\) (protože dělitelství v přirozených číslech je antisymetrické). Tedy antisymetrie platí.
Tranzitivita: Pokud \(x \mid y\) a \(y \mid z\), pak \(x \mid z\). Tedy tranzitivita platí.
Závěr: Relace \(R\) je reflexivní, antisymetrická a tranzitivní, tedy je částečným uspořádáním na množině \(A\).
12. Mějme množinu \( B = \{a,b,c\} \) a relaci \( S = \{(a,a),(b,b),(c,c),(a,b),(b,a)\} \). Je \(S\) relací ekvivalence? Pokud ano, určete ekvivalenční třídy.
Řešení příkladu 12:
Reflexivita: \(S\) obsahuje všechny \( (x,x) \) pro \(x \in B\), tedy reflexivita platí.
Symetrie: Relace obsahuje \((a,b)\) a \((b,a)\), symetrie tedy platí.
Tranzitivita: Je potřeba ověřit všechny trojice. Například z \((a,b)\) a \((b,a)\) by mělo plynout \((a,a)\), což je pravda. Dále \((a,b)\) a \((b,b)\) \(\Rightarrow (a,b)\) je v relaci, platí. Žádná další dvojice neporušuje tranzitivitu.
Závěr: Relace \(S\) je reflexivní, symetrická i tranzitivní, tedy je relací ekvivalence.
Ekvivalenční třídy jsou: \(\{a,b\}\) a \(\{c\}\).
13. Na množině \( C = \{1,2,3,4\} \) je relace \( T = \{(1,1),(2,2),(3,3),(4,4),(1,2),(2,3),(3,4)\} \). Je tato relace částečným uspořádáním?
Řešení příkladu 13:
Reflexivita: Obsahuje všechny \( (x,x) \) pro \(x \in C\), reflexivita platí.
Antisymetrie: Neexistují žádné dvojice \((a,b)\) a \((b,a)\) s \(a \neq b\), antisymetrie tedy platí.
Tranzitivita: Z \((1,2)\) a \((2,3)\) plyne \((1,3)\), ale \((1,3)\) není v relaci, relace není tranzitivní.
Závěr: Relace není tranzitivní, tedy není částečným uspořádáním.
14. Na množině \( D = \{a,b,c,d\} \) definujeme relaci \( U = \{(a,a),(b,b),(c,c),(d,d),(a,b),(b,c),(a,c)\} \). Je relace \(U\) tranzitivní? Určete, zda je to částečné uspořádání.
Řešení příkladu 14:
Reflexivita: Obsahuje všechny \((x,x)\), reflexivita platí.
Antisymetrie: Nejsou žádné protichůdné dvojice, antisymetrie platí.
Tranzitivita: Máme \((a,b)\) a \((b,c)\), tudíž by mělo být \((a,c)\), což je splněno. Žádná další kombinace nesporná.
Závěr: Relace je reflexivní, antisymetrická a tranzitivní, tedy je částečným uspořádáním.
15. Na množině \( E = \{1,2,3\} \) definujeme relaci \( V = \{(1,1),(2,2),(3,3),(1,2),(2,1),(2,3),(3,2)\} \). Je tato relace relací ekvivalence?
Řešení příkladu 15:
Reflexivita: Obsahuje všechny \((x,x)\), reflexivita platí.
Symetrie: Pro všechny \((x,y)\) je i \((y,x)\), symetrie platí.
Tranzitivita: Z \((1,2)\) a \((2,3)\) plyne \((1,3)\), ale \((1,3)\) v relaci není. Relace není tranzitivní.
Závěr: Relace není tranzitivní, tedy není relací ekvivalence.
16. Mějme množinu \( F = \{a,b,c,d\} \) a relaci \( W = \{(a,a),(b,b),(c,c),(d,d),(a,b),(b,c),(a,c),(c,d),(a,d)\} \). Je tato relace částečným uspořádáním?
Řešení příkladu 16:
Reflexivita: Obsahuje všechny \((x,x)\), reflexivita platí.
Antisymetrie: Neexistují protichůdné dvojice \((x,y)\) a \((y,x)\) pro \(x \neq y\), antisymetrie platí.
Tranzitivita: Z \((a,b)\) a \((b,c)\) plyne \((a,c)\), které je v relaci, dále z \((a,c)\) a \((c,d)\) plyne \((a,d)\), které je rovněž v relaci. Relace je tranzitivní.
Závěr: Relace je reflexivní, antisymetrická a tranzitivní, tedy je částečným uspořádáním.
17. Na množině \( G = \{1,2,3,4\} \) definujeme relaci \( X = \{(1,1),(2,2),(3,3),(4,4),(1,2),(2,3),(3,4),(1,3)\} \). Určete, zda je tato relace tranzitivní a jestli je částečným uspořádáním.
Řešení příkladu 17:
Reflexivita: Obsahuje všechny \((x,x)\), reflexivita platí.
Antisymetrie: Neexistují dvojice \((a,b)\) a \((b,a)\) pro \(a \neq b\), antisymetrie platí.
Tranzitivita: Z \((1,2)\) a \((2,3)\) plyne \((1,3)\), které je v relaci, dále z \((2,3)\) a \((3,4)\) by mělo plynout \((2,4)\), ale \((2,4)\) v relaci není, relace není tranzitivní.
Závěr: Relace není tranzitivní, tedy není částečným uspořádáním.
18. Na množině \( H = \{x,y,z\} \) definujeme relaci \( Y = \{(x,x),(y,y),(z,z),(x,y),(y,x),(y,z),(z,y),(x,z),(z,x)\} \). Je tato relace ekvivalencí?
Řešení příkladu 18:
Reflexivita: Obsahuje všechny \((a,a)\), reflexivita platí.
Symetrie: Pro každé \((a,b)\) je i \((b,a)\), symetrie platí.
Tranzitivita: Například z \((x,y)\) a \((y,z)\) plyne \((x,z)\), které je v relaci. Podobně pro ostatní kombinace.
Závěr: Relace je reflexivní, symetrická a tranzitivní, tedy je relací ekvivalence.
Ekvivalenční třída je celá množina \(H\).
19. Mějme množinu \( I = \{1,2,3,4\} \) a relaci \( Z = \{(1,1),(2,2),(3,3),(4,4),(1,3),(3,4),(1,4)\} \). Je tato relace částečným uspořádáním?
Řešení příkladu 19:
Reflexivita: Obsahuje všechny \((x,x)\), reflexivita platí.
Antisymetrie: Žádné \((a,b)\) a \((b,a)\) pro \(a \neq b\), antisymetrie platí.
Tranzitivita: Z \((1,3)\) a \((3,4)\) plyne \((1,4)\), které je v relaci. Žádná další kombinace neporušuje tranzitivitu.
Závěr: Relace je reflexivní, antisymetrická a tranzitivní, tedy je částečným uspořádáním.
20. Na množině \( J = \{a,b,c,d\} \) definujme relaci \( Q = \{(a,a),(b,b),(c,c),(d,d),(a,b),(b,c),(c,d),(a,c),(b,d),(a,d)\} \). Je tato relace totálním uspořádáním?
Řešení příkladu 20:
Reflexivita: Obsahuje všechny \((x,x)\), reflexivita platí.
Antisymetrie: Neexistují protichůdné dvojice \((x,y)\) a \((y,x)\) s \(x \neq y\), antisymetrie platí.
Tranzitivita: Z \((a,b)\) a \((b,c)\) plyne \((a,c)\), které je v relaci, dále z \((b,c)\) a \((c,d)\) plyne \((b,d)\), které je v relaci, a také \((a,c)\) a \((c,d)\) \(\Rightarrow (a,d)\), které je v relaci. Tranzitivita platí.
Kompletnost: Pro každé dva prvky \(x,y\) z množiny je buď \((x,y)\) nebo \((y,x)\) v relaci. Například mezi \(a\) a \(b\) je \((a,b)\), mezi \(b\) a \(a\) není, ale to stačí.
Závěr: Relace je reflexivní, antisymetrická, tranzitivní a totální, tedy je totálním uspořádáním.
21. Na množině \( M = \{1,2,3,4\} \) je definována relace \( R = \{(1,1),(2,2),(3,3),(4,4),(1,2),(2,3),(3,4),(1,3)\} \). Je \( R \) částečné uspořádání?
Řešení příkladu 21:
Reflexivita: Všechny prvky \( (a,a) \) pro \( a \in M \) jsou v \( R \), tedy \( (1,1), (2,2), (3,3), (4,4) \in R \). Reflexivita platí.
Antisymetrie: Zkontrolujeme, zda existuje \( (a,b) \in R \) a zároveň \( (b,a) \in R \) s \( a \neq b \). Můžeme vidět, že například \( (1,2) \in R \), ale \( (2,1) \notin R \). Podobně pro další dvojice. Žádná taková opačná dvojice neexistuje, antisymetrie platí.
Tranzitivita: Ověříme, zda z \( (a,b) \in R \) a \( (b,c) \in R \) plyne \( (a,c) \in R \). Například \( (1,2) \in R \) a \( (2,3) \in R \) \(\Rightarrow\) \( (1,3) \in R \), což platí. Dále \( (2,3) \in R \) a \( (3,4) \in R \) \(\Rightarrow\) \( (2,4) \) musí být v \( R \), ale není, tedy tranzitivita neplatí.
Relace \( R \) není částečné uspořádání, protože není tranzitivní.
22. Na množině \( A = \{a,b,c,d\} \) je relace \( S = \{(a,a),(b,b),(c,c),(d,d),(a,b),(b,a),(b,c),(c,b)\} \). Je \( S \) relací ekvivalence?
Řešení příkladu 22:
Reflexivita: Relace obsahuje všechny \( (x,x) \) pro \( x \in A \), tedy reflexivita platí.
Symetrie: Z \( (a,b) \in S \) plyne \( (b,a) \in S \), stejně \( (b,c) \in S \) a \( (c,b) \in S \), symetrie platí.
Tranzitivita: Zkontrolujeme, zda z \( (a,b) \in S \) a \( (b,c) \in S \) plyne \( (a,c) \in S \). \( (a,b) \in S \) a \( (b,c) \in S \) \(\Rightarrow\) \( (a,c) \) musí být v \( S \), ale není, tedy tranzitivita neplatí.
Relace \( S \) není relací ekvivalence, protože není tranzitivní.
23. Na množině \( B = \{1,2,3,4\} \) je relace \( T = \{(1,1),(2,2),(3,3),(4,4),(1,3),(3,1),(2,4),(4,2)\} \). Je \( T \) relací ekvivalence?
Řešení příkladu 23:
Reflexivita: Relace obsahuje všechny \( (a,a) \) pro \( a \in B \), reflexivita platí.
Symetrie: Pokud je \( (1,3) \in T \), pak \( (3,1) \in T \), a pokud je \( (2,4) \in T \), pak \( (4,2) \in T \), symetrie platí.
Tranzitivita: Zkontrolujeme, zda z \( (1,3) \in T \) a \( (3,1) \in T \) plyne \( (1,1) \in T \), což platí. Podobně z \( (2,4) \in T \) a \( (4,2) \in T \) plyne \( (2,2) \in T \). Nicméně, z \( (1,3) \in T \) a \( (3,1) \in T \) nelze vyvodit \( (1,3) \) jinak, což je v relaci, ale z \( (1,3) \) a \( (3,4) \) (které není v relaci) nelze usuzovat. Protože neexistují žádné další kombinace, tranzitivita platí.
Relace \( T \) je relací ekvivalence.
24. Na množině \( X = \{x,y,z\} \) je relace \( U = \{(x,x),(y,y),(z,z),(x,y),(y,z),(z,x)\} \). Je \( U \) relací ekvivalence?
Řešení příkladu 24:
Reflexivita: Obsahuje všechny \( (a,a) \) pro \( a \in X \), reflexivita platí.
Symetrie: Například \( (x,y) \in U \), ale \( (y,x) \notin U \), symetrie neplatí.
Tranzitivita: Ze \( (x,y) \in U \) a \( (y,z) \in U \) plyne \( (x,z) \in U \), což platí.
Relace \( U \) není relací ekvivalence, protože není symetrická.
25. Na množině \( Y = \{1,2,3,4,5\} \) je relace \( V = \{(a,b) \mid a \leq b\} \). Je \( V \) částečným uspořádáním?
Řešení příkladu 25:
Reflexivita: Pro každé \( a \in Y \) platí \( a \leq a \), tedy \( (a,a) \in V \), reflexivita platí.
Antisymetrie: Pokud \( a \leq b \) a zároveň \( b \leq a \), pak \( a = b \), antisymetrie platí.
Tranzitivita: Pokud \( a \leq b \) a \( b \leq c \), pak \( a \leq c \), tranzitivita platí.
Relace \( V \) je tedy částečné uspořádání.
26. Na množině \( Z = \{p,q,r,s\} \) je relace \( W = \{(p,p),(q,q),(r,r),(s,s),(p,q),(q,r),(p,r)\} \). Je \( W \) částečné uspořádání?
Řešení příkladu 26:
Reflexivita: Obsahuje všechny \( (a,a) \) pro \( a \in Z \), reflexivita platí.
Antisymetrie: Neexistuje \( (a,b) \) a zároveň \( (b,a) \) s \( a \neq b \), antisymetrie platí.
Tranzitivita: Z \( (p,q) \in W \) a \( (q,r) \in W \) plyne \( (p,r) \in W \), což je pravda. Žádná další kombinace neporušuje tranzitivitu.
Relace \( W \) je částečné uspořádání.
27. Na množině \( P = \{1,2,3\} \) je relace \( Q = \{(1,1),(2,2),(3,3),(1,2),(2,1),(2,3),(3,2)\} \). Je \( Q \) relací ekvivalence?
Řešení příkladu 27:
Reflexivita: Obsahuje všechny \( (a,a) \), reflexivita platí.
Symetrie: Pokud \( (1,2) \in Q \), pak \( (2,1) \in Q \), a pokud \( (2,3) \in Q \), pak \( (3,2) \in Q \), symetrie platí.
Tranzitivita: Z \( (1,2) \in Q \) a \( (2,3) \in Q \) by mělo plynnout \( (1,3) \in Q \), ale \( (1,3) \notin Q \), tedy tranzitivita neplatí.
Relace \( Q \) není relací ekvivalence.
28. Na množině \( R = \{a,b,c\} \) je relace \( S = \{(a,a),(b,b),(c,c),(a,b),(b,c),(a,c)\} \). Je \( S \) částečné uspořádání?
Řešení příkladu 28:
Reflexivita: Obsahuje všechny \( (x,x) \) pro \( x \in R \), reflexivita platí.
Antisymetrie: Žádná dvojice \( (a,b) \) a \( (b,a) \) s \( a \neq b \) neexistuje, antisymetrie platí.
Tranzitivita: Z \( (a,b) \in S \) a \( (b,c) \in S \) plyne \( (a,c) \in S \), což je v relaci, tranzitivita platí.
Relace \( S \) je částečné uspořádání.
29. Na množině \( T = \{1,2,3,4\} \) je relace \( U = \{(1,1),(2,2),(3,3),(4,4),(1,2),(2,1),(2,3),(3,2)\} \). Je \( U \) relací ekvivalence?
Řešení příkladu 29:
Reflexivita: Obsahuje všechny \( (a,a) \), reflexivita platí.
Symetrie: Například \( (1,2) \in U \) a \( (2,1) \in U \), stejně \( (2,3) \in U \) a \( (3,2) \in U \), symetrie platí.
Tranzitivita: Z \( (1,2) \in U \) a \( (2,3) \in U \) by mělo plynnout \( (1,3) \in U \), ale \( (1,3) \notin U \), tedy tranzitivita neplatí.
Relace \( U \) není relací ekvivalence.
30. Na množině \( V = \{a,b,c,d\} \) je relace \( W = \{(a,a),(b,b),(c,c),(d,d),(a,b),(b,c),(a,c),(c,d),(a,d)\} \). Je \( W \) částečné uspořádání?
Řešení příkladu 30:
Reflexivita: Obsahuje všechny \( (x,x) \) pro \( x \in V \), reflexivita platí.
Antisymetrie: Žádná opačná dvojice s různými prvky není v relaci, antisymetrie platí.
Tranzitivita: Z \( (a,b) \in W \) a \( (b,c) \in W \) plyne \( (a,c) \in W \), což je pravda. Z \( (c,d) \in W \) a \( (a,c) \in W \) plyne \( (a,d) \in W \), což je také pravda. Žádná tranzitivní podmínka není porušena.
Relace \( W \) je částečné uspořádání.
31. Na množině \( M = \{1,2,3,4\} \) je relace \( R = \{(1,1),(2,2),(3,3),(4,4),(1,2),(2,3),(1,3),(3,4)\} \). Je \( R \) částečné uspořádání?
Řešení příkladu 31:
Reflexivita: Obsahuje všechny \( (a,a) \) pro \( a \in M \), tedy reflexivita platí.
Antisymetrie: Zkontrolujeme všechny dvojice \( (a,b) \) a \( (b,a) \) s \( a \neq b \). Například \( (1,2) \in R \) ale \( (2,1) \notin R \), podobně pro další. Žádná dvojice neporušuje antisymetrii, tedy antisymetrie platí.
Tranzitivita: Z \( (1,2) \) a \( (2,3) \) plyne \( (1,3) \), které je v relaci; z \( (2,3) \) a \( (3,4) \) plyne \( (2,4) \), ale \( (2,4) \notin R \), což porušuje tranzitivitu.
Protože tranzitivita neplatí, relace není částečné uspořádání.
32. Na množině \( A = \{a,b,c\} \) je relace \( S = \{(a,a),(b,b),(c,c),(a,b),(b,a)\} \). Je relace \( S \) relací ekvivalence?
Řešení příkladu 32:
Reflexivita: Obsahuje všechny \( (x,x) \), tedy reflexivita platí.
Symetrie: Pokud je \( (a,b) \in S \), pak je i \( (b,a) \in S \) (viz \( (a,b) \) a \( (b,a) \)), symetrie platí.
Tranzitivita: Zvažme \( (a,b) \in S \) a \( (b,a) \in S \), podle tranzitivity by mělo být \( (a,a) \in S \), což platí. Zkusme \( (a,b) \) a \( (b,b) \), pak \( (a,b) \in S \). Je potřeba zkontrolovat všechny trojice; například \( (a,b) \) a \( (b,a) \Rightarrow (a,a) \) v \( S \), což platí. Není ale v relaci \( (b,c) \) ani \( (c,b) \), proto z hlediska \( c \) není tranzitivita porušena.
Protože chybí dvojice \( (a,c) \), \( (c,a) \) a podobně, relace není úplná, ale tranzitivita není porušena.
Relace splňuje reflexivitu, symetrii i tranzitivitu, tedy je relací ekvivalence.
33. Na množině \( X = \{1,2,3\} \) je relace \( T = \{(1,1),(2,2),(3,3),(1,2),(2,3),(3,1)\} \). Je relace \( T \) ekvivalencí?
Řešení příkladu 33:
Reflexivita: Obsahuje všechny \( (a,a) \), tedy reflexivita platí.
Symetrie: Například \( (1,2) \in T \), ale \( (2,1) \notin T \), symetrie neplatí.
Tranzitivita: Zvažme \( (1,2) \) a \( (2,3) \Rightarrow (1,3) \), ale \( (1,3) \notin T \), tranzitivita neplatí.
Proto relace \( T \) není relací ekvivalence.
34. Na množině \( B = \{x,y,z,w\} \) je relace \( U = \{(x,x),(y,y),(z,z),(w,w),(x,y),(y,z),(x,z),(z,w),(x,w)\} \). Je \( U \) částečné uspořádání?
Řešení příkladu 34:
Reflexivita: Obsahuje všechny \( (a,a) \), reflexivita platí.
Antisymetrie: Neexistuje \( (a,b) \) a \( (b,a) \) s \( a \neq b \), tedy antisymetrie platí.
Tranzitivita: Z \( (x,y) \) a \( (y,z) \) plyne \( (x,z) \) v relaci, z \( (z,w) \) a \( (x,z) \) plyne \( (x,w) \), které je v relaci, tranzitivita platí.
Relace je částečné uspořádání.
35. Na množině \( C = \{1,2,3,4\} \) je relace \( V = \{(1,1),(2,2),(3,3),(4,4),(1,2),(2,1),(2,3),(3,4),(4,2)\} \). Je \( V \) relací ekvivalence?
Řešení příkladu 35:
Reflexivita: Obsahuje všechny \( (a,a) \), reflexivita platí.
Symetrie: \( (1,2) \in V \) a \( (2,1) \in V \), \( (2,3) \in V \), ale \( (3,2) \notin V \), symetrie neplatí.
Tranzitivita: Například z \( (2,3) \) a \( (3,4) \) by mělo být \( (2,4) \), ale \( (2,4) \notin V \), tranzitivita neplatí.
Relace \( V \) není relací ekvivalence.
36. Na množině \( D = \{a,b,c\} \) je relace \( W = \{(a,a),(b,b),(c,c),(a,b),(b,c),(a,c),(c,a)\} \). Je \( W \) částečné uspořádání?
Řešení příkladu 36:
Reflexivita: Obsahuje všechny \( (x,x) \), reflexivita platí.
Antisymetrie: Z \( (a,c) \in W \) a \( (c,a) \in W \) s \( a \neq c \) plyne porušení antisymetrie, protože antisymetrie požaduje, že pokud \( (a,b) \) a \( (b,a) \) jsou v relaci, pak \( a = b \), což není splněno.
Relace není částečné uspořádání.
37. Na množině \( E = \{1,2,3,4\} \) je relace \( Z = \{(1,1),(2,2),(3,3),(4,4),(1,2),(2,3),(3,4),(1,4)\} \). Je \( Z \) částečné uspořádání?
Řešení příkladu 37:
Reflexivita: Obsahuje všechny \( (a,a) \), reflexivita platí.
Antisymetrie: Neexistují \( (a,b) \) a \( (b,a) \) s \( a \neq b \), antisymetrie platí.
Tranzitivita: Z \( (1,2) \) a \( (2,3) \Rightarrow (1,3) \) ale \( (1,3) \notin Z \), tranzitivita neplatí.
Relace není částečné uspořádání.
38. Na množině \( F = \{x,y,z\} \) je relace \( Q = \{(x,x),(y,y),(z,z),(x,y),(y,x),(y,z),(z,y)\} \). Je \( Q \) relací ekvivalence?
Řešení příkladu 38:
Reflexivita: Obsahuje všechny \( (a,a) \), reflexivita platí.
Symetrie: Pokud je \( (a,b) \in Q \), pak \( (b,a) \in Q \), například \( (x,y) \) a \( (y,x) \), symetrie platí.
Tranzitivita: Z \( (x,y) \) a \( (y,z) \Rightarrow (x,z) \), ale \( (x,z) \notin Q \), tranzitivita neplatí.
Relace není ekvivalencí.
39. Na množině \( G = \{1,2,3\} \) je relace \( M = \{(1,1),(2,2),(3,3),(1,2),(2,3),(1,3)\} \). Je \( M \) částečné uspořádání?
Řešení příkladu 39:
Reflexivita: Obsahuje všechny \( (a,a) \), reflexivita platí.
Antisymetrie: Žádné \( (a,b) \) a \( (b,a) \) s \( a \neq b \) v relaci není, antisymetrie platí.
Tranzitivita: Z \( (1,2) \) a \( (2,3) \Rightarrow (1,3) \), které je v relaci, tranzitivita platí.
Relace je částečné uspořádání.
40. Na množině \( H = \{a,b,c,d\} \) je relace \( N = \{(a,a),(b,b),(c,c),(d,d),(a,b),(b,a),(c,d),(d,c)\} \). Je \( N \) relací ekvivalence?
Řešení příkladu 40:
Reflexivita: Obsahuje všechny \( (x,x) \), reflexivita platí.
Symetrie: \( (a,b) \in N \) a \( (b,a) \in N \), \( (c,d) \in N \) a \( (d,c) \in N \), symetrie platí.
Tranzitivita: Zvažme \( (a,b) \) a \( (b,a) \Rightarrow (a,a) \in N \), platí. Z \( (a,b) \) a \( (b,c) \) ale \( (b,c) \notin N \), tranzitivita není porušena. Mezi třídami \( \{a,b\} \) a \( \{c,d\} \) žádné jiné vztahy nejsou.
Relace je relací ekvivalence, protože definuje dvě ekvivalenční třídy \( \{a,b\} \) a \( \{c,d\} \).
41. Na množině \( P = \{a,b,c,d\} \) je relace \( R = \{(a,a),(b,b),(c,c),(d,d),(a,b),(b,c),(a,c),(c,d)\} \). Je relace \( R \) částečné uspořádání?
Řešení příkladu 41:
Pro ověření, zda je relace \( R \) částečným uspořádáním, musíme zkontrolovat tři vlastnosti: reflexivitu, antisymetrii a tranzitivitu.
Reflexivita znamená, že pro každý prvek \( x \in P \) musí platit \( (x,x) \in R \). V našem případě jsou všechny takové prvky v relaci: \( (a,a), (b,b), (c,c), (d,d) \in R \). Reflexivita tedy platí.
Antisymetrie vyžaduje, že pokud \( (x,y) \in R \) a zároveň \( (y,x) \in R \), pak \( x = y \). Prozkoumejme všechny prvky mimo reflexivní:
\( (a,b) \in R \) a \( (b,a) \notin R \), \( (b,c) \in R \) a \( (c,b) \notin R \), \( (a,c) \in R \) a \( (c,a) \notin R \), \( (c,d) \in R \) a \( (d,c) \notin R \). Nenašli jsme žádný pár, který by porušoval antisymetrii, takže antisymetrie platí.
Tranzitivita vyžaduje, že pokud \( (x,y) \in R \) a \( (y,z) \in R \), pak musí být také \( (x,z) \in R \). Prozkoumejme všechny dvojice:
Z \( (a,b) \) a \( (b,c) \) plyne \( (a,c) \), což v relaci máme.
Z \( (b,c) \) a \( (c,d) \) plyne \( (b,d) \), ale \( (b,d) \notin R \). To znamená, že relace není tranzitivní.
Protože tranzitivita není splněna, relace \( R \) není částečným uspořádáním.
42. Na množině \( S = \{1,2,3\} \) je relace \( Q = \{(1,1),(2,2),(3,3),(1,2),(2,1),(2,3),(3,2)\} \). Je \( Q \) relací ekvivalence?
Řešení příkladu 42:
Relace je ekvivalence, pokud je reflexivní, symetrická a tranzitivní.
Reflexivita: Všechny prvky jsou v relaci sami se sebou, což platí, protože máme \( (1,1), (2,2), (3,3) \in Q \).
Symetrie: Pro každé \( (x,y) \in Q \) musí být i \( (y,x) \in Q \). Zkontrolujeme:
\( (1,2) \in Q \) a \( (2,1) \in Q \), \( (2,3) \in Q \) a \( (3,2) \in Q \). Symetrie tedy platí.
Tranzitivita: Pro všechny \( (x,y) \) a \( (y,z) \) musí platit \( (x,z) \in Q \). Zkontrolujeme možné případy:
Z \( (1,2) \) a \( (2,1) \) plyne \( (1,1) \), což platí.
Z \( (2,3) \) a \( (3,2) \) plyne \( (2,2) \), což také platí.
Z \( (1,2) \) a \( (2,3) \) plyne \( (1,3) \), ale \( (1,3) \notin Q \). To porušuje tranzitivitu.
Proto relace \( Q \) není relací ekvivalence.
43. Na množině \( M = \{x,y,z\} \) je relace \( T = \{(x,x),(y,y),(z,z),(x,y),(y,z),(x,z)\} \). Je \( T \) částečným uspořádáním a jaké jsou její maximální prvky?
Řešení příkladu 43:
Pro ověření částečného uspořádání zkontrolujeme reflexivitu, antisymetrii a tranzitivitu:
Reflexivita: Všechny prvky jsou v relaci sami se sebou, což platí.
Antisymetrie: Neexistují páry \( (a,b) \) a \( (b,a) \) pro \( a \neq b \), takže antisymetrie platí.
Tranzitivita: \( (x,y) \) a \( (y,z) \Rightarrow (x,z) \), které je v relaci. Žádné jiné kombinace tranzitivitu neporušují.
Relace je tedy částečným uspořádáním.
Maximální prvky jsou ty, pro které neexistuje žádný prvek větší podle relace. Z množiny zjistíme, že \( z \) není v relaci s žádným větším prvkem, tedy \( z \) je maximální prvek.
44. Na množině \( A = \{1,2,3,4\} \) je relace \( R = \{(1,1),(2,2),(3,3),(4,4),(1,2),(2,4),(1,4)\} \). Určete, zda je \( R \) částečným uspořádáním a najděte minimální prvky.
Řešení příkladu 44:
Zkontrolujeme vlastnosti částečného uspořádání:
Reflexivita: Obsahuje \( (a,a) \) pro všechny \( a \in A \), takže reflexivita platí.
Antisymetrie: Žádný pár \( (a,b) \) a \( (b,a) \) pro \( a \neq b \) není v relaci, antisymetrie tedy platí.
Tranzitivita: Z \( (1,2) \) a \( (2,4) \) plyne \( (1,4) \), které je v relaci, tranzitivita platí.
Žádné jiné kombinace nejsou, takže relace je tranzitivní.
Relace \( R \) je tedy částečné uspořádání.
Minimální prvek je takový, který není větší než žádný jiný prvek. Z množiny \( A \) zjistíme, že \( 1 \) není větší než žádný prvek, protože žádný \( (x,1) \) není v relaci s \( x \neq 1 \).
Takže minimální prvek je \( 1 \).
45. Na množině \( X = \{p,q,r\} \) je relace \( S = \{(p,p),(q,q),(r,r),(p,q),(q,r),(r,p)\} \). Určete, zda je relace \( S \) relací ekvivalence nebo částečným uspořádáním.
Řešení příkladu 45:
Zkontrolujeme, zda relace \( S \) je relací ekvivalence:
Reflexivita: \( (p,p), (q,q), (r,r) \in S \), reflexivita tedy platí.
Symetrie: Pro každý pár musí platit, že pokud \( (x,y) \in S \), pak i \( (y,x) \in S \). Zkontrolujeme:
\( (p,q) \in S \), ale \( (q,p) \notin S \), takže symetrie neplatí.
Relace tedy není ekvivalence.
Zkontrolujeme, zda je částečným uspořádáním:
Reflexivita platí.
Antisymetrie: Musíme zkontrolovat, zda existují \( (x,y) \) a \( (y,x) \) s \( x \neq y \).
Z \( (p,q) \in S \) a \( (q,p) \notin S \), OK.
Z \( (q,r) \in S \) a \( (r,q) \notin S \), OK.
Z \( (r,p) \in S \) a \( (p,r) \notin S \), OK.
Antisymetrie tedy platí.
Tranzitivita: Zkusíme \( (p,q) \) a \( (q,r) \), podle tranzitivity musí být \( (p,r) \in S \), ale \( (p,r) \notin S \).
Tranzitivita neplatí, relace tedy není částečné uspořádání.
Relace \( S \) není ani relací ekvivalence, ani částečným uspořádáním.
46. Na množině \( U = \{1,2,3,4\} \) je relace \( R = \{(1,1),(2,2),(3,3),(4,4),(1,2),(2,3),(3,4),(1,3),(2,4)\} \). Je \( R \) částečným uspořádáním?
Řešení příkladu 46:
Nejprve ověříme reflexivitu. Pro každé \( x \in U \) musí platit \( (x,x) \in R \). V množině jsou všechny prvky reflexivní, takže reflexivita platí.
Dále ověříme antisymetrii. Pokud pro nějaké \( x,y \in U \) platí \( (x,y) \in R \) a \( (y,x) \in R \), pak musí být \( x = y \). Prozkoumáme všechny páry mimo reflexivní:
\( (1,2) \in R \), ale \( (2,1) \notin R \); \( (2,3) \in R \), ale \( (3,2) \notin R \); \( (3,4) \in R \), ale \( (4,3) \notin R \); \( (1,3) \in R \), ale \( (3,1) \notin R \); \( (2,4) \in R \), ale \( (4,2) \notin R \). Žádná porušení antisymetrie nenalezená, antisymetrie platí.
Kontrolujeme tranzitivitu. Pro všechny \( x,y,z \) platí, pokud \( (x,y) \in R \) a \( (y,z) \in R \), pak musí být \( (x,z) \in R \):
Z \( (1,2) \) a \( (2,3) \) plyne \( (1,3) \), které je v relaci.
Z \( (2,3) \) a \( (3,4) \) plyne \( (2,4) \), které je v relaci.
Z \( (1,3) \) a \( (3,4) \) plyne \( (1,4) \), ale \( (1,4) \notin R \), což znamená, že relace není tranzitivní.
Protože tranzitivita není splněna, relace \( R \) není částečným uspořádáním.
47. Na množině \( V = \{a,b,c\} \) je relace \( S = \{(a,a),(b,b),(c,c),(a,b),(b,a),(b,c),(c,b),(a,c),(c,a)\} \). Je relace \( S \) relací ekvivalence?
Řešení příkladu 47:
Relace je ekvivalencí, pokud je reflexivní, symetrická a tranzitivní.
Reflexivita: Všechny prvky jsou ve vztahu se sebou samými: \( (a,a),(b,b),(c,c) \in S \), reflexivita platí.
Symetrie: Pro každý prvek platí, že pokud \( (x,y) \in S \), pak i \( (y,x) \in S \). V relaci jsou všechny dvojice vzájemně obrácené, takže symetrie platí.
Tranzitivita: Ověříme všechny možné kombinace:
Z \( (a,b) \) a \( (b,c) \) plyne \( (a,c) \), které je v relaci.
Z \( (b,a) \) a \( (a,c) \) plyne \( (b,c) \), které je v relaci.
Další možné kombinace také platí, jelikož všechny kombinace jsou v relaci.
Relace je tranzitivní.
Relace \( S \) je tedy relací ekvivalence.
48. Na množině \( W = \{1,2,3,4\} \) je relace \( T = \{(1,1),(2,2),(3,3),(4,4),(1,2),(2,3),(3,4),(1,3),(2,4),(1,4)\} \). Je relace \( T \) částečným uspořádáním? Pokud ano, určete minimální a maximální prvky.
Řešení příkladu 48:
Nejprve ověříme reflexivitu. Všechny prvky mají reflexivní vztahy, tedy reflexivita platí.
Antisymetrie: Prozkoumáme ne-reflexivní prvky relace. Všechny orientované páry jsou pouze jednosměrné, například \( (1,2) \in T \), ale \( (2,1) \notin T \), a podobně pro ostatní páry, proto antisymetrie platí.
Tranzitivita: Zkontrolujeme:
Z \( (1,2) \) a \( (2,3) \) plyne \( (1,3) \), které je v relaci.
Z \( (2,3) \) a \( (3,4) \) plyne \( (2,4) \), které je v relaci.
Z \( (1,3) \) a \( (3,4) \) plyne \( (1,4) \), které je v relaci.
Nejsou žádné porušení tranzitivity, takže tranzitivita platí.
Relace \( T \) je tedy částečným uspořádáním.
Minimální prvek je ten, který není větší než žádný jiný prvek podle relace. Z množiny zjistíme, že \( 1 \) není větší než žádný prvek, tedy minimální prvek je \( 1 \).
Maximální prvek je ten, který není menší než žádný jiný prvek podle relace. V tomto případě \( 4 \) není menší než žádný prvek, tedy maximální prvek je \( 4 \).
49. Na množině \( Y = \{x,y,z\} \) je relace \( U = \{(x,x),(y,y),(z,z),(x,y),(y,z),(z,x)\} \). Určete, zda je relace \( U \) relací ekvivalence, částečným uspořádáním, nebo jiným typem relace.
Řešení příkladu 49:
Reflexivita: Všechny prvky mají \( (a,a) \) v relaci, tedy reflexivita platí.
Symetrie: Například \( (x,y) \in U \), ale \( (y,x) \notin U \), proto symetrie neplatí.
Antisymetrie: Kontrolou zjistíme, že neexistuje žádný pár \( (a,b) \) a \( (b,a) \) s \( a \neq b \). Proto antisymetrie platí.
Tranzitivita: Z \( (x,y) \) a \( (y,z) \) by mělo plynout \( (x,z) \), ale \( (x,z) \notin U \). Tranzitivita neplatí.
Závěr: Relace \( U \) je reflexivní a antisymetrická, ale není tranzitivní ani symetrická. Není tedy relací ekvivalence ani částečným uspořádáním; jde o obecnou binární relaci obsahující orientovaný cyklus \(x \to y \to z \to x\).
50. Na množině \( Z = \{1,2,3,4\} \) je relace \( V = \{(1,1),(2,2),(3,3),(4,4),(1,2),(1,3),(2,4),(3,4)\} \). Určete, zda je relace \( V \) relací ekvivalence nebo částečným uspořádáním, a zdůvodněte.
Řešení příkladu 50:
Reflexivita: Pro všechny \( x \in Z \) platí \( (x,x) \in V \), reflexivita platí.
Symetrie: Pro zkontrolování symetrie hledáme, zda pokud \( (x,y) \in V \), pak \( (y,x) \in V \).
Například \( (1,2) \in V \), ale \( (2,1) \notin V \), tedy symetrie neplatí.
Relace není relací ekvivalence.
Antisymetrie: Zkontrolujeme všechny nesymetrické dvojice.
\( (1,2) \in V \), \( (2,1) \notin V \); \( (1,3) \in V \), \( (3,1) \notin V \); \( (2,4) \in V \), \( (4,2) \notin V \); \( (3,4) \in V \), \( (4,3) \notin V \). Antisymetrie platí.
Tranzitivita: Pro všechny \( x,y,z \) platí, že pokud \( (x,y) \in V \) a \( (y,z) \in V \), pak \( (x,z) \in V \):
Z \( (1,2) \) a \( (2,4) \) plyne \( (1,4) \), ale \( (1,4) \notin V \), tranzitivita neplatí.
Relace \( V \) není částečným uspořádáním.
51. Na množině \( M = \{1,2,3,4,5\} \) je relace \( R = \{(1,1),(2,2),(3,3),(4,4),(5,5),(1,2),(2,3),(3,4),(4,5),(1,3),(2,4),(3,5),(1,4),(2,5),(1,5)\} \). Určete, zda je relace \( R \) částečným uspořádáním. Pokud ano, určete minimální a maximální prvky.
Řešení příkladu 51:
Nejprve ověříme reflexivitu: pro každé \( x \in M \) musí platit \( (x,x) \in R \). V relaci jsou všechny reflexivní prvky \( (1,1), (2,2), (3,3), (4,4), (5,5) \), reflexivita tedy platí.
Dále zkontrolujeme antisymetrii. Antisymetrie říká, že pokud \( (x,y) \in R \) a \( (y,x) \in R \), pak \( x = y \). Podíváme se na nepravidelné páry mimo reflexivní:
Například \( (1,2) \in R \), ale \( (2,1) \notin R \); obdobně u všech ostatních „nerovných“ párů obrácený pár není v relaci. Proto antisymetrie platí.
Kontrola tranzitivity: Pokud \( (x,y) \in R \) a \( (y,z) \in R \), pak musí být \( (x,z) \in R \).
Zkontrolujeme několik důležitých případů:
Z \( (1,2) \) a \( (2,3) \) plyne \( (1,3) \in R \) – platí.
Z \( (2,3) \) a \( (3,4) \) plyne \( (2,4) \in R \) – platí.
Z \( (3,4) \) a \( (4,5) \) plyne \( (3,5) \in R \) – platí.
Z \( (1,3) \) a \( (3,5) \) plyne \( (1,5) \in R \) – platí.
Obecně relace obsahuje všechny potřebné složené prvky, tranzitivita tedy platí.
Relace \( R \) je reflexivní, antisymetrická a tranzitivní, tedy částečným uspořádáním.
Minimální prvek: Je to prvek, který není větší než žádný jiný. \( 1 \) není vpravo v žádném nepravidelném páru, je tedy minimální.
Maximální prvek: Je to prvek, který není menší než žádný jiný. \( 5 \) není vlevo v žádném nepravidelném páru, je tedy maximální.
52. Na množině \( A = \{a,b,c,d\} \) je relace \( S = \{(a,a),(b,b),(c,c),(d,d),(a,b),(b,a),(b,c),(c,b),(c,d),(d,c)\} \). Určete, zda je relace \( S \) relací ekvivalence nebo částečným uspořádáním.
Řešení příkladu 52:
Ověříme reflexivitu: všechny prvky \( a,b,c,d \) mají reflexivní dvojice v \( S \), takže reflexivita platí.
Zkontrolujeme symetrii: pro každý prvek platí, že pokud \( (x,y) \in S \), pak i \( (y,x) \in S \). Například \( (a,b) \in S \) a zároveň \( (b,a) \in S \), obdobně \( (b,c), (c,b) \) a \( (c,d), (d,c) \) jsou v relaci. Symetrie tedy platí.
Tranzitivita: Ověříme, zda pro všechna \( (x,y), (y,z) \in S \) platí \( (x,z) \in S \):
Z \( (a,b) \) a \( (b,c) \) by mělo plynout \( (a,c) \), ale \( (a,c) \notin S \), tranzitivita neplatí.
Relace tedy není relací ekvivalence.
Zkontrolujeme antisymetrii: vzhledem k symetrii a existenci \( (a,b) \) a \( (b,a) \) s \( a \neq b \) antisymetrie neplatí.
Relace není částečným uspořádáním.
53. Na množině \( P = \{x,y,z\} \) je relace \( T = \{(x,x),(y,y),(z,z),(x,y),(y,z),(x,z)\} \). Určete, zda je relace \( T \) částečným uspořádáním, a pokud ano, určete, zda existují maximální a minimální prvky.
Řešení příkladu 53:
Reflexivita: všechny prvky mají reflexivní dvojice, reflexivita platí.
Antisymetrie: zkontrolujeme, zda existují páry \( (a,b) \) a \( (b,a) \) s \( a \neq b \). Neexistují, antisymetrie tedy platí.
Tranzitivita: ověříme, zda pro \( (x,y) \in T \) a \( (y,z) \in T \) platí \( (x,z) \in T \). V relaci je \( (x,z) \in T \), tranzitivita tedy platí.
Relace \( T \) je částečným uspořádáním.
Minimální prvek je takový, který není větší než žádný jiný. \( x \) je minimální, protože neexistuje prvek \( w \) s \( (w,x) \in T \) a \( w \neq x \).
Maximální prvek je takový, který není menší než žádný jiný. \( z \) je maximální, protože neexistuje prvek \( w \) s \( (z,w) \in T \) a \( w \neq z \).
54. Na množině \( Q = \{1,2,3\} \) je relace \( U = \{(1,1),(2,2),(3,3),(1,2),(2,1),(2,3),(3,2)\} \). Určete, zda je relace \( U \) relací ekvivalence, částečným uspořádáním, nebo žádným z nich.
Řešení příkladu 54:
Reflexivita: Všechny prvky mají reflexivní dvojice, reflexivita platí.
Symetrie: \( (1,2) \in U \) a \( (2,1) \in U \), stejně tak \( (2,3) \in U \) a \( (3,2) \in U \), symetrie tedy platí.
Tranzitivita: Zkontrolujeme:
Z \( (1,2) \) a \( (2,3) \) plyne \( (1,3) \) by mělo být v relaci pro tranzitivitu, ale \( (1,3) \notin U \), tranzitivita tedy neplatí.
Relace není relací ekvivalence.
Antisymetrie: Z \( (1,2) \in U \) a \( (2,1) \in U \) s \( 1 \neq 2 \) plyne, že antisymetrie neplatí.
Relace není částečným uspořádáním.
55. Na množině \( R = \{a,b,c,d\} \) je relace \( W = \{(a,a),(b,b),(c,c),(d,d),(a,b),(b,c),(a,c),(c,d),(a,d)\} \). Určete, zda je relace \( W \) částečným uspořádáním, a pokud ano, určete, zda existují minimální a maximální prvky.
Řešení příkladu 55:
Reflexivita: všechny prvky mají reflexivní dvojice, reflexivita platí.
Antisymetrie: zkontrolujeme, zda existuje pár \( (x,y) \in W \) a \( (y,x) \in W \) s \( x \neq y \). Neexistuje, tedy antisymetrie platí.
Tranzitivita: Ověříme, zda pro všechny \( (x,y) \) a \( (y,z) \) platí \( (x,z) \in W \):
Z \( (a,b) \) a \( (b,c) \) plyne \( (a,c) \), které je v relaci.
Z \( (b,c) \) a \( (c,d) \) plyne \( (b,d) \), ale \( (b,d) \notin W \), tranzitivita neplatí.
Relace není částečným uspořádáním.
56. Na množině \( M = \{1,2,3,4\} \) je relace \( R = \{(1,1),(2,2),(3,3),(4,4),(1,2),(2,3),(3,4),(1,3),(2,4),(1,4)\} \). Určete, zda je \( R \) částečným uspořádáním, a pokud ano, nalezněte minimální a maximální prvky.
Řešení příkladu 56:
Nejprve ověříme reflexivitu: Pro každé \( x \in M \) musí platit \( (x,x) \in R \). Jsou zde všechny prvky \( (1,1), (2,2), (3,3), (4,4) \), reflexivita tedy platí.
Antisymetrie: Zkontrolujeme, zda existují nějaké páry \( (a,b) \in R \) a \( (b,a) \in R \) s \( a \neq b \).
Například \( (1,2) \in R \), ale \( (2,1) \notin R \), obdobně u ostatních nepravidelných párů není zpětný pár v relaci. Antisymetrie tedy platí.
Tranzitivita: Pokud \( (a,b) \in R \) a \( (b,c) \in R \), pak musí být \( (a,c) \in R \). Ověříme několik případů:
Z \( (1,2) \) a \( (2,3) \) plyne \( (1,3) \in R \) – platí.
Z \( (2,3) \) a \( (3,4) \) plyne \( (2,4) \in R \) – platí.
Z \( (1,3) \) a \( (3,4) \) plyne \( (1,4) \in R \) – platí.
Relace obsahuje všechny potřebné složené prvky, tranzitivita platí.
Relace \( R \) je reflexivní, antisymetrická a tranzitivní, tedy částečným uspořádáním.
Minimální prvek: Prvek, který není větší než žádný jiný. \( 1 \) není na pravé straně žádného nepravidelného páru, je minimální.
Maximální prvek: Prvek, který není menší než žádný jiný. \( 4 \) není na levé straně žádného nepravidelného páru, je maximální.
57. Na množině \( A = \{x,y,z,w\} \) je relace \( S = \{(x,x),(y,y),(z,z),(w,w),(x,y),(y,x),(y,z),(z,y),(z,w),(w,z)\} \). Určete, zda je \( S \) relací ekvivalence nebo částečným uspořádáním.
Řešení příkladu 57:
Reflexivita: Pro všechny \( x \in A \) platí \( (x,x) \in S \), reflexivita tedy platí.
Symetrie: Ověříme, zda pro každé \( (a,b) \in S \) je i \( (b,a) \in S \).
Z \( (x,y) \in S \) plyne \( (y,x) \in S \), \( (y,z) \in S \Rightarrow (z,y) \in S \), \( (z,w) \in S \Rightarrow (w,z) \in S \). Symetrie tedy platí.
Tranzitivita: Zkusíme \( (x,y) \) a \( (y,z) \), podle tranzitivity by mělo být \( (x,z) \in S \), ale \( (x,z) \notin S \), tranzitivita neplatí.
Relace tedy není relací ekvivalence.
Antisymetrie: Jelikož symetrie platí a existují \( (x,y) \) a \( (y,x) \) s \( x \neq y \), antisymetrie neplatí.
Relace není částečným uspořádáním.
58. Na množině \( P = \{a,b,c\} \) je relace \( T = \{(a,a),(b,b),(c,c),(a,b),(b,c),(a,c)\} \). Určete, zda je relace \( T \) částečným uspořádáním. Pokud ano, identifikujte minimální a maximální prvky.
Řešení příkladu 58:
Reflexivita: Všechny prvky mají reflexivní dvojice v relaci \( T \), reflexivita platí.
Antisymetrie: Zkontrolujeme, zda existují \( (x,y) \in T \) a \( (y,x) \in T \) s \( x \neq y \).
Neexistují, antisymetrie platí.
Tranzitivita: Ověříme pro všechny možné kombinace:
Z \( (a,b) \) a \( (b,c) \) plyne \( (a,c) \in T \), což je pravda.
Nejsou zde žádné další složené dvojice k ověření, tranzitivita tedy platí.
Relace \( T \) je tedy částečným uspořádáním.
Minimální prvek je takový, který nemá v relaci žádný prvek menší než on:
\( a \) nemá žádný prvek \( x \), pro který by platilo \( (x,a) \in T \) a \( x \neq a \), tedy \( a \) je minimální.
Maximální prvek je ten, který nemá žádný prvek větší než on:
\( c \) nemá žádný prvek \( y \), pro který by platilo \( (c,y) \in T \) a \( y \neq c \), tedy \( c \) je maximální.
59. Na množině \( Q = \{1,2,3,4,5\} \) je relace \( U = \{(1,1),(2,2),(3,3),(4,4),(5,5),(1,3),(3,5),(2,4),(4,5)\} \). Určete, zda je relace \( U \) částečným uspořádáním, a pokud ano, najděte minimální a maximální prvky.
Řešení příkladu 59:
Reflexivita: Pro všechny prvky \( 1,2,3,4,5 \) máme reflexivní dvojice, reflexivita platí.
Antisymetrie: Zkontrolujeme, zda existují nějaké páry \( (a,b) \in U \) a \( (b,a) \in U \) s \( a \neq b \).
Takové páry nejsou přítomné, antisymetrie platí.
Tranzitivita: Zkontrolujeme složené prvky:
Z \( (1,3) \) a \( (3,5) \) plyne, že by mělo být \( (1,5) \in U \), ale není, tranzitivita tedy neplatí.
Relace není částečným uspořádáním.
60. Na množině \( R = \{a,b,c,d\} \) je relace \( W = \{(a,a),(b,b),(c,c),(d,d),(a,b),(b,c),(a,c),(c,d),(a,d),(b,d)\} \). Určete, zda je relace \( W \) částečným uspořádáním, a pokud ano, určete minimální a maximální prvky.
Řešení příkladu 60:
Reflexivita: Všechny prvky mají reflexivní dvojice, reflexivita platí.
Antisymetrie: Neexistuje žádný pár \( (x,y) \in W \) a \( (y,x) \in W \) s \( x \neq y \), antisymetrie platí.
Tranzitivita: Ověříme složené páry:
Z \( (a,b) \) a \( (b,c) \) plyne \( (a,c) \in W \) – platí.
Z \( (b,c) \) a \( (c,d) \) plyne \( (b,d) \in W \) – platí.
Z \( (a,c) \) a \( (c,d) \) plyne \( (a,d) \in W \) – platí.
Z \( (a,b) \) a \( (b,d) \) plyne \( (a,d) \in W \) – platí.
Tranzitivita platí.
Relace je částečným uspořádáním.
Minimální prvek: \( a \), protože není menší než žádný jiný prvek.
Maximální prvek: \( d \), protože není větší než žádný jiný prvek.
61. Na množině \( X = \{1,2,3,4\} \) je relace
\( R = \{(1,1),(2,2),(3,3),(4,4),(1,2),(2,3),(1,3),(3,4)\} \). Určete, zda je relace \( R \) relací ekvivalence nebo částečným uspořádáním.
Řešení příkladu 61:
Zkontrolujeme reflexivitu:
Všechny prvky \( 1,2,3,4 \) mají reflexivní pár, tj. \( (1,1), (2,2), (3,3), (4,4) \in R \), tedy reflexivita platí.
Zkontrolujeme symetrii:
Například \( (1,2) \in R \), ale \( (2,1) \notin R \), symetrie neplatí.
Relace není ekvivalence.
Zkontrolujeme antisymetrii:
Pro \( (1,2) \in R \) je \( (2,1) \notin R \), pro \( (2,3) \in R \) je \( (3,2) \notin R \), pro \( (3,4) \in R \) je \( (4,3) \notin R \). Žádný pár obousměrných vztahů mezi různými prvky tedy není, antisymetrie platí.
Zkontrolujeme tranzitivitu:
\( (1,2) \in R \) a \( (2,3) \in R \Rightarrow (1,3) \in R \) — ano, platí.
\( (2,3) \in R \) a \( (3,4) \in R \Rightarrow (2,4) \in R \) — ale \( (2,4) \notin R \), tranzitivita neplatí.
Relace tedy není částečné uspořádání.
Závěr: Relace \( R \) není ani relací ekvivalence, ani částečným uspořádáním.
62. Na množině \( X = \{a,b,c\} \) je relace
\( Q = \{(a,a),(b,b),(c,c),(a,b),(b,a),(b,c),(c,b)\} \). Určete, zda je relace \( Q \) relací ekvivalence nebo částečným uspořádáním.
Antisymetrie: Existuje \( (a,b) \in Q \) a \( (b,a) \in Q \) s \( a \neq b \), antisymetrie tedy neplatí.
Závěr: Relace \( Q \) není ani relací ekvivalence, ani částečným uspořádáním.
63. Na množině \( X = \{x,y,z\} \) je relace
\( T = \{(x,x),(y,y),(z,z),(x,y),(y,z),(x,z),(z,x)\} \). Určete, zda je relace \( T \) relací ekvivalence nebo částečným uspořádáním.
Řešení příkladu 63:
Reflexivita: Všechny prvky mají reflexivní dvojici, tedy reflexivita platí.
Symetrie: \( (x,y) \in T \), ale \( (y,x) \notin T \), takže symetrie neplatí.
Relace není ekvivalencí.
Antisymetrie: Zkontrolujeme, zda existují oba páry \( (a,b) \) i \( (b,a) \) s \( a \neq b \):
Máme \( (x,z) \in T \) a \( (z,x) \in T \) s \( x \neq z \), tedy antisymetrie neplatí.
Závěr: Relace není částečné uspořádání ani ekvivalence.
64. Na množině \( X = \{1,2,3\} \) je relace
\( U = \{(1,1),(2,2),(3,3),(1,2),(2,1),(2,3),(3,2)\} \). Určete, zda je relace \( U \) relací ekvivalence nebo částečným uspořádáním.
Řešení příkladu 64:
Reflexivita platí, jelikož \( (1,1),(2,2),(3,3) \in U \).
Symetrie: Pro každý pár ověříme inverzní pár:
\( (1,2) \in U \) a \( (2,1) \in U \), \( (2,3) \in U \) a \( (3,2) \in U \), symetrie tedy platí.
Zkontrolujeme tranzitivitu:
\( (1,2) \in U \) a \( (2,3) \in U \Rightarrow (1,3) \in U \)? Ne, protože \( (1,3) \notin U \).
Relace není tranzitivní, tedy není ekvivalence.
Antisymetrie: \( (1,2) \in U \) a \( (2,1) \in U \) s \( 1 \neq 2 \), antisymetrie neplatí.
Závěr: Relace \( U \) není ani ekvivalence, ani částečné uspořádání.
65. Na množině \( X = \{a,b,c,d\} \) je relace
\( V = \{(a,a),(b,b),(c,c),(d,d),(a,b),(b,c),(a,c),(c,d),(a,d)\} \). Určete, zda je relace \( V \) relací ekvivalence nebo částečným uspořádáním.
Řešení příkladu 65:
Reflexivita: Všechny prvky mají reflexivní páry, tedy platí reflexivita.
Symetrie: Například \( (a,b) \in V \), ale \( (b,a) \notin V \), symetrie neplatí.
Relace není ekvivalence.
Antisymetrie: Zkontrolujeme, zda existují páry obousměrné u různých prvků:
Neexistuje žádný pár \( (x,y) \in V \) a \( (y,x) \in V \) s \( x \neq y \), antisymetrie tedy platí.
Tranzitivita: Ověříme základní případy:
\( (a,b) \in V \) a \( (b,c) \in V \Rightarrow (a,c) \in V \), platí.
\( (b,c) \in V \) a \( (c,d) \in V \Rightarrow (b,d) \in V \)? Ne, protože \( (b,d) \notin V \).
Tranzitivita neplatí, tedy relace není částečné uspořádání.
Závěr: Relace \( V \) není ani relací ekvivalence, ani částečným uspořádáním.
66. Na množině \( X = \{1,2,3,4\} \) je relace
\( R = \{(1,1),(2,2),(3,3),(4,4),(1,2),(2,3),(3,4),(1,3),(2,4),(1,4)\} \). Určete, zda je relace \( R \) relací ekvivalence nebo částečným uspořádáním.
Řešení příkladu 66:
Nejprve zkontrolujeme reflexivitu:
Všechny prvky množiny \( X \) mají reflexivní dvojici \( (x,x) \in R \) pro \( x = 1,2,3,4 \), tedy reflexivita platí.
Zkontrolujeme symetrii:
Například \( (1,2) \in R \), ale \( (2,1) \notin R \), takže symetrie neplatí.
Relace tedy není ekvivalence.
Ověříme antisymetrii:
Hledáme zda existuje pár \( (x,y) \in R \) a zároveň \( (y,x) \in R \) s \( x \neq y \).
Žádný takový pár neexistuje, antisymetrie tedy platí.
Zkontrolujeme tranzitivitu:
Máme například \( (1,2) \in R \) a \( (2,3) \in R \Rightarrow (1,3) \in R \) – platí.
Dále \( (2,3) \in R \) a \( (3,4) \in R \Rightarrow (2,4) \in R \) – platí.
Také \( (1,3) \in R \) a \( (3,4) \in R \Rightarrow (1,4) \in R \) – platí.
Všechny potřebné trojice jsou v relaci, tranzitivita tedy platí.
Závěr: Relace \( R \) je reflexivní, antisymetrická a tranzitivní, tedy je částečným uspořádáním.
67. Na množině \( X = \{a,b,c,d\} \) je relace
\( S = \{(a,a),(b,b),(c,c),(d,d),(a,b),(b,a),(b,c),(c,b),(a,c),(c,a)\} \). Určete, zda je relace \( S \) relací ekvivalence nebo částečným uspořádáním.
Řešení příkladu 67:
Reflexivita: Všechny prvky mají reflexivní dvojici, tedy reflexivita platí.
Symetrie: Pro každý pár je i inverzní pár v relaci:
\( (a,b) \in S \) a \( (b,a) \in S \), \( (b,c) \in S \) a \( (c,b) \in S \), \( (a,c) \in S \) a \( (c,a) \in S \), symetrie tedy platí.
Tranzitivita: Ověříme klíčové případy:
\( (a,b) \in S \) a \( (b,c) \in S \Rightarrow (a,c) \in S \), platí.
\( (b,a) \in S \) a \( (a,c) \in S \Rightarrow (b,c) \in S \), platí.
Všechny kombinace jsou pokryté, tedy tranzitivita platí.
Závěr: Relace \( S \) je reflexivní, symetrická a tranzitivní, tedy je relací ekvivalence.
68. Na množině \( X = \{1,2,3,4,5\} \) je relace
\( T = \{(1,1),(2,2),(3,3),(4,4),(5,5),(1,3),(3,5),(1,5),(2,4),(4,5),(2,5)\} \). Určete, zda je relace \( T \) relací ekvivalence nebo částečným uspořádáním.
Řešení příkladu 68:
Reflexivita: Všechny prvky mají reflexivní dvojici, tedy reflexivita platí.
Symetrie: Zkontrolujeme několik párů:
\( (1,3) \in T \), ale \( (3,1) \notin T \), symetrie neplatí.
Relace není ekvivalencí.
Antisymetrie: Ověříme, zda existují oba páry \( (x,y) \) a \( (y,x) \) s \( x \neq y \).
Nevyskytuje se žádný takový pár, antisymetrie platí.
Tranzitivita:
\( (1,3) \in T \) a \( (3,5) \in T \Rightarrow (1,5) \in T \), platí.
\( (2,4) \in T \) a \( (4,5) \in T \Rightarrow (2,5) \in T \), platí.
Všechny relevantní případy tranzitivity jsou splněny, tranzitivita tedy platí.
Závěr: Relace \( T \) je reflexivní, antisymetrická a tranzitivní, je tedy částečným uspořádáním.
69. Na množině \( X = \{x,y,z\} \) je relace
\( U = \{(x,x),(y,y),(z,z),(x,y),(y,x),(y,z),(z,y),(x,z),(z,x)\} \). Určete, zda je relace \( U \) relací ekvivalence nebo částečným uspořádáním.
Řešení příkladu 69:
Reflexivita platí, všechny prvky mají reflexivní pár.
Symetrie: Pro všechny prvky \( (a,b) \in U \) existuje \( (b,a) \in U \), tedy symetrie platí.
Tranzitivita: Zkontrolujeme případy:
\( (x,y) \in U \) a \( (y,z) \in U \Rightarrow (x,z) \in U \), platí.
\( (y,x) \in U \) a \( (x,z) \in U \Rightarrow (y,z) \in U \), platí.
Relace je tedy tranzitivní.
Závěr: Relace \( U \) je reflexivní, symetrická a tranzitivní, tedy relací ekvivalence.
70. Na množině \( X = \{1,2,3,4\} \) je relace
\( V = \{(1,1),(2,2),(3,3),(4,4),(1,2),(2,3),(3,4),(1,3),(2,4)\} \). Určete, zda je relace \( V \) relací ekvivalence nebo částečným uspořádáním.
Řešení příkladu 70:
Reflexivita: Všechny prvky mají reflexivní dvojici, reflexivita platí.
Symetrie: Například \( (1,2) \in V \), ale \( (2,1) \notin V \), symetrie neplatí.
Relace není ekvivalencí.
Antisymetrie: Neexistují žádné oba páry \( (x,y) \) a \( (y,x) \) s \( x \neq y \), antisymetrie tedy platí.
Tranzitivita:
\( (1,2) \in V \) a \( (2,3) \in V \Rightarrow (1,3) \in V \), platí.
\( (2,3) \in V \) a \( (3,4) \notin V \), tudíž není třeba kontrolovat.
\( (1,3) \in V \) a \( (3,4) \notin V \), tranzitivita tedy není porušena.
Relace je tranzitivní.
Závěr: Relace \( V \) je reflexivní, antisymetrická a tranzitivní, je tedy částečným uspořádáním.
71. Na množině \( X = \{a,b,c,d\} \) je relace
\( R = \{(a,a),(b,b),(c,c),(d,d),(a,b),(b,c),(a,c),(c,d),(a,d)\} \). Určete, zda je relace \( R \) relací ekvivalence nebo částečným uspořádáním.
Řešení příkladu 71:
Reflexivita: Všechny prvky mají reflexivní dvojici, tedy reflexivita platí.
Symetrie: Zkontrolujeme, zda pro každý pár platí, že pokud \( (x,y) \in R \), pak i \( (y,x) \in R \).
\( (a,b) \in R \), ale \( (b,a) \notin R \), symetrie tedy neplatí.
Relace není ekvivalencí.
Antisymetrie: Ověříme, zda existují oba páry \( (x,y) \) a \( (y,x) \) s \( x \neq y \).
Nenacházíme žádný takový pár, antisymetrie tedy platí.
Tranzitivita:
Podíváme se na páry, které by měly zajistit tranzitivitu:
\( (a,b) \in R \) a \( (b,c) \in R \Rightarrow (a,c) \in R \) – platí.
\( (b,c) \in R \) a \( (c,d) \in R \Rightarrow (b,d) \in R \) – ale \( (b,d) \notin R \), tranzitivita tedy neplatí.
Závěr: Relace \( R \) není tranzitivní, není tedy částečným uspořádáním ani relací ekvivalence.
72. Na množině \( X = \{1,2,3,4\} \) je relace
\( S = \{(1,1),(2,2),(3,3),(4,4),(1,2),(2,1),(2,3),(3,2),(3,4),(4,3),(1,4),(4,1)\} \). Určete, zda je relace \( S \) relací ekvivalence nebo částečným uspořádáním.
Řešení příkladu 72:
Reflexivita: Každý prvek má dvojici \( (x,x) \in S \), reflexivita platí.
Symetrie: Zkontrolujeme pro vybrané páry:
\( (1,2) \in S \) a \( (2,1) \in S \), \( (2,3) \in S \) a \( (3,2) \in S \), \( (3,4) \in S \) a \( (4,3) \in S \), \( (1,4) \in S \) a \( (4,1) \in S \), tedy symetrie platí.
Tranzitivita: Prověříme kritické případy:
\( (1,2) \in S \) a \( (2,3) \in S \Rightarrow (1,3) \in S \)?
\( (1,3) \notin S \), tranzitivita neplatí.
Závěr: Relace není tranzitivní, tudíž není relací ekvivalence.
Antisymetrie: Neplatí, protože existují páry \( (1,2) \) i \( (2,1) \) s \( 1 \neq 2 \).
Relace není částečným uspořádáním.
73. Na množině \( X = \{a,b,c\} \) je relace
\( T = \{(a,a),(b,b),(c,c),(a,b),(b,c),(a,c)\} \). Určete, zda je relace \( T \) relací ekvivalence nebo částečným uspořádáním.
Řešení příkladu 73:
Reflexivita: Všechny prvky mají reflexivní dvojici, reflexivita platí.
Symetrie: Zkontrolujeme:
\( (a,b) \in T \), ale \( (b,a) \notin T \), symetrie neplatí.
Relace není ekvivalencí.
Antisymetrie: Ověříme, zda existuje pár \( (x,y) \) a \( (y,x) \) s \( x \neq y \).
Takový pár neexistuje, antisymetrie platí.
Tranzitivita:
\( (a,b) \in T \) a \( (b,c) \in T \Rightarrow (a,c) \in T \), platí.
Relace je tedy tranzitivní.
Závěr: Relace \( T \) je reflexivní, antisymetrická a tranzitivní, tedy částečným uspořádáním.
74. Na množině \( X = \{1,2,3,4,5\} \) je relace
\( U = \{(1,1),(2,2),(3,3),(4,4),(5,5),(1,3),(3,1),(2,4),(4,2),(3,5),(5,3)\} \). Určete, zda je relace \( U \) relací ekvivalence nebo částečným uspořádáním.
Řešení příkladu 74:
Reflexivita: Všechny prvky mají reflexivní dvojici, reflexivita platí.
Symetrie: Pro každý pár zkontrolujeme, zda je inverzní pár také v relaci:
\( (1,3) \in U \) a \( (3,1) \in U \), \( (2,4) \in U \) a \( (4,2) \in U \), \( (3,5) \in U \) a \( (5,3) \in U \), tedy symetrie platí.
Tranzitivita: Zkontrolujeme některé případy:
\( (1,3) \in U \) a \( (3,5) \in U \Rightarrow (1,5) \in U \)?
\( (1,5) \notin U \), tranzitivita neplatí.
Závěr: Relace není tranzitivní, není tedy relací ekvivalence.
Antisymetrie: Neplatí, protože existují oba páry \( (1,3) \) a \( (3,1) \) s \( 1 \neq 3 \).
Relace není částečným uspořádáním.
75. Na množině \( X = \{p,q,r,s\} \) je relace
\( V = \{(p,p),(q,q),(r,r),(s,s),(p,q),(q,r),(p,r),(r,s),(p,s)\} \). Určete, zda je relace \( V \) relací ekvivalence nebo částečným uspořádáním.
Řešení příkladu 75:
Reflexivita: Každý prvek má reflexivní dvojici, reflexivita platí.
Symetrie: Zkontrolujeme, zda pokud \( (x,y) \in V \), pak \( (y,x) \in V \):
\( (p,q) \in V \), ale \( (q,p) \notin V \), symetrie neplatí.
Relace není ekvivalencí.
Antisymetrie: Ověříme, zda existují oba páry \( (x,y) \) a \( (y,x) \) s \( x \neq y \).
Nenacházíme žádné takové páry, antisymetrie platí.
Tranzitivita:
\( (p,q) \in V \) a \( (q,r) \in V \Rightarrow (p,r) \in V \), platí.
\( (q,r) \in V \) a \( (r,s) \in V \Rightarrow (q,s) \in V \)?
\( (q,s) \notin V \), tranzitivita neplatí.
Závěr: Relace není tranzitivní, není tedy částečným uspořádáním ani relací ekvivalence.
76. Na množině \( X = \{x,y,z\} \) je relace
\( R = \{(x,x),(y,y),(z,z),(x,y),(y,z),(x,z),(y,x)\} \). Určete, zda je relace \( R \) relací ekvivalence nebo částečným uspořádáním.
Řešení příkladu 76:
Reflexivita: Všechny prvky mají dvojici \( (a,a) \in R \), reflexivita platí.
Symetrie: Pro relaci musí platit, že pokud \( (x,y) \in R \), tak i \( (y,x) \in R \).
Zkontrolujeme:
\( (x,y) \in R \) a \( (y,x) \in R \), symetrie platí pro tento pár.
\( (y,z) \in R \), ale \( (z,y) \notin R \), symetrie tedy neplatí.
Relace není ekvivalencí.
Antisymetrie: Zkontrolujeme, zda existují oba páry \( (x,y) \) i \( (y,x) \) s \( x \neq y \).
\( (x,y) \in R \) a \( (y,x) \in R \) s \( x \neq y \), antisymetrie neplatí.
Relace tedy nemůže být částečným uspořádáním.
Závěr: Relace není ani relací ekvivalence, ani částečným uspořádáním.
77. Na množině \( X = \{1,2,3,4\} \) je relace
\( S = \{(1,1),(2,2),(3,3),(4,4),(1,2),(2,3),(3,4),(1,3),(2,4),(1,4)\} \). Určete, zda je relace \( S \) relací ekvivalence nebo částečným uspořádáním.
Řešení příkladu 77:
Reflexivita: Každý prvek má reflexivní dvojici, reflexivita platí.
Symetrie: Pro každý pár \( (x,y) \in S \) zkontrolujeme, zda \( (y,x) \in S \).
Zkontrolujeme např. \( (1,2) \in S \), ale \( (2,1) \notin S \), symetrie neplatí.
Relace není ekvivalencí.
Antisymetrie: Zkontrolujeme, zda existuje pár \( (x,y) \) a \( (y,x) \) s \( x \neq y \).
Nenacházíme takový pár, antisymetrie platí.
Tranzitivita:
Zkontrolujeme, zda platí, že pokud \( (x,y) \in S \) a \( (y,z) \in S \), pak \( (x,z) \in S \):
\( (1,2) \in S \) a \( (2,3) \in S \Rightarrow (1,3) \in S \) – platí.
\( (2,3) \in S \) a \( (3,4) \in S \Rightarrow (2,4) \in S \) – platí.
\( (1,3) \in S \) a \( (3,4) \in S \Rightarrow (1,4) \in S \) – platí.
Závěr: Relace je reflexivní, antisymetrická a tranzitivní, tedy částečným uspořádáním.
78. Na množině \( X = \{a,b,c,d\} \) je relace
\( T = \{(a,a),(b,b),(c,c),(d,d),(a,b),(b,a),(b,c),(c,b),(c,d),(d,c),(a,d),(d,a)\} \). Určete, zda je relace \( T \) relací ekvivalence nebo částečným uspořádáním.
Řešení příkladu 78:
Reflexivita: Každý prvek má reflexivní dvojici, reflexivita platí.
Symetrie: Pro každý pár zkontrolujeme, zda inverzní pár je také v relaci:
Například \( (a,b) \in T \) a \( (b,a) \in T \), stejně tak \( (b,c) \in T \) a \( (c,b) \in T \), \( (c,d) \in T \) a \( (d,c) \in T \), \( (a,d) \in T \) a \( (d,a) \in T \), tedy symetrie platí.
Tranzitivita:
Zkontrolujeme:
\( (a,b) \in T \) a \( (b,c) \in T \Rightarrow (a,c) \in T \)?
\( (a,c) \notin T \), tranzitivita neplatí.
Závěr: Relace není tranzitivní, proto není ekvivalencí.
Antisymetrie: Neplatí, protože existují páry \( (a,b) \) a \( (b,a) \) s \( a \neq b \).
Relace není částečným uspořádáním.
79. Na množině \( X = \{1,2,3\} \) je relace
\( U = \{(1,1),(2,2),(3,3),(1,2),(2,3)\} \). Určete, zda je relace \( U \) relací ekvivalence nebo částečným uspořádáním.
Řešení příkladu 79:
Reflexivita: Každý prvek má reflexivní dvojici, reflexivita platí.
Symetrie: Zkontrolujeme, zda pro každý pár platí, že pokud \( (x,y) \in U \), pak i \( (y,x) \in U \):
\( (1,2) \in U \), ale \( (2,1) \notin U \), symetrie neplatí.
Relace není ekvivalencí.
Antisymetrie: Zkontrolujeme, zda existují oba páry \( (x,y) \) a \( (y,x) \) s \( x \neq y \).
Nenacházíme takový pár, antisymetrie platí.
Tranzitivita: Zkontrolujeme:
\( (1,2) \in U \) a \( (2,3) \in U \Rightarrow (1,3) \in U \)?
\( (1,3) \notin U \), tranzitivita neplatí.
Závěr: Relace není tranzitivní, není částečným uspořádáním ani relací ekvivalence.
80. Na množině \( X = \{a,b,c,d\} \) je relace
\( V = \{(a,a),(b,b),(c,c),(d,d),(a,b),(b,c),(c,d),(a,c),(b,d),(a,d)\} \). Určete, zda je relace \( V \) relací ekvivalence nebo částečným uspořádáním.
Řešení příkladu 80:
Reflexivita: Reflexivní páry jsou přítomné u všech prvků, reflexivita platí.
Symetrie: Zkontrolujeme, zda pro každý pár \( (x,y) \in V \) existuje i \( (y,x) \in V \):
\( (a,b) \in V \), ale \( (b,a) \notin V \), symetrie neplatí.
Relace není ekvivalencí.
Antisymetrie: Zkontrolujeme, zda existují oba páry \( (x,y) \) a \( (y,x) \) s \( x \neq y \).
Nenacházíme takové páry, antisymetrie platí.
Tranzitivita:
Zkontrolujeme případy:
\( (a,b) \in V \) a \( (b,c) \in V \Rightarrow (a,c) \in V \), platí.
\( (b,c) \in V \) a \( (c,d) \in V \Rightarrow (b,d) \in V \), platí.
\( (a,c) \in V \) a \( (c,d) \in V \Rightarrow (a,d) \in V \), platí.
Závěr: Relace je reflexivní, antisymetrická a tranzitivní, tedy částečným uspořádáním.
81. Na množině \( X = \{a,b,c,d\} \) je relace
\( R = \{(a,a),(b,b),(c,c),(d,d),(a,b),(b,a),(b,c),(c,b),(a,c),(c,a)\} \). Určete, zda je relace \( R \) relací ekvivalence nebo částečným uspořádáním.
Řešení příkladu 81:
Nejprve zkontrolujeme, zda je relace \( R \) relací ekvivalence.
Reflexivita: Relace obsahuje všechny dvojice \( (x,x) \) pro \( x \in X \), tedy \( (a,a), (b,b), (c,c), (d,d) \in R \). Reflexivita platí.
Symetrie: Pro každý pár \( (x,y) \in R \) musí být také \( (y,x) \in R \). Zkontrolujeme klíčové páry:
\( (a,b) \in R \) a \( (b,a) \in R \) – symetrie platí.
\( (b,c) \in R \) a \( (c,b) \in R \) – symetrie platí.
\( (a,c) \in R \) a \( (c,a) \in R \) – symetrie platí.
Páry obsahují i své symetrické protějšky, symetrie tedy platí.
Tranzitivita: Pro všechny \( x,y,z \in X \), pokud \( (x,y) \in R \) a \( (y,z) \in R \), musí být \( (x,z) \in R \). Zkusíme klíčové případy:
1. \( (a,b) \in R \) a \( (b,c) \in R \) \Rightarrow \( (a,c) \in R \), což platí.
2. \( (b,a) \in R \) a \( (a,b) \in R \) \Rightarrow \( (b,b) \in R \), platí.
3. \( (c,a) \in R \) a \( (a,b) \in R \) \Rightarrow \( (c,b) \in R \), platí.
Nezjistili jsme žádné porušení tranzitivity, tranzitivita tedy platí.
Závěr: Relace je reflexivní, symetrická i tranzitivní, tedy je relací ekvivalence.
82. Na množině \( X = \{1,2,3,4,5\} \) je relace
\( S = \{(1,1),(2,2),(3,3),(4,4),(5,5),(1,2),(2,3),(3,4),(4,5),(1,3),(2,4),(3,5)\} \). Určete, zda je relace \( S \) relací ekvivalence nebo částečným uspořádáním.
Řešení příkladu 82:
Ověříme reflexivitu:
Všechny prvky mají dvojici \( (x,x) \), tedy \( (1,1), (2,2), (3,3), (4,4), (5,5) \in S \). Reflexivita platí.
Symetrie: Pro symetrii musí platit, že pokud \( (x,y) \in S \), pak i \( (y,x) \in S \). Zkontrolujeme:
\( (1,2) \in S \), ale \( (2,1) \notin S \), symetrie tedy neplatí.
Relace není relací ekvivalence.
Antisymetrie: Zkontrolujeme, zda neexistuje \( (x,y) \in S \) a \( (y,x) \in S \) s \( x \neq y \).
Žádné takové páry neexistují, antisymetrie tedy platí.
Tranzitivita: Zkontrolujeme, zda pokud \( (x,y) \in S \) a \( (y,z) \in S \), pak \( (x,z) \in S \):
1. \( (1,2) \in S \) a \( (2,3) \in S \) \Rightarrow \( (1,3) \in S \), platí.
2. \( (2,3) \in S \) a \( (3,4) \in S \) \Rightarrow \( (2,4) \in S \), kontrola: \( (2,4) \in S \), platí.
3. \( (3,4) \in S \) a \( (4,5) \in S \) \Rightarrow \( (3,5) \in S \), platí.
Tranzitivita tedy platí.
Závěr: Relace je reflexivní, antisymetrická a tranzitivní, tedy je částečným uspořádáním.
83. Na množině \( X = \{x,y,z\} \) je relace
\( T = \{(x,x),(y,y),(z,z),(x,y),(y,x),(y,z),(z,y)\} \). Určete, zda je relace \( T \) relací ekvivalence nebo částečným uspořádáním.
Řešení příkladu 83:
Reflexivita: \( (x,x), (y,y), (z,z) \in T \), reflexivita platí.
Symetrie: Zkontrolujeme páry:
\( (x,y) \in T \) a \( (y,x) \in T \), symetrie platí.
\( (y,z) \in T \) a \( (z,y) \in T \), symetrie platí.
Symetrie tedy platí pro všechny prvky relace.
Tranzitivita: Zkontrolujeme všechny možnosti, kde to může být problematické:
\( (x,y) \in T \) a \( (y,z) \in T \) \Rightarrow \( (x,z) \in T \)?
\( (x,z) \notin T \), tranzitivita neplatí.
Závěr: Relace není tranzitivní, tudíž není relací ekvivalence.
Antisymetrie: Z \( (x,y) \in T \) a \( (y,x) \in T \) s \( x \neq y \) plyne, že antisymetrie neplatí.
Relace není částečným uspořádáním.
84. Na množině \( X = \{1,2,3,4\} \) je relace
\( U = \{(1,1),(2,2),(3,3),(4,4),(1,2),(1,3),(2,4),(3,4)\} \). Určete, zda je relace \( U \) relací ekvivalence nebo částečným uspořádáním.
Řešení příkladu 84:
Reflexivita: Dvojice \( (1,1), (2,2), (3,3), (4,4) \in U \), reflexivita platí.
Symetrie: Například \( (1,2) \in U \), ale \( (2,1) \notin U \), symetrie neplatí.
Relace není ekvivalencí.
Antisymetrie: Musíme zkontrolovat, zda existují oba páry \( (x,y) \) a \( (y,x) \) s \( x \neq y \). Žádné takové páry nejsou přítomné, antisymetrie platí.
Tranzitivita: Zkontrolujeme:
\( (1,2) \in U \) a \( (2,4) \in U \Rightarrow (1,4) \in U \)?
\( (1,4) \notin U \), tranzitivita neplatí.
Závěr: Relace není tranzitivní, není částečným uspořádáním ani relací ekvivalence.
85. Na množině \( X = \{a,b,c\} \) je relace
\( V = \{(a,a),(b,b),(c,c),(a,b),(b,c),(a,c),(b,a)\} \). Určete, zda je relace \( V \) relací ekvivalence nebo částečným uspořádáním.
Řešení příkladu 85:
Reflexivita: Všechny prvky mají reflexivní dvojici \( (a,a), (b,b), (c,c) \in V \), reflexivita platí.
Symetrie: Zkontrolujeme pro všechny nepřímé páry:
\( (a,b) \in V \) a \( (b,a) \in V \), symetrie platí pro tyto prvky.
\( (b,c) \in V \), ale \( (c,b) \notin V \), symetrie neplatí.
Relace není ekvivalencí.
Antisymetrie: Jelikož \( (a,b) \in V \) a \( (b,a) \in V \) s \( a \neq b \), antisymetrie neplatí.
Relace tedy nemůže být částečným uspořádáním.
Závěr: Relace není ani relací ekvivalence, ani částečným uspořádáním.
86. Na množině \( X = \{a,b,c,d\} \) je relace \( R = \{(a,a),(b,b),(c,c),(d,d),(a,b),(b,c),(a,c)\} \). Určete, zda je relace \( R \) relací ekvivalence nebo částečným uspořádáním.
Řešení příkladu 86:
Nejprve zkontrolujeme reflexivitu:
\( (a,a), (b,b), (c,c), (d,d) \in R \), reflexivita tedy platí.
Symetrie:
Zkontrolujeme pro každý prvek: například \( (a,b) \in R \), ale \( (b,a) \notin R \), symetrie tedy neplatí.
Relace není ekvivalence.
Zkontrolujeme antisymetrii:
Existuje-li \( (x,y) \in R \) a \( (y,x) \in R \) s \( x \neq y \), antisymetrie neplatí.
V tomto případě žádný takový pár neexistuje, tedy antisymetrie platí.
Tranzitivita:
Z \( (a,b) \in R \) a \( (b,c) \in R \) plyne, že musí být \( (a,c) \in R \), což platí.
Nejsou další kombinace k ověření, všechny vyhovují.
Relace \( R \) je reflexivní, antisymetrická a tranzitivní, tedy je částečným uspořádáním.
87. Na množině \( X = \{1,2,3,4\} \) je relace \( S = \{(1,1),(2,2),(3,3),(4,4),(1,2),(2,1),(3,4),(4,3)\} \). Určete, zda je relace \( S \) relací ekvivalence nebo částečným uspořádáním.
Řešení příkladu 87:
Reflexivita: všechny prvky mají v relaci pár \( (x,x) \), reflexivita platí.
Symetrie:
Pro \( (1,2) \in S \) máme \( (2,1) \in S \), pro \( (3,4) \in S \) máme \( (4,3) \in S \), symetrie tedy platí.
Tranzitivita:
Zkontrolujeme všechny možné dvojice:
\( (1,2) \) a \( (2,1) \Rightarrow (1,1) \in S \) – platí.
\( (2,1) \) a \( (1,2) \Rightarrow (2,2) \in S \) – platí.
\( (3,4) \) a \( (4,3) \Rightarrow (3,3) \in S \) – platí.
\( (4,3) \) a \( (3,4) \Rightarrow (4,4) \in S \) – platí.
Žádné jiné kombinace neporušují tranzitivitu, tedy tranzitivita platí.
Relace je reflexivní, symetrická a tranzitivní, tedy relace ekvivalence.
88. Na množině \( X = \{x,y,z\} \) je relace \( T = \{(x,x),(y,y),(z,z),(x,y),(y,z)\} \). Určete, zda je relace \( T \) relací ekvivalence nebo částečným uspořádáním.
Řešení příkladu 88:
Reflexivita:
\( (x,x), (y,y), (z,z) \in T \), reflexivita tedy platí.
Symetrie:
\( (x,y) \in T \), ale \( (y,x) \notin T \), symetrie neplatí.
Relace není ekvivalence.
Antisymetrie:
Neexistuje žádný pár \( (a,b) \) a \( (b,a) \) s \( a \neq b \), takže antisymetrie platí.
Tranzitivita:
Z \( (x,y) \in T \) a \( (y,z) \in T \) musí být \( (x,z) \in T \), což není pravda.
Tranzitivita neplatí.
Relace \( T \) není ani relací ekvivalence, ani částečným uspořádáním.
89. Na množině \( X = \{m,n,o\} \) je relace \( U = \{(m,m),(n,n),(o,o),(m,n),(n,m),(n,o),(o,n),(m,o),(o,m)\} \). Určete, zda je relace \( U \) relací ekvivalence nebo částečným uspořádáním.
Řešení příkladu 89:
Reflexivita:
\( (m,m), (n,n), (o,o) \in U \), reflexivita platí.
Symetrie:
Pro všechny \( (x,y) \in U \) existuje i \( (y,x) \in U \), symetrie tedy platí.
Tranzitivita:
Zkontrolujeme kombinace:
\( (m,n) \) a \( (n,o) \Rightarrow (m,o) \in U \) – platí.
\( (n,m) \) a \( (m,o) \Rightarrow (n,o) \in U \) – platí.
\( (m,o) \) a \( (o,n) \Rightarrow (m,n) \in U \) – platí.
Další kombinace jsou obdobné a platí.
Relace je reflexivní, symetrická a tranzitivní, tedy relace ekvivalence.
90. Na množině \( X = \{1,2,3,4\} \) je relace \( V = \{(1,1),(2,2),(3,3),(4,4),(1,2),(1,3),(2,4),(3,4)\} \). Určete, zda je relace \( V \) relací ekvivalence nebo částečným uspořádáním.
Řešení příkladu 90:
Reflexivita:
\( (1,1), (2,2), (3,3), (4,4) \in V \), reflexivita platí.
Symetrie:
Z \( (1,2) \in V \), ale \( (2,1) \notin V \), symetrie neplatí.
Relace není ekvivalence.
Antisymetrie:
Neexistuje žádný pár \( (x,y) \) a \( (y,x) \) s \( x \neq y \), antisymetrie tedy platí.
Tranzitivita:
Z \( (1,2) \in V \) a \( (2,4) \in V \) plyne \( (1,4) \) musí být v relaci, ale není.
Tranzitivita neplatí, relace není částečným uspořádáním.
Relace \( V \) není ani relací ekvivalence, ani částečným uspořádáním.
91. Na množině \( X = \{a,b,c,d\} \) je relace \( R = \{(a,a),(b,b),(c,c),(d,d),(a,b),(b,c),(a,c),(c,d),(a,d)\} \). Určete, zda je relace \( R \) relací ekvivalence nebo částečným uspořádáním.
Řešení příkladu 91:
Reflexivita: Všechny prvky mají v relaci reflexivní páry, tedy \( (a,a), (b,b), (c,c), (d,d) \in R \), reflexivita platí.
Symetrie:
Zkusíme najít pár, kde by symetrie mohla selhat. Například \( (a,b) \in R \), ale \( (b,a) \notin R \), tedy symetrie neplatí.
Relace tedy není ekvivalence.
Antisymetrie:
Zkontrolujeme, zda existují dva různé prvky \( x,y \) takové, že \( (x,y) \in R \) a zároveň \( (y,x) \in R \). V množině žádné takové dvojice není, tedy antisymetrie platí.
Tranzitivita:
Zkusíme ověřit tranzitivitu pro všechny kombinace:
Máme \( (a,b) \in R \) a \( (b,c) \in R \), podle tranzitivity musí být \( (a,c) \in R \), což platí.
Dále \( (a,c) \in R \) a \( (c,d) \in R \) \Rightarrow \( (a,d) \in R \), což také platí.
Žádná další kombinace porušující tranzitivitu neexistuje.
Relace je reflexivní, antisymetrická a tranzitivní, tedy částečné uspořádání.
92. Na množině \( X = \{1,2,3\} \) je relace \( S = \{(1,1),(2,2),(3,3),(1,2),(2,1),(2,3),(3,2)\} \). Určete, zda je relace \( S \) relací ekvivalence nebo částečným uspořádáním.
Řešení příkladu 92:
Reflexivita: Relace obsahuje všechny reflexivní páry, tj. \( (1,1), (2,2), (3,3) \), reflexivita platí.
Symetrie:
Zkontrolujeme, zda platí symetrie. Pro \( (1,2) \in S \) máme i \( (2,1) \in S \), stejně tak pro \( (2,3) \in S \) je \( (3,2) \in S \). Symetrie tedy platí.
Tranzitivita:
Podíváme se na \( (1,2) \in S \) a \( (2,3) \in S \), podle tranzitivity by mělo být \( (1,3) \in S \), ale toto není v relaci.
Tranzitivita neplatí, relace není ekvivalence.
Antisymetrie:
Jelikož existují \( (1,2) \) a \( (2,1) \) s \( 1 \neq 2 \), antisymetrie neplatí.
Relace není částečným uspořádáním.
Relace není ani relací ekvivalence, ani částečným uspořádáním.
93. Na množině \( X = \{x,y,z,w\} \) je relace \( T = \{(x,x),(y,y),(z,z),(w,w),(x,y),(y,z),(x,z),(z,w),(y,w),(x,w)\} \). Určete, zda je relace \( T \) relací ekvivalence nebo částečným uspořádáním.
Například \( (x,y) \in T \), ale \( (y,x) \notin T \), symetrie neplatí.
Relace není ekvivalence.
Antisymetrie:
Neexistuje žádný pár \( (a,b) \) a \( (b,a) \) s \( a \neq b \), antisymetrie platí.
Tranzitivita:
Zkusíme některé případy:
Z \( (x,y) \in T \) a \( (y,z) \in T \) plyne \( (x,z) \in T \), což je pravda.
Z \( (y,z) \in T \) a \( (z,w) \in T \) plyne \( (y,w) \in T \), platí.
Z \( (x,z) \in T \) a \( (z,w) \in T \) plyne \( (x,w) \in T \), platí.
Žádná další kombinace neporušuje tranzitivitu.
Relace je částečné uspořádání.
94. Na množině \( X = \{1,2,3\} \) je relace \( U = \{(1,1),(2,2),(3,3),(1,2),(2,3),(1,3),(2,1)\} \). Určete, zda je relace \( U \) relací ekvivalence nebo částečným uspořádáním.
Řešení příkladu 94:
Reflexivita: Všechny prvky mají reflexivní páry, tedy platí.
Symetrie:
Z \( (1,2) \in U \) a \( (2,1) \in U \), symetrie tedy alespoň částečně platí.
Zkusíme další páry:
\( (2,3) \in U \), ale \( (3,2) \notin U \), symetrie neplatí úplně.
Relace není ekvivalence.
Antisymetrie:
Existují \( (1,2) \) a \( (2,1) \) s \( 1 \neq 2 \), což porušuje antisymetrii.
Relace není částečným uspořádáním.
Tranzitivita:
Z \( (1,2) \) a \( (2,3) \Rightarrow (1,3) \in U \), což platí.
Relace není ani ekvivalence, ani částečné uspořádání.
95. Na množině \( X = \{a,b,c,d\} \) je relace \( V = \{(a,a),(b,b),(c,c),(d,d),(a,b),(b,c),(c,d),(a,c),(b,d),(a,d)\} \). Určete, zda je relace \( V \) relací ekvivalence nebo částečným uspořádáním.
Řešení příkladu 95:
Reflexivita: Všechny prvky mají reflexivní páry, reflexivita platí.
Symetrie:
Zkusíme ověřit symetrii. Například \( (a,b) \in V \), ale \( (b,a) \notin V \), symetrie neplatí.
Relace není ekvivalence.
Antisymetrie:
Neexistuje žádný pár \( (x,y) \) a \( (y,x) \) s \( x \neq y \), tedy antisymetrie platí.
Tranzitivita:
Z \( (a,b) \in V \) a \( (b,c) \in V \) plyne \( (a,c) \in V \), platí.
Z \( (b,c) \in V \) a \( (c,d) \in V \) plyne \( (b,d) \in V \), platí.
Z \( (a,c) \in V \) a \( (c,d) \in V \) plyne \( (a,d) \in V \), platí.
Relace je reflexivní, antisymetrická a tranzitivní, tedy částečné uspořádání.
96. Nech je množina \( M = \{1, 2, 3, 4\} \) a relace \( R = \{(1,1), (2,2), (3,3), (4,4), (1,2), (2,3), (1,3), (3,4), (1,4)\} \). Určete, zda je \( R \) relací ekvivalence nebo částečným uspořádáním.
Řešení příkladu 96:
Reflexivita: Všechny prvky mají reflexivní páry, tedy relace je reflexivní.
Symetrie: Například \( (1,2) \in R \), ale \( (2,1) \notin R \), tedy symetrie neplatí.
Antisymetrie: Neexistuje žádný pár \( (x,y) \) a \( (y,x) \) s \( x \neq y \), antisymetrie tedy platí.
Tranzitivita: Z \( (1,2) \in R \) a \( (2,3) \in R \) plyne \( (1,3) \in R \), což platí. Dále \( (2,3) \in R \) a \( (3,4) \in R \) implikuje \( (2,4) \), který není v \( R \), ale můžeme ověřit, že tento pár není nutný pro tranzitivitu, protože \( (2,4) \notin R \) a zároveň \( (2,4) \notin R \), tranzitivita neplatí přímo, proto je potřeba zkontrolovat všechny další kombinace:
Z \( (1,3) \in R \) a \( (3,4) \in R \) plyne \( (1,4) \in R \), což platí.
Z chybějícího \( (2,4) \) však plyne, že relace není úplně tranzitivní, protože by měla obsahovat tento prvek pro úplnou tranzitivitu.
Z toho vyplývá, že relace není tranzitivní, a tedy není ani částečným uspořádáním ani relací ekvivalence.
97. Na množině \( X = \{a, b, c, d\} \) je relace \( S = \{(a,a),(b,b),(c,c),(d,d),(a,b),(b,a),(c,d),(d,c)\} \). Určete, zda je \( S \) relací ekvivalence, částečným uspořádáním, nebo jinou relací.
Řešení příkladu 97:
Reflexivita: Každý prvek má reflexivní pár, tedy \( S \) je reflexivní.
Symetrie: Pokud je \( (a,b) \in S \), je také \( (b,a) \in S \). Stejně pro \( (c,d) \) a \( (d,c) \). Symetrie platí.
Tranzitivita: Z \( (a,b) \in S \) a \( (b,a) \in S \) plyne \( (a,a) \in S \), což platí. Podobně pro ostatní prvky. Zkontrolujeme kombinace:
Z \( (a,b) \) a \( (b,a) \) plyne \( (a,a) \) – platí.
Z \( (c,d) \) a \( (d,c) \) plyne \( (c,c) \) – platí.
Žádné jiné kombinace, které by narušily tranzitivitu, neexistují.
Relace je reflexivní, symetrická a tranzitivní, tedy je relací ekvivalence.
Třídy ekvivalence jsou: \( \{a,b\} \) a \( \{c,d\} \).
98. Nechť \( T \) je množina všech přirozených čísel a relace \( R \) na \( T \) definovaná jako \( (x,y) \in R \Leftrightarrow x \mid y \) (tedy \( x \) dělí \( y \)). Určete, zda je \( R \) relací ekvivalence nebo částečným uspořádáním.
Řešení příkladu 98:
Reflexivita: Každé číslo dělí samo sebe, tedy \( R \) je reflexivní.
Symetrie: Pokud \( x \mid y \) a \( y \mid x \), pak \( x = y \), protože dělitelnost oběma směry znamená rovnost. Ale pro obecné \( x \neq y \) symetrie neplatí, například \( 2 \mid 4 \), ale \( 4 \nmid 2 \). Symetrie neplatí.
Antisymetrie: Pokud \( x \mid y \) a \( y \mid x \), pak \( x = y \), antisymetrie tedy platí.
Tranzitivita: Pokud \( x \mid y \) a \( y \mid z \), pak \( x \mid z \), tranzitivita platí.
Závěr: \( R \) je reflexivní, antisymetrická a tranzitivní, tedy částečné uspořádání na množině přirozených čísel podle dělitelnosti.
99. Mějme množinu \( M = \{1, 2, 3\} \) a relaci \( R = \{(1,1),(2,2),(3,3),(1,2),(2,1),(2,3),(3,2)\} \). Určete, zda je \( R \) relací ekvivalence, částečným uspořádáním nebo jiným typem relace.
Řešení příkladu 99:
Reflexivita: Pro všechny prvky existují reflexivní páry, takže reflexivita platí.
Symetrie: Například \( (1,2) \in R \) a \( (2,1) \in R \), \( (2,3) \in R \) a \( (3,2) \in R \), symetrie platí.
Tranzitivita: Zkontrolujeme, zda z \( (1,2) \) a \( (2,3) \) plyne \( (1,3) \). Ale \( (1,3) \notin R \), takže tranzitivita neplatí.
Relace není ekvivalence, protože chybí tranzitivita.
Relace není částečné uspořádání, protože není antisymetrická (existují symetrické páry s různými prvky).
Relace je tedy symetrická a reflexivní, ale ne tranzitivní, není ani ekvivalencí, ani částečným uspořádáním.
100. Na množině \( X = \{a,b,c,d\} \) je relace \( R = \{(a,a),(b,b),(c,c),(d,d),(a,b),(b,c),(a,c),(c,d),(a,d)\} \). Určete, zda je \( R \) relací ekvivalence nebo částečným uspořádáním.
Řešení příkladu 100:
Reflexivita: Každý prvek má reflexivní pár, tedy relace je reflexivní.
Symetrie: Například \( (a,b) \in R \), ale \( (b,a) \notin R \), symetrie neplatí.
Antisymetrie: Neexistují dvojice \( (x,y) \) a \( (y,x) \) s \( x \neq y \), tedy antisymetrie platí.
Tranzitivita: Z \( (a,b) \in R \) a \( (b,c) \in R \) plyne \( (a,c) \in R \), což platí.
Z \( (b,c) \in R \) a \( (c,d) \in R \) plyne \( (b,d) \), ale \( (b,d) \notin R \), tranzitivita neplatí.
Proto relace není tranzitivní, a tudíž není částečným uspořádáním ani relací ekvivalence.
