Santa Claus — modified 2021-10-14 23:25 (447 days ago) — edit — reply
> 1. Dokažte, že je-li $X$ konečná množina, potom existují $r,s \in \mathbb{N}, r < s$ takové, že $R^r = R^s$.
Platí $R \subseteq X \times X$
Také platí, že $\forall n \in \N: R^n \subseteq X \times X$, dokažme to indukčně:
$R^n \subseteq X\times X$
Předpokládejme že věta platí pro $n$.
$xR^{n+1}y \implies \exists z: xRz \wedge zR^ny$
Ale $xRz \implies x \in X$ a $zR^ny \implies y \in X$
A $(x \in X \wedge y \in X) \implies (x,y) \in X\times X$
Pro $n = 1$ věta platí, protože $R^1 = R$, a $R$ je definována jako relace na $X$
Takže jsme ukázali, že pokud věta platí pro $n$, platí $xR^{n+1}y \implies (x,y) \in X\times X$, takže platí i pro $n+1$, takže platí pro každé $n$.
Jestliže je ale každá z těchto relací podmnožinou stejné konečné množiny, může nabývat pouze hodnot z potenční množiny $P(X \times X)$. Tato potenční množina ale musí být také konečná, protože počet možných permutací konečného počtu prvku je také konečný (to bychom mohli dokázat snadno třeba indukcí, ale je to trivialní).
Jestliže relace $R^n$ může nabývat konečného počtu hodnot, pak $\exists m \in \N$ takové, že $m$ je větší než velikost potenční množiny, potom ale nemůžou být všechny relace $R^n$ $n \leq m$ různé, protože jinak by musela být velikost potenční množiny alespoň rovna $m$, ale to je spor.
> 2. Nalezněte relaci na nekonečné množině takovou, že všechny $R^n$ jsou různé -- tedy předchozí bod pro nekonečné množiny neplatí.
Uvažme relaci $R$ na množině $\N$, takovou, že $R = \{(x,y): 2x = y\}$
Pro $R^n$ bude platit, že $R^n = \{(x,y): 2^nx = y\}$
Důkaz (můj oblíbený - indukcí):
Pro $n = 1$ věta platí, protože
$R^1 = R = \{(x,y): 2x = y\} = \{(x,y): 2^1x = y\}$
Předpokládejme, že věta platí pro $n$, a ukažme, že platí pro $n+1$
$xR^{n+1}y \implies \exist z: xRz \wedge zR^ny \implies 2x = z \wedge 2^nz = y \underset{dosazením}{\implies} 2^n2x = y \implies 2^{n+1}x = y$
Takže věta platí.
Ale v tom případě bude v každé $R^n$ dvojice $(1, 2^n)$, která bude pro každá dvě různá $n$ různá, takže se všechny relace budou lišit minálně těmito dvěma dvojcemi.