定义1：集合是对象的一个无序的聚集，对象也称为集合的元素（element）或成员（member）。集合包含（contain）它的元素。我们用$a \in A$来表示a是集合A中的一个元素。而记号$a \notin A$表示a不是集合A中的一个元素。
通常我们用大写字母来表示集合。用小写字母表示集合中的元素。
定义2：两个集合相等当且仅当它们拥有同样的元素。所以，如果A和B是集合，则A和B是相等的当且仅当$\forall x(x \in A \leftrightarrow x \in B)$。如果A和B是相等的集合，就记为A=B。
有一个特殊的不含任何元素的集合。这个集合称为空集（empty set 或 null set），并用$\phi$表示。
只有一个元素的集合叫做单元素集（singleton set）。一个常见的错误是混淆空集$\phi$与单元素集{$\phi$}。
定义3：集合A是集合B的子集当且仅当A的每个元素也是B的元素。我们用记号$A \subseteq B$表示集合A是集合B的子集。
$A \subseteq B$当且仅当量化式 $\forall x(x \in A \to x \in B)$为真。
定理1：对于任意集合S，（i）$\phi \subseteq S$ 和 （ii）$S \subseteq S$。
证明两个集合相等：$A \subseteq B$ 和 $B \subseteq A$
定义4：令S为集合。如果S中恰有n个不同的元素，这里n是非负整数，我们就说S是有限集，而n是S的基数（cardinality）。S的基数记为|S|。
定义5：一个集合称为是无限的如果它不是有限的。
定义6：给定集合S，S的幂集（power set）是集合S所有子集的集合。S的幂集记为P(S)。
定义7：有序n元组（ordered n-tuple）(a1,a2,...,an)是以a1为第1个元素，a2为第2个元素，...，an为第n个元素的有序聚集。
两个有序n元组是相等的当且仅当每一对对应的元素都相等。换言之，(a1,a2,...,an)=(b1,b2,...,bn)当且仅当对于i=1,2,...,n,有ai=bi。特别地，有序二元组为序偶（ordered pair）。
定义8：令A和B为集合。A和B的笛卡尔积（Cartesian product）用$A \times B$表示，是所有序偶（a,b）的集合，其中$a \in A$且$b \in B$。于是，$A \times B=\{(a,b)|a \in A \land b \in B\}$
定义9：集合A1,A2,...,An的笛卡尔积用$A_1 \times A_2 \times \cdots \times A_n$表示，是有序n元组(a1,a2,...,an)的集合，其中ai属于Ai，i=1,2,...,n。换言之，$A_1 \times A_2 \times \cdots \times A_n=\{(a_1,a_2,\cdots,a_n)|a_i \in A_i,i=1,2,\cdots,n\}$
有时我们通过使用特定的符号来显式地限定一个量化命题的论域。例如，$\forall x \in S(P(x))$表示P(x)在集合S所有元素上的全称量化。换句话说，$\forall x \in S(P(x))$是$\forall x(x \in S \to P(x))$的简写。类似地，$\exists x \in S(P(x))$表示P(x)在集合S所有元素上的存在量化。即$\exists x \in S(P(x))$是$\exists x (x \in S \land P(x))$的简写。
给定谓词P和论域D，定义P的真值集(truth set)为D中使P(x)为真的元素x组成的集合。P(x)的真值集记为$\{x \in D | P(x)\}$。
定义1：令A和B为集合。集合A和B的并集，用$A \cup B$表示，是一个集合，它包含A或B中或同时在A和B中的元素。
一个元素x属于A和B的并集当且仅当x属于A或x属于B。这说明 $A \cup B=\{x|x \in A \lor x \in B\}$
定义2：令A和B为集合。集合A和B的交集，用$A \cap B$表示，是一个集合，它包含同时在A和B中的那些元素。
一个元素x属于集合A和B的交集当且仅当x属于A而且x属于B。这说明 $A \cap B=\{x|x \in A \land x \in B\}$
定义3：两个集合称为是不相交的，如果它们的交集为空集。
$|A \cup B| = |A| + |B| - |A \cap B|$
把这一结果推广到任意多个集合的并集就是所谓的包含排斥原理或简称容斥原理(principle of inclusion-exclusion)。容斥原理是枚举中的一项重要技术。
定义4：令A和B为集合。A和B的差集，用A-B表示，是一个集合，它包含属于A而不属于B的元素。A和B的差集也称为B相对于A的补集。
评注：集合A和B的差集有时候也记为 A \ B。
一个元素x属于A和B的差集当且仅当 $x \in A$且$x \notin B$，这说明$A-B=\{x|x \in A \land x \notin B\}$
定义5：令U为全集。集合A的补集，用$\bar{A}$表示，是A相对于U的补集。所以，集合A的补集是U-A。
一个元素x属于$\bar{A}$当且仅当$x \notin A$。这说明$\bar{A}=\{x \in U | x \notin A\}$
定义6：一组集合的并集是包含那些至少是这组集合中一个集合成员的元素的集合。用$A_1 \cup A_2 \cup \cdots \cup A_n = \cup_{i=1}^n A_i$表示集合$A_1,A_2,\cdots,A_n$的并集。
定义7：一组集合的交集是包含那些属于这组集合中所有成员集合的元素的集合。用$A_1 \cap A_2 \cap \cdots \cap A_n = \cap_{i=1}^n A_i$表示集合$A_1,A_2,\cdots,A_n$的交集。
定义1：令A和B为非空集合。从A到B的函数f是对元素的一种指派，对A的每个元素恰好指派B的一个元素。如果B中元素b是唯一由函数f指派给A中元素a的，则我们就写成f(a)=b。如果f是从A到B的函数，就写成f:A->B。
评注：函数有时也称为映射(mapping)或者变换(transformation)。
定义2：如果f是从A到B的函数，我们说A是f的定义域（domain），而B是f的陪域（codomain）。如果f(a)=b，我们说b是a的像（image），而a是b的原像（preimage）。f的值域（range）或像是A中元素的所有像的集合。如果f是从A到B的函数，我们说f把A映射（map）到B。
当定义一个函数的时候，我们需要指定它的定义域、陪域、定义域中元素到陪域的映射。当两个函数有相同的定义域、陪域，定义域中的每个元素映射到陪域中相同的元素时，这两个函数是相等的。注意，如果改变函数的定义域或陪域，那么将得到一个不同的函数。如果改变元素的映射关系，也会得到一个不同的函数。
一个函数称为是实值函数如果其陪域是实数集合，称为整数值函数如果其陪域是整数集合。具有相同定义域的两个实值函数或两个整数值函数可以相加和相乘。
定义3：令f1和f2是从A到R的函数，那么f1+f2和f1f2也是从A到R的函数，其定义为对任意$x \in A$
$(f_1+f_2)(x)=f_1(x)+f_2(x)$
$(f_1f_2)(x)=f_1(x)f_2(x)$
定义4：令f为从A到B的函数，S为A的一个子集。S在函数f下的像是由S中元素的像组成的B的子集。我们用f(S)表示S的像，于是$f(S)=\{t|\exists s \in S(t=f(s))\}$，我们也用简写$\{f(s)|s \in S\}$来表示这个集合。
评注：用f(S)表示集合S在函数f下的像可能会有潜在二义性。这里，f(S)表示一个集合，而不是函数f在集合S处的值。
定义5：函数f称为一对一(one-to-one)或单射函数(injection)，当且仅当对于f的定义域中的所有a和b有f(a)=f(b)蕴含a=b。一个函数如果是一对一的，就称为单射的(injective)。
评注：我们可以用量词表达f是一对一的，如$\forall a \forall b(f(a)=f(b) \to a=b)$或等价地$\forall a \forall b(a \ne b \to f(a) \ne f(b))$，其中论域是函数的定义域。
定义6：定义域和陪域都是实数集子集的函数f从称为是递增的，如果对f的定义域中的x和y，当x < y时有$f(x) \le f(y)$；称为是严格递增的，如果当x < y时有f(x) < f(y)。类似地，f称为是递减的，如果对f的定义域中的x和y，当x < y时有 $f(x) \ge f(y)$；称为是严格递减的，如果当x < y时有f(x) > f(y)。
评注：一个函数f是递增的，如果$\forall x \forall y(x<y \to f(x) \le f(y))$；是严格递增的，如果$\forall x \forall y(x<y \to f(x) < f(y))$；是递减的，如果$\forall x \forall y(x<y \to f(x) \ge f(y))$；是严格递减的，如果$\forall x \forall y(x<y \to f(x) > f(y))$。这里论域均为函数f的定义域。
有些函数的值域和陪域相等。即陪域中的每个成员都是定义域中某个元素的像。具有这一性质的函数称为映上函数。
定义7：一个从A到B的函数f称为映上(onto)或满射(surjection)函数，当且仅当对每个$b \in B$有元素$a \in A$使得f(a)=b。一个函数f如果是映上的就称为是满射的(surjection)。
评注：一个函数f是映上的如果$\forall y \exists x(f(x)=y)$，其中x的论域是函数的定义域，y的论域是函数的陪域。
定义8：函数f是一一对应(one-to-one correspondance)或双射(bijection)函数，如果它既是一对一的又是映上的。这样的函数称为双射的(bijective)。
定义9：令f为从集合A到集合B的一一对应。f的反函数是这样的函数，它指派给B中元素b的是A中使得f(a)=b唯一元素a。f的反函数用$f^{-1}$表示。于是，当f(a)=b时$f^{-1}(b)=a$。
一一对应关系称为可逆的（invertible），就因为可以定义这个函数的反函数。如果函数不是一一对应关系，就说它是不可逆的(not invertible)，因为这样的函数不存在反函数。
定义10：令g为从集合A到B的函数，f是从集合B到集合C的函数，函数f和g的合成（composition），记作$f \circ g$，定义为对任意$a \in A,(f \circ g)(a)=f(g(a))$
在构造函数和它的反函数的合成时，不论以什么次序合成，得到的都是恒等函数。要看清这一点，假定f是从集合A到集合B的一一对应关系。那么存在反函数$f^{-1}$且是从B到A的一一对应关系。反函数把原函数的对应关系颠倒过来，所以当f(a)=b时$f^{-1}(b)=a$，当$f^{-1}(b)=a$时，f(a)=b。因此，
$(f^{-1} \circ f)(a)=f^{-1}(f(a))=f^{-1}(b)=a$
$(f \circ f^{-1})(b)=f(f^{-1}(b))=f(a)=b$
可以将一个$A \times B$中的序偶集合和每个从A到B的函数关联起来。这个序偶集合称为该函数的图(graph)。
定义11：令f为从集合A到集合B的函数，函数f的图像是序偶集合$\{(a,b)| a \in A \land f(a)=b\}$。
定义12：下取整函数（floor）指派给实数x的是小于或等于x的最大整数。下取整函数在x的值用$\llcorner x \lrcorner$表示。上取整函数（ceiling）指派给实数x的是大于或等于x的最小整数。上取整函数在x的值用$\ulcorner x \urcorner$表示。
本书中logx表示x以2为底的对数，$log_b x$表示以b为底的对数(b>1)，Inx表示自然对数。
阶乘函数f:$N \to Z^{+}$，记为f(n)=n!。
定义13：一个从集合A到集合B的部分函数(partial function)f是给A的一个子集（成为f的定义域(domain of definition)）中的每个元素a指派唯一的一个B中的元素b。集合A和B分别称为f的域和陪域。我们说f对于A中但不在f的定义域中的元素无定义(undefined)。当f的定义域等于A时，就说f是全函数（total function）。
定义1：序列（sequence）是一个从整数集的一个子集（通常是集合{0,1,2,...}或集合{1,2,3,...}）到一个集合S的函数。用记号$a_n$表示整数n的像。称$a_n$为序列的一个项（item）。
定义2：几何级数是如下形式的序列：$a,ar,ar^2,\cdots,ar^n,\cdots$，其中初始项a和公比r都是实数。
评注：几何级数是指数函数$f(x)=ar^x$的离散的对应体。
定义3：算术级数是如下形式的序列：$a,a+d,a+2d,\cdots,a+nd,\cdots$，其中初始项a和公差d都是实数。
评注：算术级数是线性函数f(x)=dx+a的离散的对应体。
在计算机科学中经常使用形如$a_1,a_2,\cdots,a_n$的序列。这些有穷序列也称为串（string）。这个串也可记作$a_1a_2 \cdots a_n$。串的长度是这个串的项数。空串是没有任何项的串，记作$\lambda$。空串的长度为0。
定义4：关于序列$\{a_n\}$的一个递推关系（recurrence relation）是一个等式，对所有满足$n \ge n_0$的n，它把$a_n$用序列中的前面项即$a_0,a_1,\cdots,a_{n-1}$中的一项或多项来表示。这里$n_0$是一个非负整数。如果一个序列的项满足递推关系，则该序列就称为是递推关系的一个解。（一个递推关系称为递归地定义了一个序列）。
递归定义的序列的初始条件指定了在递推关系定义的首项前的那些项。采用第5章介绍的数学归纳法，可以证明一个递推关系及其初始条件可以唯一地确定了一个序列。
定义5：斐波那契数列$f_0,f_1,f_2,\cdots,$由初始条件$f_0=0,f_1=1$，和下列递推关系所定义$f_n=f_{n-1}+f_{n-2},n=2,3,4,\cdots$
当我们为序列的项找到一个显式公式，称为闭公式（closed formula）时，我们就说解决了带有初始条件的递推关系。
定理1：如果a和r都是实数且$r \ne 0$，则$\sum_{j=0}^n ar^j=\left\{\begin{matrix} \frac{ar^{n+1}-a}{r-1},& if\ r \ne 1 \\ (n+1)a, & r=1. \end{matrix}\right.$
定义1：集合A和集合B有相同的基数（cardinality），当且仅当存在从A到B的一个一一对应，当A和B有相同的基数时，就写成|A|=|B|。
定义2：如果存在一个从A到B的一对一函数，则A的基数小于或等于B的基数，并写成$|A| \le |B|$。再者，当$|A| \le |B|$并且A和B有不同的基数时，我们说A的基数小于B的基数，并写成|A| < |B|。
定义3：一个集合或者是有限集或者与自然数具有相同的基数，这个集合就称为可数的（countable）。一个集合不是可数的，就称为不可数的（uncountable）。如果一个无限集S是可数的，我们用符号$\aleph_0$来表示集合S的基数。写作$|S|=\aleph_0$，并说S有基数“阿里夫零”。
例1 证明正奇数集合是可数集 解 要证明正奇数集合是可数的，就要给出这个集合与正整数集合之间的一个一一对应。考虑从$Z^{+}$到正奇数集合的函数$f(n)=2n-1$。
通过证明f既是一对一的又是映上的来证明f是一一对应的。要想知道f是一对一的，假定f(n)=f(m)。于是2n-1=2m-1，所以n=m。要想知道f是映上的，假定t是正奇数。于是t比一个偶数2k少1，其中k是自然数。因此t=2k-1=f(k)。图1显示了这个一一对应。
希尔伯特大饭店（例2）：这是一个悖论，它证明了某些对有限集不可能的事情对无限集变得可能了。大饭店有可数无限多个房间，每个房间都有客人。当一个客人来到一家只有有限个房间的饭店，而且房间已经都有客人时，不赶走一位客人是容纳不下新来的客人的。可是，在大饭店我们总是能够容纳一位新客人的，即使所有房间已都住了客人。
证 因为大饭店的房间是可数的，我们可以把它们排列成1号房间、2号房间、3号房间等。当一位新客人到来时，我们把1号房间的客人安排到2号房间，把2号房间的客人安排到3号房间，更一般地，对于所有整数n，把n号房间的客人安排到n+1号房间。这样就把1号房间腾出来了，把这个房间分配给新来的客人，并且所有原先的客人也都有房间。这种场景的解释如图2所示。
例4：证明正有理数集合是可数的。
解 首先，注意每个正有理数都是两个正整数之比p/q。可以这样来排列正有理数：在第1行列出分母q=1的有理数，在第2行列出分母q=2，等等，如图3所示。
把有理数排列成序列的关键是：沿着图3所示的路线，先列出满足p+q=2的正有理数p/q，再列出满足p+q=3的正有理数，然后列出满足p+q=4的正有理数，等等。每当遇到已经列出过的数p/q时，就不再次列出了。例如，当遇到2/2=1时就不列出了，因为已经列出过1/1=1。这样构造的正有理数序列的初始项是1,1/2,2,3,1/3,1/4,2/3,3/2,4,5,等等。这些数在图3中都加了圆圈，序列中没有圆圈的数是那些被剔除的，因为它们已经在序列中了。由于所有有理数都只列出一次，所以我们证明了正有理数集合是可数的。
例5：证明实数集合是不可数集合
解 我们假定实数集合是可数的，于是所有落在0和1之间的实数所构成的子集也是可数的（因为可数集合的任意子集合都是可数的）。在此假设下，在0和1之间的实数可以按照某种顺序列出，比如说$r_1,r_2,r_3,\cdots$。设这些实数的十进制表示为
$$ r_1=0.d_{11}d_{12}d_{13}d_{14}\cdots \\ r_2=0.d_{21}d_{22}d_{23}d_{24}\cdots \\ r_3=0.d_{31}d_{32}d_{33}d_{34}\cdots \\ r_4=0.d_{41}d_{42}d_{43}d_{44}\cdots \\ \vdots $$其中$d_{ij} \in \{0,1,2,3,4,5,6,7,8,9\}$。（例如，如果$r_1=0.23794102\cdots$，就有$d_{11}=2,d_{12}=3,d_{13}=7$，等等）于是，构造新的实数具有十进制展开式$r=0.d_1d_2d_3d_4\cdots$，其中十进制数字由下列规则确定：$d_i=\left\{\begin{matrix} 4,& if\ d_{ii} \ne 4 \\ 5,& if\ d_{ii}=4 \end{matrix}\right.$
（例如，假定$r_1=0.23794102\cdots,r_2=0.44590138\cdots,r_3=0.09118764\cdots,r_4=0.80553900\cdots$，等等。于是，就有$r=0.d_1d_2d_3d_4\cdots=0.4544\cdots$）。
每个实数都有唯一的十进制展开式。所以，实数r不等于$r_1,r_2,\cdots$中的任何一个，因为对于每个i，r的十进制展开式与$r_i$的十进制展开式的小数点右边的第i位是不同的。
由于存在不在列表中的0和1之间的实数r，所以假设可以列出在0和1之间的所有实数就必定为假。所以，在0和1之间的所有实数不能一一列出，因此在0和1之间的实数集合是不可数的。（康托对角线法）
定理1：如果A和B是可数集合，则$A \cup B$也是可数集合。
定理2 SCHRODER-BERNSTEIN定理：如果A和B是集合且 $|A| \le |B|$ 和 $|B| \le |A|$，则|A| = |B|。换言之，如果存在一对一函数f从A到B和g从B到A，则存在A和B之间的一一对应函数。
定义4：一个函数称为是可计算的（computable），如果存在某种编程语言写的计算机程序能计算该函数的值。如果一个函数不是可计算的，就说是不可计算的（umcomputable）。
连续统假设：康托的一个重要定理表明一个集合的基数总是小于其幂集的基数。故有$|Z^{+}| < |P(Z^{+})|$。我们将这个结论重写为 $\aleph_0 < 2^{\aleph_0}$，这里用记号$2^{|S|}$表示集合S的幂集的基数。连续统假设阐述了不存在介于$\aleph_0$和c之间的基数X。换言之，连续统假设说明了不存在集合A使得正整数集合的基数$\aleph_0$小于|A|，而|A|又小于实数集的基数c。
定义1：矩阵（matrix）是矩形状的数组。m行n列的矩阵称为$m \times n$矩阵。行数和列数相同的矩阵称为方阵（square）。如果两个矩阵有相同数量的行和列且每个位置上的对应项都相等，则这两个矩阵是相等的。
定义2：令m和n是正整数，并令$A=\left[ \begin{matrix} a_{11} & a_{12} & \cdots & a_{1n} \\ a_{21} & a_{22} & \cdots & a_{2n} \\ \vdots & \vdots & \ddots & \vdots \\ a_{m1} & a_{m2} & \cdots & a_{mn} \\ \end{matrix} \right]$
A的第i行是$1 \times n$矩阵$[a_{i1},a_{i2}, \cdots, a_{in}]$。A的第j列是$n \times 1$矩阵$\left[ \begin{matrix} a_{1j}\\ a_{2j}\\ \vdots\\ a_{mj}\\ \end{matrix} \right]$。
A的第(i,j)元素（element）或项（entry）是元素$a_{ij}$，即A的第i行第j列位置上的数。表示矩阵A的一个方便的简写符号是写成$A=[a_{ij}]$，表示A是其第(i,j)元素为$a_{ij}$的矩阵。
定义3：令$A=[a_{ij}]$和$B=[b_{ij}]$为$m \times n$矩阵。A和B的和，记作A+B，是其第(i,j)元素为$a_{ij}+b_{ij}$的矩阵。换言之，$A+B=[a_{ij}+b_{ij}]$。
定义4：令A为$m \times k$矩阵，B为$k \times n$矩阵。A和B的乘积，记作AB，是一个$m \times n$矩阵，其第(i,j)元素等于A的第i行与B的第j列对应元素的乘积之和。换言之，如果$AB=[c_{ij}]$，则$c_{ij}=a_{i1}b_{1j}+a_{i2}b_{2j}+\cdots+a_{ik}b_{kj}$
定义5：n阶单位矩阵(identity matrix of order n)是 $n \times n$矩阵$I_n=[\delta_{ij}]$，其中$\delta_{ij}=1,i=j;\delta_{ij}=0,i \ne j$。因此$I_n=\left[ \begin{matrix} 1 & 0 & \cdots & 0 \\ 0 & 1 & \cdots & 0 \\ \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & \cdots & 1 \\ \end{matrix} \right]$
一个矩阵乘以一个合适的单位阵不会改变该矩阵。换言之，当A是一个$m \times n$矩阵时，有$AI_n=I_mA=A$。
可以定义方阵的幂次。当A是一个$n \times n$矩阵时，则有$A_0=I_n,A^r=\underbrace{AAA \cdots A}_{r\ times}$。
定义6：令$A=[a_{ij}]$为$m \times n$矩阵。A的转置（transpose），记作$A^T$，是通过交换A的行和列所得到的$n \times m$矩阵。换言之，如果$A^T=[b_{ij}],b_{ij}=a_{ji},i=1,2,\cdots,n;j=1,2,\cdots,m$。
定义7：方阵A称为对称的（symmetric）如果$A=A^T$。因此$A=[a_{ij}]$为对称的如果对所有i和j，$i \le n,1 \le j \le n$，有$a_{ij}=a_{ji}$。
定义8：令$A=[a_{ij}]$和$B=[b_{ij}]$为$m \times n$阶0-1矩阵。A和B的并是0-1矩阵，其(i,j)元素为$a_{ij} \lor b_{ij}$。A和B的并记作$A \lor B$。A和B的交集是0-1矩阵，其(i,j)元素是$a_{ij} \land b_{ij}$。A和B的交记作$A \land B$。
定义9：令$A=[a_{ij}]$为$m \times k$阶0-1矩阵，$B=[b_{ij}]$为$k \times n$阶0-1矩阵。A和B的布尔积（Boolean product），记作$A \odot B$，是$m \times n$矩阵$[c_{ij}]$，其中$c_{ij}=(a_{i1} \land b_{1j}) \lor (a_{i2} \land b_{2j}) \lor \cdots \lor (a_{ik} \land b_{kj})$
定义10：令A为0-1方阵，r为正整数。A的r次布尔幂是r个A的布尔积。A的r次布尔幂记作$A^{[r]}$。因此$A^{[r]}=\underbrace{A \odot A \odot A \odot \cdots \odot A}_{r\ times}$
In [ ]: