====== AP1, IN1 Množiny a relace ======

===== Zadání =====
(zobrazení, funkce, rozklady a ekvivalence)

===== Vypracování =====
<note>Naivní pohled: Množina je soubor prvků a je svými prvky plně určena. Naivní pohled uvažuje jen konečné množiny.</note>
Množiny ale mohou být i prvky jiných množin. Množiny mohou pochopitelně mít i nekonečně mnoho prvků.
<box 95% round blue|Příklady>

<math>
M=\{a, b\} = \{b, a\} = \{a, b, a\};\ N=\{\{a\}\, ,\,\{b,c,d,e\} \}
</math>

<math>
a \in M;\ a \notin N;\ \{ a\} \notin M;\ \{ a\} \in N
</math>

<math>
\emptyset \in \{\emptyset\};\ \emptyset \notin \emptyset
</math>
</box>
<note>
V této souvislosti je dobré uvést také **Russelův paradox**

Fakt: Není pravda, že //každý soubor prvků// lze považovat za množinu.

<math>X=\{ M | M</math> je množina taková, že <math>M \not\in M\}</math>. Platí <math>X \in X</math>?
  * Ano. Tj. <math>X \in X</math>. Pak ale X splňuje <math>X \not\in X</math>.
  * Ne. Pak X splňuje vlastnost <math>X \not\in X</math>, tedy X je prvkem X, tj. <math>X \in X</math>.

Obě možné odpovědi vedou **ke sporu**. <math>X</math> tedy **nelze** prohlásit za množinu.
</note>

<note>
Právě tento a další paradoxy vedly na začátku 20. století ke vzniku **axiomatické teorie množin** (později ke vzniku více axiomatických teorií).
V takových axiomatizovaných teoriích množin obvykle nesmí množina obsahovat jiné prvky než zase jenom množiny a nic jiného.
</note>

==== Základní pojmy a definice ====
**Podmnožina:** <math>A \subseteq B\ \Leftrightarrow\ \forall x\in A:\, x \in A \Rightarrow x \in B</math>
**Vlastní podmnožina:** <math>A \subset B\ \Leftrightarrow\ A \subseteq B\, \wedge\, A \neq B</math>
**Sjednocení:** <math>A \cup B = \{ x\,\mid\, x \in A\,\vee\, x \in B \}</math>
**Průnik:** <math>A \cap B = \{ x\, \mid\, x \in A\, \wedge\, x \in B \}</math>
**Rozdíl:** <math>A \setminus B = \{ x\, \mid\, x \in A\,\wedge\, x \notin B \}</math>
**Doplněk:** Nechť <math>A\subseteq M\</math>. Doplněk A vzhledem k M je množina <math>B = M \setminus A</math>  
**Součin:** <math>A \times B = \{(a,b)\,\mid\, a \in A \wedge b \in B\}</math>
**Potenční množina:** Jedná se vlastně o množinu všech podmnožin. <math>2^{A}=\{ B\, \mid\, B \subseteq A\}</math>
<box 95% round blue|Příklady>

<math>
A=\{1,2,3\},\ B=\{3,4,5\},\ C=\{a,b\},\ D=\{1,2\}
D \subset A;\ D \subseteq A
</math>

<math>
A \cup B\,=\,\{1,2,3,4,5\}
</math>

<math>
A \cap B\,=\,\{3\}
</math>

<math>
A \setminus B\,=\,\{1,2\}
</math>

<math>
A \times C \,=\,\{(1,a),(1,b),(2,a),(2,b),(3,a),(3,b)\}
</math>

<math>
2^{C}\,=\,\{\emptyset,\{a\},\{b\},\{a,b\} \};\ 2^{\emptyset}\,=\,\{\emptyset\}
</math>
</box>

==== Relace ====
k-ární relace mezi <math>A_1, A_2,\ldots,A_k</math> je podmnožina součinu <math>A_1 \times A_2\times  \ldots \times A_k</math>. <math>2^{A_1 \times A_2 \times \ldots \times A_k}</math> je množina všech relací mezi <math>A_1,A_2,\ldots, A_k</math>. Pokud je <math>k=2</math> jedná se o binární relaci, pokud je <math>k=3</math>, jde o relaci ternární. 


**Složení relací:** Má smysl pouze u binárních relací a definováno následovně:

<math>
R\subseteq A\times B,\ S \subseteq B \times C:
</math>

<math>
S\circ R\, =\, \{(a,c)\,\mid\, \exists b \in B.\, (a,b)\in R\, \wedge\, (b,c)\in S\}
</math>

