Obsah

AP1, IN1 Množiny a relace
Diskuze

AP1, IN1 Množiny a relace

Zadání

(zobrazení, funkce, rozklady a ekvivalence)

Vypracování

Naivní pohled: Množina je soubor prvků a je svými prvky plně určena. Naivní pohled uvažuje jen konečné množiny.

Množiny ale mohou být i prvky jiných množin. Množiny mohou pochopitelně mít i nekonečně mnoho prvků.

Příklady

$M=\{a, b\} = \{b, a\} = \{a, b, a\};\ N=\{\{a\}\, ,\,\{b,c,d,e\} \}$

$a \in M;\ a \notin N;\ \{ a\} \notin M;\ \{ a\} \in N$

$\emptyset \in \{\emptyset\};\ \emptyset \notin \emptyset$

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.

$X=\{ M | M$ je množina taková, že $M \not\in M\}$ . Platí $X \in X$ ?

Ano. Tj. $X \in X$ . Pak ale X splňuje $X \not\in X$ .
Ne. Pak X splňuje vlastnost $X \not\in X$ , tedy X je prvkem X, tj. $X \in X$ .

Obě možné odpovědi vedou ke sporu. $X$ tedy nelze prohlásit za množinu.

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.

Základní pojmy a definice

Podmnožina: $A \subseteq B\ \Leftrightarrow\ \forall x\in A:\, x \in A \Rightarrow x \in B$ Vlastní podmnožina: $A \subset B\ \Leftrightarrow\ A \subseteq B\, \wedge\, A \neq B$ Sjednocení: $A \cup B = \{ x\,\mid\, x \in A\,\vee\, x \in B \}$ Průnik: $A \cap B = \{ x\, \mid\, x \in A\, \wedge\, x \in B \}$ Rozdíl: $A \setminus B = \{ x\, \mid\, x \in A\,\wedge\, x \notin B \}$ Doplněk: Nechť $A\subseteq M\$ . Doplněk A vzhledem k M je množina $B = M \setminus A$ Součin: $A \times B = \{(a,b)\,\mid\, a \in A \wedge b \in B\}$ Potenční množina: Jedná se vlastně o množinu všech podmnožin. $2^{A}=\{ B\, \mid\, B \subseteq A\}$

Příklady

$A=\{1,2,3\},\ B=\{3,4,5\},\ C=\{a,b\},\ D=\{1,2\} D \subset A;\ D \subseteq A$

$A \cup B\,=\,\{1,2,3,4,5\}$

$A \cap B\,=\,\{3\}$

$A \setminus B\,=\,\{1,2\}$

$A \times C \,=\,\{(1,a),(1,b),(2,a),(2,b),(3,a),(3,b)\}$

$2^{C}\,=\,\{\emptyset,\{a\},\{b\},\{a,b\} \};\ 2^{\emptyset}\,=\,\{\emptyset\}$

Relace

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

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

$R\subseteq A\times B,\ S \subseteq B \times C:$

$S\circ R\, =\, \{(a,c)\,\mid\, \exists b \in B.\, (a,b)\in R\, \wedge\, (b,c)\in S\}$

Příklady

$A=\{1,2,3\};\ B=\{a,b,c\};\ C=\{x,y,z\}$

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

$R^{-1}=\{(a,1),(b,1),(c,2),(a,3)\}$

$S\circ R = \{(1,x),(1,z),(3,z)\}$

Funkce a zobrazení

(Totální) funkce z $A$ do $B$ je relace $f \subseteq A\times B$ kde pro každé $x\in A$ existuje právě jedno $y\in B$ takové, že $(x,y)\in f$ .

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

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

Funkce $f$ je injektivní (prostá) právě tehdy, když $\forall x,y\in A, x\neq y\ \Rightarrow \ f(x)\neq f(y)$ .
Funkce $f$ je surjektivní (na) právě tehdy, když $\forall y\in B. \exists x\in A.\, f(x)=y$ .
Funkce $f$ 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:

