The Postal Owl

> 1. $X = \N, p\in\N$, $(x,y)\in R \iff p\text{ dělí }(x-y)$

Dokažme, že je relace reflexivní, tranzitivní a symetrická:

- Reflexivní:
$\forall x,p \in \N: p|0 \implies xRx$

- Symetrická: 
$xRy {\implies} p|(x-y) \implies p|((-1)(y-x))$  
Pokud je číslo $a$ dělitelné číslem $b$, pak je dělitelné stejným číslem i $-a$:  
$b|a \implies \exists k \in \Z \setminus \{0\}: a = k \cdot b \implies \exists k \in \Z \setminus \{0\}: -a = -k \cdot b  \implies b|-a$.  
Takže: 
$p|((-1)(y-x)) \implies p|(y-x) \implies yRx$  

- Tranzitivní:
Rozdělme důkaz na dvě části (důvod se odhalí později).
1. $\forall x,y,z, x = y,  xRz \wedge zRy$  
Platí nezávisle na, že $xRx$  
$xRx \implies xRy$

2. $\forall x,y,z, x \neq y,  xRz \wedge zRy$  
$\implies p|(x-z) \wedge p|(z-y) \implies \exist k,l \in \Z  \setminus\{0\}: x-z = k \cdot p \wedge z-y = l \cdot p$  
$z= l \cdot p + y$  
$x-(l \cdot p + y) = k \cdot p$  
$x- y= k \cdot p +  l \cdot p =  (k+l) \cdot p$  
Ještě ukažme, že $k + l \neq 0$:  
$z= l \cdot p + y$  
$z= x - k \cdot p$  
$l \cdot p + y = x - k \cdot p$  
$l \cdot p + k \cdot p = x - y$  
$(l + k)  = \frac{x - y}{p}$  
Ale $x \neq y \implies x - y \neq 0 \implies l+k \neq 0$  
No a pro dokončení důkazu:
$x - y=   (k+l) \cdot p \wedge k + l \in \Z \setminus \{0\} \implies p|x-y \implies xRy$

- Rozdělení na třídy:  
Dalo by se říci, že aby prvky x y byly v relaci, musí p dělit jejich vzdálenost, protože ta může nabývat hodnot buď $x-y$ nebo $y-x$ a pokud $p$ dělí jedno, dělí i druhé (stačí vytknout minus jedničku jako u symetrie výše). Můžou tedy nastat dva případy, buď p dělí vzdálenost, nebo nedělí, takže budou dvě třídy ekvivalence. Možná není ani potřeba tuto vzdálenost zavádět, byla by nápomocná v případném výčtu tříd ekvivalence.

  
> 2. $X = \Z \setminus \{0\}$, $(x,y)\in R \iff x\text{ dělí }y \text{ a zároveň
> } y\text{ dělí }x$

$x|y \implies \exists a \in \Z \setminus \{0\}: y = a \cdot x$  

$y|x \implies \exists b \in \Z \setminus \{0\}: x = b \cdot y$  

Dosazením dostáváme:  
$x = b \cdot (a \cdot x)$  
$1 = ab$  
Protože jsou ale $a$ i $b$ celá čísla, nastávají jenom dvě možnosti:  
$a = b = 1$  nebo $a = b = -1$

Takže buď $x = -y$ nebo $x = y$

Ukázal jsem, že $x = |y| \iff xRy$

Teď dokažme, že je relace ekvivalencí:
+ Reflexe
$\forall x: x|x  \implies xRx$

+ Symetrie  
Pokud $x=y$, platí reflexně.
Pokud $x=-y$, $x|(-1)y \implies x|-y$ a stejně obráceně.

+ Tranzitivita
$\forall x, y, z: xRy \wedge yRz$ platí $x=-y$ nebo $x=y$  
Taky platí, že $z=-y$ nebo $z=y$
Pokud
1. $x=-y$  
a)$z=-y \implies x=z$  
b)$z=y \implies x=-z$
2. $x=y$  
a)$z=-y \implies x=-z$  
b)$z=y \implies x=z$
Takže $x=-z$ nebo $x=z$   
$\implies xRz$

+ Rozdělení na třídy:

$x \in [a]_R \text{ kde } a > 0 \implies a = |x|$  
Mohli bychom rozdělit množinu podle absolutní hodnoty, ta může nabývat libovolných hodnot, tudíž je i nekonečně mnoho ekvivalenčních tříd. V každé z nich jsou pak právě dva prvky, protože pro každe $a > 0$ existují dva prvky, pro které platí $|x| = a$, a sice $x$ a $-x$




> 3. $X = \N$, $(x,y)\in R \iff \exists z\in\N$, že $z$ dělí $x$ i $y$
Relace je:

- reflexivní:
$x|x \implies xRx$

- symetrická
$xRy \implies \exists z\in \N: z|x \wedge z|y \implies yRx$

- tranzitivní:
$\forall x,y,z: 1|x \wedge 1|y \wedge 1|z \implies \text{ každá možná dvojice je v relaci}$ 

Relace splňuje definici, takže je ekvivalencí, ekvivalenční třída je jen jedna a obsahuje všechny prvky, protože každé dva prvky mají společného dělitele jedničku.

> 4. $X = \Z\times(\Z \setminus\{0\})$, $((a,b),(c,d))\in R \iff \frac{a}{b} =
> \frac{c}{d}$

Zkopíruji důkaz z jiného příkladu z OWLU (který jsem psal také já):

dokažme, že je relace reflexivní, tranzitivní a symetrická:

Pojmenujme $X= \Z\times(\Z \setminus\{0\})$

- Reflexivní:
$\forall (x,y) \in X: \frac{x}{y} = \frac{x}{y} \implies (x,y)R(x,y)$

- Symetrická: 
$(u,w)R(x,y) \underset{def.}{\implies} \frac{u}{w} = \frac{x}{y} \implies \frac{x}{y} = \frac{u}{w} \implies (x,y)R(u,w)$

- Tranzitivní:
$\forall (a,b),(c,d),(e,f); (a,b)R(c,d) \wedge (c,d)R(e,f) \implies \frac{a}{b} = \frac{c}{d} \wedge \frac{c}{d} = \frac{e}{f} \implies \frac{a}{b} = \frac{e}{f} \implies (a,b)R(e,f)$


Tříd ekvivalence bude nekonečně mnoho, pro každou dvojci vzájemně nesoudělných *přirozených* čísel $a$,$b$ budou tyto třídy čtyři, a sice $[(a,b)]_R$,  $[(b,a)]_R$, $[(-a,b)]_R$,  $[(-b,a)]_R$. Pro každou ostatní dvojci čísel bude možné jejich zlomek zkrátit, nebo bude záporný, nebo půjde zkrátit a k tomu bude záporný, každopádně nám vyjde kladný nebo záporný zlomek dvou nesoudělných čísel, pro který už máme třídu. Poslední třídou bude třída pro všechny dvojce  $(a,b) \in X$, kde $a = 0$, hodnota jejichž zlomku bude rovná nule.