Basic Structures: Sets, Functions, Sequences, Sums, and Matrices

2.1 集合

定义1$\qquad$集合是对象的一个无序的聚集,对象也称为集合的元素或成员.集合包含它的元素.

$a\in A$表示$a$是集合$A$中一个元素; $a\notin A$表示$a$不是集合$A$中的一个元素.

描述集合有多种方式.一种方式是在可能的情况是在花括号之间列出所有元素.这种描述集合的方式也称为是 花名册方法.

例子

例1例2例3

英语字母表中所有元音字母的集合$V$可以表示为$V=\{a, e, i, o, u\}$.

小于10的正奇数集合$O$可以表示为$O=\{1,3,5,7,9\}$.

小于100的正整数集合可以表示为$\{1,2,3,\cdots,99\}$.

如例3所示,用花名册方法表示集合时并不需要列出它的所有元素,可以先列出集合中的某些元素，当元素的一般规律显而易见时就用省略号($\cdots$)代替.

描述集合的另一种方式是使用 集合构造器 符号.

例子

例1例2

小于10的正奇数集合$O$可以表示为

\[ O=\{x\in\mathbf{Z^+}|x为奇数,x<10\} \]

所有正有理数集合可以被写为

\[ Q^+ = \left\{ z\in R | x = p/q,p和q为正整数\right\} \]

一些常用的数集如下:

\[\begin{aligned} &\mathbf{N} =\{0,1,2,3,\cdots\},\text{自然数集}\\ &\mathbf{Z} =\{\cdots,-1,0,1,\cdots\},\text{整数集}\\ &\mathbf{Z^+}=\{1,2,3,\cdots\},\text{正整数集}\\ &\mathbf{Q}=\{p/q|p\in \mathbf{Z},q\in\mathbf{Z},q\ne0 \},\text{有理数集}\\ &\mathbf{R},\text{实数集}\\ &\mathbf{R^+},\text{正实数集}\\ &\mathbf{C},\text{复数集} \end{aligned} \]

对于实数$a,b$且$a<b$,实数区间:

\[ \begin{aligned} \ [a,b\ ]=\{x\mid a\le x\le b\}\\ (a,b\ ]=\{x\mid a< x\le b\}\\ \ [a,b\ )=\{x\mid a\le x< b\}\\ \ (a,b\ )=\{x\mid a< x< b\}\\ \end{aligned} \]

其中,$[a,b]$称为闭区间,$(a,b)$称为开区间,$[a,b)$和$(a,b]$称为半开半闭区间.

定义2$\qquad$两个集合相等当且仅当它们具有相同的元素,即对于集合$A$和集合$B$有

\[ \forall x(x\in A\leftrightarrow x\in B) \]

记为$A=B$.

朴素集合论可能会导致一些悖论

韦恩图

全集$U$用矩形表示,全集中的集合用圆形或者其它图形表示,集合中的特定元素用点表示. Veen diagram

子集

定义3$\qquad$当且仅当集合$A$中的元素也是集合$B$的元素,那么集合$A$是集合$B$的子集,集合$B$是集合$A$的超集,即

\[ \forall x(x\in A\to x\in B) \]

记为$A\subseteq B$和$B\supseteq A$.

证明方法

证明$A$是$B$的子集:需要证明如果$x\in A$那么$x\in B$.
证明$A$不是$B$的子集:需要找一个$x\in A$使$x\notin B$.
证明两个集合相等:需要证明$A\subseteq B$和$B\subseteq A$.

定理1$\qquad$对于任意集合$x$有(i)$\varnothing\subseteq S$, (ii)$S\subseteq S$ 证明: (i). 根据子集的定义有$\forall x(x\in \varnothing\to x\in S)$,因为$\varnothing$中没有元素,所以$x\in\varnothing$一定为假当前提为假时,条件语句一定为真. (ii) 根据子集的定义有$\forall x(x\in S\to x\in S)$,显然成立.

当$A$是$B$的子集且$A\ne B$时,则$A$是$B$的真子集,记为$A\subset B$.

集合的大小

定义4$\qquad$如果集合$S$中恰有$n$个不同元素($n$为非负整数),则$S$为有限集,$n$称为$S$的基数,记为$|S|$.

空集没有元素,所以$|\varnothing|=0$.

定义5$\qquad$．如果一个集合不是有限的,则称其是无限的.

幂集

定义6$\qquad$给定集合$S$,$S$的幂集是集合$S$所有子集的集合.记为$\mathcal{P}(S)$.

空集的幂集

\[ \begin{aligned} &\mathcal{P}(\varnothing)=\{ \varnothing\}\\ &\mathcal{P}(\{\varnothing\})=\{\varnothing,\{\varnothing\}\} \end{aligned} \]

笛卡尔积

定义7$\qquad$有序$n$元组$(a_1, a_2, \cdots , a_n)$是以$a_1$为第$1$个元素,$a_2$为第$2$个元素,$\cdots$,$a_n$为第$n$个元素的有序聚集.

两个有序$n$元组是相等的当且仅当每一对对应的元素都相等.

定义8$\qquad$集合$A$和$B$的笛卡儿积用$A\times B$表示,是所有序偶$(a, b)$的集合,其中$a\in A$且$b\in B$.于是

\[ A\times B=\{(a,b)\mid a\in A\wedge b\in B\} \]

注意

$A\times B$与$B\times A$所得结果不同,除非当$A=\varnothing$或$B=\varnothing$.

定义9$\qquad$集合$A_1,A_2,\cdots,A_n$的笛卡儿积用$A_1\times A_2\times A_3\times\cdots\times A_n$表示，是有序$n$元组$(a_1,a_2,\cdots,a_n)$的集合，其中 $a_i$属于$A_i$,$i= 1,2,\cdots,n$.换言之

