\setcounter{chapter}{-1}
\chapter{预备知识}
\section{逻辑与集合}
略。见《离散数学》。

\section{间接证明法}
\subsection{反证法}
欲证$A$成立，则假设$A$不成立，推导出矛盾即可。

\subsection{数学归纳法}
给定一个与自然数$n$有关的命题$P(n)$，如果：
\begin{enumerate}
    \item 可以证明当$n$取初始值$n_0$时命题$P(n_0)$成立；
    \item 假设当$n = k (k \geq n_0)$时命题$P(k)$成立，可以证明当$n = k + 1$ 时命题$P(k + 1)$也成立；
\end{enumerate}
则对一切自然数$n \geq n_0$，命题$P(n)$都成立。

\section{映射}
\begin{definition}[映射]
    设有集合$X$和$Y$，如果$X$中任意元素$x$，都以某种法则$f$对应于$Y$中唯一一个元素，则称这个对应法则$f$是集合$X$到集合$Y$的一个\textbf{映射}，$X$中元素$x$所对应的$Y$中的元素常记作$f(x)$。

    映射用如下记号表示：
    \begin{align*}
        f:\ X &\to Y \eqco\\
        x & \mapsto f(x) \eqper
    \end{align*}
    这里，集合$X$称为映射$f$的\textbf{定义域}，集合$Y$称为映射$f$的\textbf{陪域}。设$x \in X, y =f(x) \in Y$，我们称$y$为$x$在映射$f$下的\textbf{原像}。注意，$Y$中的元素不一定都有原像；有原像时，原像也可能不唯一。定义域$X$中所有元素在$f$下的像构成$Y$的一个子集$\{ f(x) \mid x \in X \}$，称为映射$f$的\textbf{像集}或\textbf{值域}，记作$f(X)$。

    如果对$X$中的任意两个不同元素$x_1$，$x_2$，都有$f(x_1) \neq f(x_2)$，则称$f$是一个\textbf{单射}；即，任何元素的原像至多只有一个。

    如果对$Y$中的任意元素$y$，都存在$X$中的某个$x$，使得$y = f(x)$，则称$f$是一个\textbf{满射}；即，$f$的像集$f(X) = Y$。

    映射$f$即是单射又是满射，则称$f$是一个\textbf{双射}。双射$f$给出了集合$X$和$Y$之间的一个一一对应。

    当映射$f$的定义域和陪域都是$X$时，称$f$是集合$X$上的一个\textbf{变换}。
\end{definition}

\begin{definition}[映射的复合]
    设$X$，$Y$，$Z$是三个集合，$f: X \to Y$，$g: Y \to Z$是两个映射，则可以定义一个映射
    \begin{align*}
        h: X &\to Z \eqco\\
        x &\mapsto h(x) = g(f(x)) \eqco
    \end{align*}
    称其为$g$与$f$的\textbf{复合}，记作$h = g \circ f$。
\end{definition}

映射的复合满足结合律，即$f \circ (g \circ h) = (f \circ g) \circ h$。

容易看到，一个变换永远可以跟自身复合，记$f^2 = f \circ f$，$f^n = f^{n-1} \circ f$，$n \geq 1$。任意集合$X$上都有一个特殊的变换，它把$X$中的任意元素$x$映到$x$本身，成为$X$上的\textbf{恒同变换}，记作$\id_X$，即$\id_X(x) = x$，对任意$x \in X$都成立。恒同变换与映射的复合不改变映射：对任意映射$f:X \to Y$，都有$f \circ \id_X = f = \id_Y \circ f$。

\begin{definition}[可逆、逆映射]
    设$f: X \to Y$是一个映射，若存在另一个映射$g: Y \to X$，满足$f \circ g = \id_Y$，$g \circ f = \id_X$，则称映射$f$\textbf{可逆}，称$g$是$f$的一个\textbf{逆（映射）}。
\end{definition}

\begin{theorem}
    对映射$f: X \to Y$，若$X \neq \varnothing$，则有
    \begin{enumerate}
        \item $f$是单射当且仅当存在另一个映射$g: Y \to X$，使得$g \circ f = \id_X$；
        \item $f$是满射当且仅当存在另一个映射$g: Y \to X$，使得$f \circ g = \id_Y$；
        \item $f$是双射当且仅当$f$可逆，即存在另一个映射$g: Y \to X$，使得$g \circ f = \id_X$，$f \circ g = \id_Y$。
    \end{enumerate}
\end{theorem}