Zpět na stránku cvika

3. cvičení

Relace

Dnes budeme pokračovat příklady, které se minule nestihly. Ještě se zběžně podíváme na relace obecně, a potom se budeme věnovat dvěma specifickým třídám relací – ekvivalencím a uspořádáním.

Příklad 1. Nechť $X$ je konečná množina a $R$ a $S$ nechť jsou relace na této množině. Rozhodněte, zda platí tvrzení: "Má-li $R$ i $S$ vlastnost $V$, pak i $R \oplus S$ má vlastnost $V$" pro $V \in \{\text{reflexivní, tranzitivní,}$ $\text{symetrická}\}$ a $\oplus \in \{\cap,\cup,\setminus,\operatorname{\triangle},\circ,^{-1}\}$. $\triangle$ je symetrický rozdíl, tedy $A \operatorname{\triangle} B = (A \setminus B) \cup (B \setminus A)$

$R\cap S$ $R \cup S$ $R \setminus S$ $R \operatorname{\triangle} S$ $R\circ S$
reflexivní
symetrická
antisymetrická
tranzitivní

Zobraz částečné řešení Skryj řešení

Ukážeme zde důkazy pro 3 konkrétní výroky, na nichž demonstrujeme, jak se mohou tvrzení tohoto typu obecně dokazovat.

  1. Nechť jsou relace $R$ a $S$ reflexivní. Ukážeme, že $R\cup S$ je také reflexivní.
    2. Vzhledem k tomu, že pro každé $x\in X$ platí $(x,x) \in R$ z reflexivity $R$, je také pro každé $x\in X$ $(x,x)\in R\cup S$. $R\cup S$ je tedy reflexivní.
  2. Nechť jsou relace $R$ a $S$ tranzitivní. Ukážeme, že relace $R \cup S$ tranzitivní být nemusí.
    3. Nechť $X=\{1,2,3\}$, $R = \{(1,2)\}$, $S = \{(2,3)\}$. Pak $(1,2)\in R\cup S$ a $(2,3) \in R\cup S$, ale $(1,3)\notin R\cup S$, což znamená, že $R\cup S$ tranzitivní není.
  3. Nechť jsou relace $R$ a $S$ antisymetrické. Ukážeme, že relace $R \setminus S$ bude také antisymetrická.
    4. Antisymetrie je nadefinována tak, že relace je antisymetrická, pokud $\forall (x,y) \in R: x=y \vee (y,x) \notin R$. To znamená, že pokud budeme z $R$ dvojice pouze odstraňovat, nikdy nemůžeme antisymetrii porušit – k žádné "šipce" nevytvoříme "šipku" opačnou, protože žádné šipky netvoříme. Proto obecně platí, že pokud $R$ je antisymetrická, tak každé $R'\subseteq R$ také. No a protože $R\setminus S\subseteq R$, je $R\setminus S$ antisymetrické.

Ekvivalence

Příklad 2. Rozhodněte, zda jsou následující relace na množině $X$ ekvivalence. Pokud ano, popište třídy ekvivalence.

O číslu $a\in \mathbb Z\setminus\{0\}$ řekneme, že dělí $b \in \mathbb Z$, právě pokud $b/a \in \mathbb Z$. "$a$ dělí $b$" můžeme také zapsat jako "$a\mid b$".
  1. $X = \mathbb N$, $p$ je dané přirozené číslo, $(a,b) \in R \Leftrightarrow p\mid(a-b)$.
  2. $X = \mathbb Z \setminus \{0\}$, $(a,b) \in R \Leftrightarrow a \mid b \wedge b\mid a$.
  3. $X = \mathbb N$, $(a,b) \in R \Leftrightarrow a \mid b \vee b\mid a$.
  4. $X = \mathbb N$, $(a,b) \in R \Leftrightarrow \exists c\in \mathbb N: c \mid b \wedge c\mid a$.
  5. $X = \mathbb N$, $(a,b) \in R \Leftrightarrow \exists c > 1\in \mathbb N: c \mid b \wedge c\mid a$.
  6. $X = \mathbb Z\times(\mathbb Z \setminus \{0\})$, $((a,b),(c,d)) \in R \Leftrightarrow \frac ab = \frac cd$.
  7. $X = \mathcal P(\mathbb N)$, $(a,b)\in R \Leftrightarrow \text{Existuje bijekce z $a$ do $b$}$.
  8. $X = \text{Množina všech přímek v rovině}$, $(a,b)\in R \Leftrightarrow \text{$a$ a $b$ jsou rovnoběžné}$.

Uspořádání

Definice. Mějme relaci $R$ na množině $X$ a relaci $S$ na množině $Y$. Řekneme, že relace $R$ a $S$ jsou izomorfní,, právě když existuje bijektivní funkce $f:X\rightarrow Y$, taková, že $\forall a,b\in X: aRb\Leftrightarrow f(a)Sf(b)$. Funkci $f$ nazveme izomorfismus. Jinými slovy, relace $R$ je izomorfní s relací $S$, pokud jsou až na přejmenování prvků stejné.

Příklad 3. Ukažte, že všechna lineární uspořádání na dané konečné množině jsou izomorfní. Všimněte si, že pro částečná uspořádání již toto tvrzení neplatí.

Příklad 4. Jak dlouhý je nejdelší řetězec v relaci $(\mathcal P(\{1,\dots,n\}),\subseteq)$? Máte-li hotové všechny ostatní příklady, můžete zkusit najít i nejdelší antiřetězec jako hvězdičkový příklad.

Příklad 5. O následujících relacích na $\mathbb N^2$ rozhodněte, zda jsou částečné uspořádání. Které z nich jsou také lineárními uspořádáními?

  1. $(a,b) \preceq_a (x,y) \Leftrightarrow a \leq x \wedge b \leq y$
  2. $(a,b) \preceq_b (x,y) \Leftrightarrow a \leq x \vee b \leq y$
  3. $(a,b) \preceq_c (x,y) \Leftrightarrow a < x \vee (a = x \wedge b \leq y)$ (tzv. lexikografické uspořádání)
  4. $(a,b) \preceq_d (x,y) \Leftrightarrow \max(a,b) > \max(x,y) \vee (\max(a,b) = \max(x,y) \wedge \min(a,b) \leq \min(x,y))$
  5. $(a,b) \preceq_e (x,y) \Leftrightarrow \max(a,b) > \max(x,y) \vee (\max(a,b) = \max(x,y) \wedge (a,b) \preceq_c (x,y))$

Příklad 6. Na vhodné (ne nutně vždy stejné; ne nutně konečné) množině najděte částečné uspořádání, které bude mít:

  1. Žádný maximální nebo minimální prvek.
  2. Alespoň jeden maximální prvek, ale žádný největší.
  3. Právě jeden maximální prvek, ale žádný největší.
  4. Nekonečno maximálních prvků, ale pouze konečno minimálních.

Příklad 7. Mějme částečně uspořádanou množinu o $n$ prvcích. Nechť $r$ je délka jejího nejdelšího řetězce a $a$ délka nejdelšího antiřetězce. Z věty o dlouhém a širokém víme, že $r\cdot s$ je alespoň $n$. Umíte pro $r\cdot s$ pouze ze znalosti $n$ určit i nějakou horní mez?