<box 95% blue round|Příklady>

<math>
A=\{1,2,3\};\ B=\{a,b,c\};\ C=\{x,y,z\}
</math>

<math>
R=\{(1,a),(1,b),(2,c),(3,a)\}\subseteq A\times B;\ S=\{(a,z),(b,x)\}\subseteq B\times C
</math>

<math>
R^{-1}=\{(a,1),(b,1),(c,2),(a,3)\}
</math>

<math>
S\circ R = \{(1,x),(1,z),(3,z)\}
</math>
</box>

==== Funkce a zobrazení ====
**(Totální) funkce** z <math>A</math> do <math>B</math> je relace <math>f \subseteq A\times B</math> kde pro každé <math>x\in A</math> existuje //právě jedno// <math>y\in B</math> takové, že <math>(x,y)\in f</math>.

<math>(x,y)\in f</math> je ekvivalentní zápisu <math>f(x)=y</math>. <math>A</math> je definiční obor, <math>B</math> je obor hodnot.


**Parciální funkce** z množiny <math>A</math> do množiny <math>B</math> je relace <math>f \subseteq A\times B</math> kde pro každé <math>x\in A</math> existuje //nejvýše jedno// <math>y\in B</math> takové, že <math>(x,y)\in f</math>.

  * Funkce <math>f</math> je injektivní (//prostá//) právě tehdy, když <math>\forall x,y\in A, x\neq y\ \Rightarrow \ f(x)\neq f(y)</math>.
  * Funkce <math>f</math> je surjektivní (//na//) právě tehdy, když <math>\forall y\in B. \exists x\in A.\, f(x)=y</math>.
  * Funkce <math>f</math> je bijektivní, jestliže je injektivní a surjektivní.

Tyto vlastnosti funkcí lze využít pro porovnávání velikostí jednotlivých množin a to i nekonečných:
  * <math>|A| \leq |B|</math> pokud existuje injekce <math>A \rightarrow B</math>.
  * <math>|A|=|B|</math> pokud existuje bijekce <math>A \rightarrow B</math>. - např. N, Q a Z jsou "stejně velké" (tzv. spočetně nekonečné)
  * <math>|A|<|B|</math> pokud existuje injekce <math>A \rightarrow B</math> ale neexistuje bijekce <math>A \rightarrow B</math>. - např. R je striktně větší než libovolná spočetná množina

==== Vlastnosti binárních relací ====
Pro následující definice budeme uvažovat <math>R \subseteq M \times M</math>.
  * Relace <math>R</math> je reflexivní právě tehdy, když <math>\forall a\in M:\, (a,a)\in R</math>.
  * Relace <math>R</math> je symetrická, pokud platí: <math> (a,b)\in R\, \Rightarrow\, (b,a)\in R</math>.
  * Relace <math>R</math> je antisymetrická, pokud platí: <math>(a,b)\in R\, \wedge\, (b,a)\in R \,\Rightarrow\, a=b</math>.
  * Relace <math>R</math> je tranzitivní, pokud platí: <math>(a,b)\in R\,\wedge\, (b,c)\in R\, \Rightarrow\, (a,c)\in R</math>.
  * Relace <math>R</math> je **ekvivalence**, pokud je reflexivní, symetrická a tranzitivní.
  * Relace <math>R</math> je **uspořádání**, pokud je reflexivní, antisymetrická a tranzitivní.

<box 95% blue round|Příklady>Buď <math>M</math> množina studentů FI. Uvažujme relace <math>R\subseteq M\times M</math> definované takto:
\\
  * <math>(x,y) \in R </math> právě když <math>x</math> má stejnou výšku jako <math>y</math>
  relace je reflexivní, symetrická a tranzitivní: jde o relaci ekvivalence.
  * <math>(x,y) \in R </math> právě když <math>x</math> má alespoň takovou výšku jako <math>y</math>
  tato relace je reflexivní a tranzitivní.
  * <math>(x,y) \in R </math> právě když <math>x</math> a <math>y</math> mají stejné rodné číslo
  tato relace je reflexivní, symetrická, antisymetrická a tranzitivní (je to tedy ekvivalence i uspořádání).
  * <math>(x,y) \in R </math> právě když <math>x</math> má jinou výšku než <math>y</math>
  tato relace je symetrická.
</box>

==== Rozklady a ekvivalence ====
Buď <math>M</math> množina. Rozklad na <math>M</math> je množina <math>N \subseteq 2^{M}</math> taková, že platí:

  * <math>\emptyset \notin N</math>
  * <math>A,B \in N \Rightarrow A \cap B = \emptyset\ \vee\ A=B</math>
  * <math>\bigcup_{A\in N}A = M</math>

Pokud chceme ověřit, že daná množina je rozklad na nějaké množině, musíme ověřit platnost výše uvedených tří podmínek.

<box 95% blue round|Příklad>

<math>
M=\{1,2,3,4,5,6,7,8,9\}
</math>

<math>
N=\{\{1,4\},\{2,7,8,9\},\{3\},\{5,6\} \};\ O=\{\{1,4\},\{2,7,8,9\},\{3,4\},\{5,6\} \}
</math>

<math>N</math> je rozklad na <math>M</math>, ale <math>O</math> rozklad na <math>M</math> není (nemůže být rozkladem ani na žádné jiné množině -- viz 2. podmínka pro rozklad).
</box>

Každý rozklad <math>N</math> určuje jistou ekvivalenci <math>R_N</math> na množině <math>M</math> a to následovně:

<math>(x,y)\in R_N\ \Leftrightarrow\ \exists A\in N.\, x,y \in A</math>

Takto definovaná relace <math>R_N</math> splňuje všechny požadavky na relaci ekvivalence. Je tedy reflexivní, symetrická a tranzitivní. Toto je možné ověřit důkazem ((Slidy IB000 Úvod do informatiky, podzim 2005, slide č. 46)).

<box 95% blue round|Příklad><math>
M=\{1,2,3,4\};\ N=\{\{1,3,4\},\{2\}\}
</math>

<math>
R_N=\{(1,1),(1,3),(1,4),(3,3),(3,1),(3,4),(4,4),(4,1),(4,3),(2,2)\}
</math>
</box>

Každá ekvivalence <math>R</math> určuje jistý rozklad <math>M/R</math> na <math>M</math>:
  * <math>[x] = \{y\in M\, \mid\, (x,y)\in R \}</math>\\
  * <math>M/R = \{ [x]\, \mid\, x \in M\}</math>
Takto definovaný rozklad splňuje všechny požadavky na rozklad (viz výše). Toto je opět možné dokázat ((Slidy IB000 Úvod do informatiky, podzim 2005, slide č. 47-48)).

<box 95% blue round|Příklad><math>M=\{1,2,3,4\};\ </math>




Buď <math>R=\{(1,1),(1,2),(2,1),(2,2),(3,3),(4,4)\}</math> ekvivalence na <math>M</math>. Potom:
<math>
M/R=\{\{1,2\},\{3\},\{4\} \}
</math>
</box>

===== Co byste ještě měli znát? =====

  * Měli byste také znát, kde se využívá ekvivalence.


===== Předměty =====
  * [[https://is.muni.cz/auth/predmety/predmet.pl?obdobi=3082;kod=IB000|FI:IB000]] Úvod do informatiky (podzim 2005), prof. RNDr. Antonín Kučera, Ph.D.

===== Použitá literatura =====
  * prof. RNDr. Antonín Kučera, Ph.D., slidy z přednášek předmětu IB000 Úvod do informatiky. Tyto slidy nejsou v současné době již dostupné na osobním webu prof. Kučery. Jako alternativa se nabízejí materiály doc. RNDr. Petra Hliněného, Ph.D. dostupné [[http://www.fi.muni.cz/~hlineny/Vyuka/UINF/|zde]]. 

  * [[http://www.fi.muni.cz/~hlineny/Vyuka/UINF/UInf-text06.pdf|Úvod do informatiky, doc. RNDr. Petr Hliněný]] -- v kapitole 11 jsou hezky popsány Nekonečné množiny a zastavení algoritmu

===== Vypracoval =====

Honza Palas, UČO: 172760
Z mé strany na 99% hotovo, pokud vás napadne něco doplnit, samozřejmě můžete.

Otázku si přečetl pan RNDr. Jan Bouda a rámcově prošel. Jeho podněty pro doplnění textu, opravy nesrovnalostí a odstranění matoucích či k otázce se nevztahujících textů byly do otázky zaneseny. Tato kontrola je jen **rámcová**, stále se může stát, že v otázce zůstala zapomenutá chybka či nesrovnalost, vyučující za toto nenese odpovědnost, berte tuto rámcovou kontrolu jako formu pomoci od vyučujících pro studenty.

~~DISCUSSION~~