\input /home/pasky/school/fastex/lib.tex

\subchapter{Množiny}{

	\shortdef{Množina}{soubor prvků.}

	\scpart{Zápis:}{
	\list{
		\olistItem{výčtem prvků: $X = \{a,b,c\}$}
		\olistItem{vlastností: $X = \{i\in\nat: \existss j\in\nat,\ i=j\}$}
	}
	}

	$$ X = Y \Leftrightarrow (x \in X \Leftrightarrow x \in Y)\qquad \forall x $$

	Je-li $X$ konečná, $|X| \Leftrightarrow {\rm len}(X)$ (velikost, mohutnost).

	$$ X \subseteq Y \Leftrightarrow (x \in X \Rightarrow x \in Y)\qquad \forall x $$

	\shortdef{$P(X)$}{Potenční množina množiny $X$ --- množina všech podmnožin množiny $X$
		(včetně $\emptyset$ a $X$). Je-li $X$ konečná, $|P(X)|=2^{|X|}$.}

	\shortdef{Symbolika}{$|X| \cap |Y|$, $|X| \cup |Y|$, $|X| \setminus |Y|$, \dots}

}


\subchapter{Relace}{

	\shortdef{Neuspořádaná dvojice}{$\{x,y\}$}
	\shortdef{Uspořádaná dvojice}{$(x,y)$: $(x,y) = (x',y') \Leftrightarrow (x=x' \et y=y')$; např. $\{\{x\},\{x,y\}\}$}

	\shortdef{Kartézský součin}{$ X \times Y = \{(x,y): x\in X,\ Y \in Y\} $}

	\shortdef{Relace $R$ mezi $X$, $Y$}{$R \subseteq X \times Y$}
	\shortdef{Relace $R$ na $X$}{$R \subseteq X \times X$}

	\shortdef{Značení}{$(x,y) \in \real$: $xRy$ (jde-li o binární relaci)}

	\definition{
		Relace $R$ na množině $X$ je:
		\list{
			\olistItem{{\bf reflexivní:} $xRx\qquad \forall x \in X: xRx$}
			\olistItem{{\bf symetrická:} $xRy \Rightarrow yRx\qquad \forall x,y \in X$}
			\olistItem{{\bf tranzitivní:} $(xRy \et yRz) \Rightarrow xRz\qquad \forall x,y,z \in X$}
			\olistItem{{\bf ekvivalence:} reflexivní, symetrická, tranzitivní}
		}
	}

	\scpart{Třídy ekvivalence}{
		Určené prvkem $x$:
		$$ R[x] = \{y\in X, xRy\} $$
		(díky symetrii platí i $yRx$).

		\example{
			$$ X = \{1,2,3,4\} $$
			$$ R = \{(1,1),(2,2),(3,3),(4,4),(2,4),(4,2)\} $$
			$$ \eqalign{R[1] &= \{1\}\cr R[2] = R[4] &= \{2,4\}} $$
		}

		\declaration{
		\list{
			\listItem{$x\in R[x]\qquad \forall x \in X$}
			\listItem{$R[x] = R[y] \lor R[x] \cap R[y] = \emptyset\qquad \forall x,y \in X$}
		}
		}

		\proof{
		\list{
			\listItem{Z reflexivity.}
			\listItem{Nechť $x, y \in X$:
				\list{
				\listItem{Předpokládejme $xRy$:

					$R[x] \subseteq R[y]$: Mějme libovolné $z \in R[x]$,
					tedy $zRx \becauseof{tranz.}{\rightarrow} zRy$,
					to znamená $z \in R[y]$. \sqed

					$R[y] \subseteq R[x]$ obdobně (symetrie).

					$$R[x] = R[y]$$
				}
				\listItem{Předpokládejme, že neplatí $xRy$:

					Pro spor nechť $R[x] \cap R[y] \ne \emptyset$.
					Mějme libovolné $z \in R[x] \cap R[y]$. Pak jistě
					$xRz \et zRy \becauseof{tranz.}{\Rightarrow} xRy$.
					\XXX

					$$R[x] \cap R[y] = \emptyset$$
				}
				}
			}
		}
		}

		\impl{
			Množina (systém množin) $\{R[x]: x\in X\}$ tvoří tzv.
			{\bf rozklad} množiny $X$. $\forall x \in X$ pak patří
			do právě jedné množiny z rozkladu.
		}
	}

}


\subchapter{Uspořádání}{

	\shortdef{(Částečné) uspořádání}{Relace na $X$, která je reflexivní,
		tranzitivní a {\it antisymetrická}
		($xRy \et yRx \Rightarrow x=y\quad \forall x,y\in X$).
	}

	\shortdef{Značení}{$\le$ či $\preceq$}
	\shortdef{Příklady}{$(\nat,\preceq)$, $(\nat,\cong)$ {\it (dělí)}, $(P(X),\preceq)$}

	\shortdef{Lineární uspořádání}{Takové uspořádání, že $xRy \lor yRx\quad \forall x,y\in X$.}
	\shortnote{$(P(X),\preceq)$ je lineární, pokud $|X| \le 1$.}

}


\subchapter{Zobrazení}{

	\definition{
		Máme-li množiny $X$, $Y$, {\bf zobrazení z $X$ do $Y$} definujeme
		jako libovolnou relaci $f \subseteq X \times Y$, která splňuje
		předpoklad, že $\forall x\in X\ \onexists y \in Y$ takové, že
		$xfy$.
	}

	\shortdef{Značení}{$f\colon X\to Y$, $f\colon x \mapsto y$, $f(x) = y$}

	\definition{
		Máme-li $f\colon X\to Y$ a $g\colon Y\to Z$,
		{\bf složené zobrazení} $g \circ f$
		značí zobrazení $X \to Z$, definované předpisem:
		$$(g \circ f)(x) = g(f(x))\qquad \forall x \in X$$

		\note{
			$g \circ f$ je skutečné zobrazení z $X$ do $Z$:
			$$(g \circ f)(x) = g(\undernote{f(x)}{\onexists y}) = \undernote{g(y)}{\onexists z} = z$$
		}
	}

	\definition{
		Říkáme, že zobrazení $f\colon X\to Y$ je:
		\list{
			\olistItem{{\bf prosté} (injekce $f\colon X\leftrightarrow Y$),
				pokud $x \ne y \Rightarrow f(x) \ne f(y)\quad \forall x,y\in X$.}
			\olistItem{{\bf na (z $X$ na $Y$)} (surjekce $f\colon X\rightarrow\hskip-4pt> Y$),
				pokud $\forall y\in Y\ \existss x\in X$ takové, že $f(x) = y$.}
			\olistItem{{\bf vzájemně jednoznačné} (bijekce $f\colon X \leftrightarrow\hskip-4pt> Y$
				či $f\colon X \bijection Y$), pokud je prosté a {\it na}.}
		}

		Pro konečné množiny platí:
		\list{
			\olistItem{prosté: $|X| \le |Y|$}
			\olistItem{{\it na\/}: $|X| \ge |Y|$}
			\olistItem{bijekce: $|X| = |Y|$}
		}
	}

	\shortnote{Pojem {\bf funkce} se používá ve významu ``zobrazení'' či ``zobrazení do $\real$''.}

}

\bend