PLIN013, podzim 2010
Zadání: Studenti A a B jsou v relaci R, pokud A sedí ve stejné řadě jako
B nebo v některé řadě před ním. Je R ekvivalence? Je R uspořádání?
Řešení:
Označme r(x) = a fakt, že student x sedí v řadě a. Pak relaci R můžeme
zapsat jako množinu takto: R = {(a, b)|r(a) ≤ r(b)}. Postupně budeme ověřovat,
zda relace je reflexivní, symetrická, antisymetrická a tranzitivní.
Reflexivita: Zřejmě r(x) = r(x) (student sedí ve stejné řadě, ve které
sedí), tedy i r(x) ≤ r(x), takže (x, x) ∈ R pro všechny studenty x. Tedy R je
reflexivní.
Symetrie: Pro x, y zvolené tak, že r(x) = r(y) podmínka symetrie platí.
Pokud ale zvolíme x, y tak, že r(x) < r(y) (to můžeme pouze pokud alespoň
ve 2 řadách jsou nějací studenti), pak (x, y) ∈ R, ale (y, x) ∈ R (protože
r(y) ≤ r(x)). Tedy R není symetrická (pokud alespoň ve 2 řadách jsou nějací
studenti).
Antisymetrie: Pro x, y zvolené tak, že r(x) = r(y) ∧ x = y (to můžeme,
pokud alespoň v jedné řadě sedí víc než jeden student), platí (x, y) ∈ R ∧
(y, x) ∈ R ∧ x = y, což je v rozporu s podmínkou antisymetrie. Tedy R není
antisymetrická (pokud alespoň v jedné řadě sedí víc než jeden student).
Tranzitivita: Zvolme libovolné studenty x, y, z. Pokud (x, y) ∈ R ∧ (y, z) ∈
R, platí r(x) ≤ r(y) a r(y) ≤ r(z), tedy i r(x) ≤ r(z) a tedy i (x, z) ∈ R.
Tedy R je tranzitivní.
R není ekvivalence ani uspořádání (není symetrická ani antisymetrická).
1