信息与计算科学导论01

\newcommand\norm[1]{\left\lVert#1\right\rVert} \newcommand\abs[1]{\left\lvert#1\right\rvert} 信息与计算科学导论一

##罗素悖论

考虑这么一个集合：

考虑一个集合内的元素$x$，若$x\in S$，则根据定义$x\not\in S$，矛盾

若$x\not\in S$，则根据定义有$x\in S$，矛盾

我们找不到这样一个集合，这就是大名鼎鼎的罗素悖论

##公理集合论

悖论的源头在于构建集合的描述性方法，我们在使用这个方法的时候出现了所谓“自引用”的情况

为了体系的和谐与自洽，数学家们提出了公理集合论，创造了“类”(class)的概念。

一个集合是一个类，但是所有的类不都是集合。对于那些不是集合的类我们称之为真类(proper class)

可以存在set的set但是不能存在class的class，这样就可以比较和谐地处理一些问题了

关于公理集合论的的具体内容可以看wiki，这里给了一个比较重要的公理——正则公理

若$S$为一集合，要么$S=\varnothing$，要么$\exists x\in S$使得$x\cap S=\varnothing$

这排除了一些看起来是集合然而不太和谐的真类，比如说$\left{\left{\left{\dots\right}\right}\right}$

例子：不存在集合$A$，$B$使得$A\in B$且$B\in A$

证明：假设存在集合，由集合公理得到$\left{A,B\right}$也是一个集合，这个集合与正则公理矛盾

例子：不存在$\left{S_0,S_1,S_2,\dots\right}$使得$\forall i\in\mathbb N$都有$S_i\in S_{i+1}$

证明：和上面的例子类似，反证然后用正则公理推出矛盾

##集合运算

然后介绍了差集(set difference)的概念，即$A\backslash B=A\backslash \left(A\cap B\right)=A\cap \overline B$

差集没有交换律，考虑这个例子：$A\cap B=\varnothing$，显然$A\backslash B\neq B\backslash A$

差集也没有结合律，考虑这个：$A\cap B\neq \varnothing$，$A\neq B=C$，则显然$A\backslash\left(B\backslash C\right)\neq\left(A\backslash B\right)\backslash C$

然后介绍了De Morgan Law：$A\backslash\left(B\cup C\right)=\left(A\backslash B\right)\cap\left(A\backslash C\right)$

证明：考虑用上面差集定义，那么$A\backslash\left(B\cup C\right)=A\cap\left({\overline{B\cup C} }\right)=A\cap\left({\overline B\cap\overline C}\right)\=\left(A\cap\overline B\right)\cap\left(A\cap\overline C\right)=\left(A\backslash B\right)\cap\left(A\backslash C\right)$

当然证明左右互相为对面的子集也是可以的

接下来引入了笛卡尔积(cartesian product)的概念

其中$\left(x,y\right)$是一个有序二元组(tuple)，它的集合定义是$\left{x,\left{x,y\right}\right}$或$\left{\left{\varnothing, \left{x\right}\right},\left{\left{y\right}\right}\right}$

但是n元组却不能简单地类似定义，例如$\left(x,\left(y,z\right)\right)$和$\left(\left(x,y\right),z\right)$是等价的3元组，但是在这种嵌套方式下它们不等价，所以很多时候数学的表达方式都不是最严谨的。。(比如说zhongsheng老湿的lecture notes)

##关系

定义在集合$A$上的二元关系(binary relation)指$R=A\times A=A^2$，类比还有n元关系

关系有一下四种性质，不同的关系满足其中一个或多个

1. 自反性(reflexive)：若$x\in A\Rightarrow\left(x,x\right)\in R$，则称这个关系具有自反性

2. 对称性(symmetric)：若$\left(x,y\right)\in R\iff \left(y,x\right)\in R$

3. 反对称性(anti-symmetric)：若$\left(x,y\right)\in R$且$\left(y,x\right)\in R\Rightarrow x=y$

4. 强反对称性(strongly anti-symmetric)：若$\left(x,y\right)\in R\Rightarrow \left(y,x\right)\not\in R$

5. 传递性(transitive)：若$\left(x,y\right),\left(y,z\right)\in R\Rightarrow \left(x,z\right)\in R$

##传递闭包

然后讲了传递闭包，也就是所谓的$Warshall- Floyd$算法，也就是最短路。。

证明思路留坑，反正也不难，来填坑了

$Warshall$算法的过程可以表述如下：

1. 枚举一个中间元素$k$

2. 枚举一个元素$i$

3. 枚举一个元素$j$

4. 若$\left(i,k\right)\in R$且$\left(k,j\right)\in R$，则将$\left(i,j\right)$加入$R$

5. 最后得到的$R=R^\star$

由于$k$是递增的，我们就可以根据$k$来归纳。我们说一条路径$< a , b

$指的是$\left(a,c_1\right),\left(c_1,c_2\right),\dots,\left(c_m,b\right)$这样首尾相连的关系链，再定义$k$-路径为除了首尾以外的点编号都不超过k的路径，记为$< a, b >_k$

那么第0次循环时，所有的路径都是0-路径，这个很简单

假设做到了第k+1次循环，那么对于$R^\star$中的关系有两种情况：

1. 这条路径上的最大点小于k+1，那么这条路径已经在前面的循环中被找出来加入$R$了

2. 这条路径上的最大点恰好等于k+1，那么此时从k+1处断开，剩下的两条链都已经在前面的循环中被加入了$R$，于是这里可以一步做完

3. 大于k+1，什么都没有发生……

##等价类的概念

如果一个集合$X$上的二元关系是自反的、对称的、传递的，那么这个关系就可以被称为一个等价关系(equivalence relation)

定理：集合$X$上的一个等价关系提供了$X$的一个划分(partition)

称$X$的一个划分为$Y$，当且仅当$\forall x,y\in Y$都有$x\cap y=\varnothing$，且$\cup Y=X$

若两个元素有等价关系，则我们称它们属于同一个等价类(equivalent class)

证明：首先由自反性可知等价关系至少包含了所有元素，因此只需要证明这些等价类不相交就可以了

反证法：假设存在一个元素$z$同时属于等价类$X$和$Y$且$X\neq Y$

任取$x\in X,y\in Y$，则$\left(x,z\right)\in R$且$\left(y,z\right)\in R$，由传递性可知$\left(x,y\right)\in R$，即$X=Y$，矛盾

##函数

接下来是函数基于二元关系的新定义。即$f: A\mapsto D$可以理解为$A\times D$的一个子集，满足每个A(定义域)中的元素只出现了一次

单射(injective)、双射(bijective)、满射(surjective)都很好理解，不说

函数的复合、求逆也很好理解，只需要注意复合运算的顺序就行了

再然后介绍了函数的函数(算子、泛函)的概念，提了一嘴函数式编程(functional programming)，只要知道lambda验算和图灵机是等价的应该就行了

需要注意的是，计算一个函数有时候是一件很难的事情(难以找到确定关系、复杂度不可接受)

还有非确定函数的概念(functionality)，这个在密码学中运用的比较广泛。比如给出一个输入$L$，输出一个长度为$L$的随机二进制串使得它满足一定的概率分布等等