# Domácí úkoly 2
## Rn
### 1.
Obecně platí, že je-li $R$ relací na množině $X$, pak $R \subseteq X\times X$, čili může obsahovat nejvýše $|X|^{2}$ uspořádaných dvojic. Při skládání pak platí $|R \circ R| \leq |X\times X|$, jelikož obě skládané relace obsahují prvky ze stejné množiny ($X$) a tedy nemohou vzniknout žádná jiná "propojení" než obsahuje samotný kartézský součin. Tím pádem je počet relací definitivně omezen, a jelikož hodnoty $r$ ani $s$ nejsou nijak omezeny, při opakovaném skládání se začnou relace opakovat, byť neperiodicky (nebo vzniknou prázdné množiny, které se také rovnají).
### 2.
Je-li $R$ relace na nekonečné množině (a tedy i sama relace může být nekonečná), pak lze relaci složit tak, že výsledná relace bude obsahovat o několik dvojic méně, ale jelikož je nekonečná, tak při opakovaném skládání nelze počet jejích prvků vyčerpat. Příkladem je binární relace $>$ na množině $\mathbb Z$ - vždy bude existovat dvojice $(n+1;0)$, kterou složím přes $(n+1;1)$$(\in R^n)$ a $(1;0)$$(\in R^1)$, ale dvojice $(n;1)$ již v následující relaci existovat nebude. Dalo by se to zapsat i jako $((n+1)RnR(n-1)R(n-2)\dots R1R0)$, kde počet "$R$" v závorce je roven $(n+1)$.
## Reflex
### 1. $R \cup S$
$R \cup S$: každý prvek byl v relaci sám se sebou, při sjednocení se žádná relace neztrácí - platí
### 2. $R \cap S$
$R \cap S$: Obsahují li relace $R$ i $S$ stejnou dvojici, pak musí být oba prvky této dvojice v relaci samy se sebou v obou relacích (což platí právě tehdy, když jsou reflexivní). Pokud ne, pak je průnikem prázdná množina, která je také reflexivní.
### 3. $R \setminus S$
$R = \{(x,x)(x,y)(y,y)\}$, $S = \{(x,x)(y,y)\}$, $R\setminus S = \{x,y\}$, tzn. relace $R$ může obsahovat dvojici, která není reflexivní, tvrzení neplatí.
### 4. $R^{-1}$
Také bude reflexivní - pokud v jednotlivých uspořádaných dvojicích přehodíme pořadí prvků, u reflexivních dvojic se nic nezmění.

### 5. $R \circ S$ (blbě jsem přečetl zadání)
Pokud obě "pravidla" složené relace umožňují zavést dvojici stejných prvků, pak lze tento prvek použít i jako "prostřední" prvek nutný pro podmínku existence dané dvojice ve složené relaci (tedy $xRxSx$).
## Tranzit

### 1. $R \cup S$
Nová relace nemůže obsahovat trojici, pro kterou by tranzitivita neplatila, takže výsledná relace bude také tranzitivní.
### 2. - 4. $R \cap S$, $R \setminus S$, $R \triangle S$ xxx Ověřit
Pokud nějaká z dvojic $(x,y)$ existuje v obou relacích, pak je k ní možno vytvořit dvojice $(x,r)(y,r)$ v relaci $R$ a dvojice $(x,s)(y,s)$ v relaci $S$, přitom však nemusí platit $r = s$ (takže tyto dvojice v průniku nebudou). Každá z výše uvedených operací tak může dát vzniknout netranzitivní relaci.

### 5. $R \circ S$
Složením dvou tranzitivních relací nemusí vzniknout tranzitivní relace, jelikož v elementárním případě $R = S$ onen prostřední prvek (v tomto případě prvek $y$ - z $R = S = (x,y), (y,r), (x,r)$ vznikne $R \circ S$ = ${(x,r)}$ ) se ve výsledné složené relaci nenachází.
### 6. $R^{-1} \circ S^{-1}$
Ne
### 7. $R^{-1}$
Ano - převrátí se všechny vztahy, u kterých platí tranzitivita

## Ekv
### a) (přirozené číslo p dělí (x-y))
Předpokládám, že číslo $p$ je zvolené předem.
Nula je dělitelná - relace je reflexivní
U záporných celých čísel se dá určit dělitelnost - relace je symetrická
Je-li $x - y$ dělitelné $p$, pak další dělitelný rozdíl vytvoříme tak, že k menšiteli přičteme $kp$ ($k \in \mathbb{Z}$), takže $x - (y + kp)$ bude dělitelné $p$, a $y - (y + np) = -np$ - tzn. $(y + np)$ je "třetí člen" nutný pro tranzitivitu relace.
Relace je tedy ekvivalencí, přičemž ji můžeme rozdělit na $p$ tříd jako aritmetické posloupnosti s diferencí $p$ (pro $p=4$ je první třídou ${1,5,9}$, druhou ${2,6,10}$...)
### b) (x|y $\land$ y|x )
Tato situace může nastat pouze v případě, že $|x| = |y|$.
Každá třída pak obsahuje dva prvky - kladnou a zápornou hodnotu téhož čísla.
### c) Existuje společný dělitel čísel x, y
Ano, relace bude ekvivalencí, ale má jen jednu třídu, jelikož každé číslo je dělitelné jedničkou.
### d) Zlomky vytvořené z čísel (a,b,c,d) se rovnají
Nejedná se o ekvivalenci - nula není v relaci sama se sebou