$|A| \leq |B|$ pokud existuje injekce $A \rightarrow B$ .
$|A|=|B|$ pokud existuje bijekce $A \rightarrow B$ . - např. N, Q a Z jsou „stejně velké“ (tzv. spočetně nekonečné)
$|A|<|B|$ pokud existuje injekce $A \rightarrow B$ ale neexistuje bijekce $A \rightarrow B$ . - 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 $R \subseteq M \times M$ .

Relace $R$ je reflexivní právě tehdy, když $\forall a\in M:\, (a,a)\in R$ .
Relace $R$ je symetrická, pokud platí: $(a,b)\in R\, \Rightarrow\, (b,a)\in R$ .
Relace $R$ je antisymetrická, pokud platí: $(a,b)\in R\, \wedge\, (b,a)\in R \,\Rightarrow\, a=b$ .
Relace $R$ je tranzitivní, pokud platí: $(a,b)\in R\,\wedge\, (b,c)\in R\, \Rightarrow\, (a,c)\in R$ .
Relace $R$ je ekvivalence, pokud je reflexivní, symetrická a tranzitivní.
Relace $R$ je uspořádání, pokud je reflexivní, antisymetrická a tranzitivní.

Příklady

Buď $M$ množina studentů FI. Uvažujme relace $R\subseteq M\times M$ definované takto:

$(x,y) \in R$ právě když $x$ má stejnou výšku jako $y$

relace je reflexivní, symetrická a tranzitivní: jde o relaci ekvivalence.

$(x,y) \in R$ právě když $x$ má alespoň takovou výšku jako $y$

tato relace je reflexivní a tranzitivní.

$(x,y) \in R$ právě když $x$ a $y$ mají stejné rodné číslo

tato relace je reflexivní, symetrická, antisymetrická a tranzitivní (je to tedy ekvivalence i uspořádání).

$(x,y) \in R$ právě když $x$ má jinou výšku než $y$

tato relace je symetrická.

Rozklady a ekvivalence

Buď $M$ množina. Rozklad na $M$ je množina $N \subseteq 2^{M}$ taková, že platí:

$\emptyset \notin N$
$A,B \in N \Rightarrow A \cap B = \emptyset\ \vee\ A=B$
$\bigcup_{A\in N}A = M$

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.

Příklad

$M=\{1,2,3,4,5,6,7,8,9\}$

$N=\{\{1,4\},\{2,7,8,9\},\{3\},\{5,6\} \};\ O=\{\{1,4\},\{2,7,8,9\},\{3,4\},\{5,6\} \}$

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

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

$(x,y)\in R_N\ \Leftrightarrow\ \exists A\in N.\, x,y \in A$

Takto definovaná relace $R_N$ splňuje všechny požadavky na relaci ekvivalence. Je tedy reflexivní, symetrická a tranzitivní. Toto je možné ověřit důkazem ¹⁾.

Příklad

$M=\{1,2,3,4\};\ N=\{\{1,3,4\},\{2\}\}$

$R_N=\{(1,1),(1,3),(1,4),(3,3),(3,1),(3,4),(4,4),(4,1),(4,3),(2,2)\}$

Každá ekvivalence $R$ určuje jistý rozklad $M/R$ na $M$ :

$[x] = \{y\in M\, \mid\, (x,y)\in R \}$
$M/R = \{ [x]\, \mid\, x \in M\}$

Takto definovaný rozklad splňuje všechny požadavky na rozklad (viz výše). Toto je opět možné dokázat ²⁾.

Příklad

$M=\{1,2,3,4\};\$

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

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

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

Předměty

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é zde.

Ú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.

¹⁾

Slidy IB000 Úvod do informatiky, podzim 2005, slide č. 46

²⁾

Slidy IB000 Úvod do informatiky, podzim 2005, slide č. 47-48