\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