\[ A_1\times A_2\times\cdots\times A_n=\left\{(a_1,a_2,\cdots\,a_n)\mid a_i\in A_i,i=1,2,\cdots,n\right\} \]

给定谓词$P$和论域$D$,则$P$的真值集为$D$中使$P(x)$为真的元素$x$组成的集合.$P(x)$的真值集记为$\{x\in D \mid P(x)\}$.

2.2 集合的运算

定义1$\qquad$集合$A$和集合$B$的并集是一个包含$A$或包含$B$或同时在$A$和$B$中的元素组成的集合,记为$A\cup B$.

\[ A\cup B=\{x\mid x\in A\vee x\in B\} \]

定义2$\qquad$集合$A$和集合$B$的交集是一个由同时在$A$和$B$中的元素组成的集合,记为$A\cap B$.

\[ A\cap B=\{x\mid x\in A\wedge x\in B\} \]

union&intersection set

定义3$\qquad$如果两个集合的交集为空,则称它们是不相交的.

容斥原理

\[ |A\cup B| = |A|+|B|-|A\cap B| \]

定义4$\qquad$集合$A$和集合$B$的差集是一个包含$A$的元素但不包含$B$的元素的集合,记为$A- B$.

\[ A- B=\{x\mid x\in A\wedge x\notin B\} \]

定义5$\qquad$集合$A$在全集$U$上的补集记为$\overline{A}$.

\[ \overline{A}=\{x\in U|x\notin A\} \]

difference&complement set

集合恒等式

常用的集合恒等式见下图

set identity

证明集合恒等式的方法

子集法
成员表
利用已知的恒等式

拓展的并集与交集

定义6$\qquad$一组集合的并集是指至少包含这组集合中一个集合成员的元素的集合. 可以用记号

\[ \bigcup_{i=1}^{n}A_i=A_1\cup A_2\cdots\cup A_n \]

表示集合$A_1,A_2,\cdots,A_n$的并集.

定义7$\qquad$一组集合的交集是指同时包含这组集合中集合成员的元素的集合. 可以用记号

\[ \bigcap_{i=1}^{n}A_i=A_1\cap A_2\cdots\cap A_n \]

表示集合$A_1,A_2,\cdots,A_n$的交集.

多重集

2.3 函数

定义1$\qquad$从非空集合$A$和$B$的函数$f$是对元素的一种指派:对$A$ 的每个元素恰好指派$B$ 的一个元素。如果B 中元素b 是唯一由函数f指派给A 中元素a 的，则我们就写成$f(a)=b$.如果$f$是从$A$ 到$B$的函数，就写成$f:A\to B$.

函数有时也称为映射或者变换。

定义 2 如果$f$是从$A$ 到$B$ 的函数，那么$A$是$f$的定义域,而$B$是$f$的陪域. 如果$f(a)=b$，那么$b$ 是$a$的像,而 $a$ 是$b$ 的原像. $f$的值域或像是 $A$ 中元素的所有像的集合。如果 $f$是从$A$ 到 $B$ 的函数，我们说$f$把$A$ 映射（map）到 $B$。

2.4 序列与求和

序列

定义1$\qquad$ 序列是从整数集的一个子集（通常是集合$\{0, 1, 2,\cdots\}$或集合$\{1, 2, 3, \cdots\}$）到一个集合 $S$ 的函数。记号$a_n$表示整数$n$的像，称为序列的一个项。

定义2$\qquad$ 序列 $$ a,ar,ar^2,\cdots,ar^n,\cdots $$ 称为几何级数，其中首项 $a$和公比$r$ 都是实数。

定义3$\qquad$ 序列 $$ a,a+d,a+2d,\cdots,a+nd,\cdots $$ 称为算术级数，其中首项 $a$和公差$d$ 都是实数。

计算机科学中将形如 $a_1, a_2, \cdots, a_n$ 的有穷序列称为串。这个串也可以记作 $a_1a_2\cdots a_n$。

比特串是比特的有限序列。

串的长度

串的长度是这个串的项数。空串是没有任何项的串，记作 $\lambda$。空串的长度为$0$.

递推关系

定义4$\qquad$ 对所有满足$n\ge n_0$（$n_0$为非负整数）的$n$，将$a_n$用序列前面项，即$a_0, a_1, \cdots, a_{n-1}$中的一项或多项来表示，称为序列$\{a_n\}$的递推关系。

如果一个序列的项满足递推关系，则该序列就称为是递推关系的一个解。

定义5$\qquad$ 斐波那契数列$f_0, f_1, f_2, \cdots$是初始条件为$f_0 = 0$和$f_1 = 1$且满足递推关系 $$ f_n = f_{n-1} + f_{n-2}\qquad n = 2, 3, \cdots $$ 的序列。

如果为序列的项找到一个显示公式，即闭公式，那么就说明求解了一个带有初始条件的递推关系。

求和

对于序列$a_m, a_{m+1}, a_{m+2}, \cdots, a_n$，可以使用记号 $$ \sum_{j=m}^{n}a_j\quad\text{或}\quad \sum_{m\le j\le n}a_j $$ 表示 $$ a_m+a_{m+1}+\cdots+a_n $$

定理1$\qquad$如果$a$和$r$都是实数且$a\ne0$,则 $$ \sum_{j=0}^{n}ar^j = \begin{cases} a\frac{1-r^{n+1}}{1-r}\quad\text{当}r\ne1 \ a(n+1)\quad\text{当}r=1 \end{cases} $$