学习笔记01

定义

定义 1.1 幂集

设是任意集合，的所有子集所组成的集合称为集合的幂集，记为或，即

容易知道

定义 1.2 笛卡尔积

集合和的笛卡尔积(直积)为

定义 1.3 关系

对集合和，的子集称为从到的二元关系。特别地，当时，称为上的二元关系

若则称与有关系，记为

若，为空关系，，为全关系

记

定义 1.4 值域和定义域

的一个子集 $存在，使得$ 称为的定义域，记为，称为的前域

的一个子集 $存在，使得$ 称为的值域，记为，称为的陪域

定义 1.5 特殊的二元关系

为集合上的二元关系

(1) 自反关系对任意有

(2) 反自反关系对任意有

(3) 对称关系对任意若则

(4) 反对称关系对任意若且则

或任意若且则

(5) 传递关系或任意若且则

注意一个满足传递关系和对称关系的关系不一定满足自反关系，这是因为自反关系要求对任意

对称性和传递性能保证：如果存在，则必有（对称），进而有和（传递：和推出；同理和推出 )。但如果某个元素完全与任何元素无关，即对于任何不满足或，那么对称性和传递性无法得到。

如果关系非空且 每个元素都至少与某个元素相关（即没有孤立元素），那么对称+传递确实能推出自反

对集合

定义 1.6 关系矩阵

对集合设，为它们之间的二元关系，称阶矩阵为的关系矩阵

其中 $（）（）$

对复合关系，它们的关系矩阵直接相乘即可得到复合关系的关系矩阵

定义 1.7 关系的逆

的逆关系定义为

注意等式成立

课堂小记

1.

证明集合 () 的广义结合律

记为一种任意的结合方法，我们只需证明

采用第二数学归纳法

当时，结论显然
假设时都成立，当时

证毕

2.

元集合，分别求上的自反关系、反自反关系、对称关系、反对称关系有多少个

自反关系有个

我们考虑下面这个表（表示了所有元素）

…

… …

对自反关系上面这个表的对角线元素一定存在，只需考虑其他元素是否存在即可
反自反关系有个

我们考虑下面这个表（表示了所有元素）

…

… …

对反自反关系上面这个表的对角线元素一定不存在，只需考虑其他元素是否存在即可
对称关系有个

我们考虑下面这个表（表示了所有元素）

…

… …

对自反关系上面这个表的对角线元素可能存在，先选择一次，有种选法，再考虑其他元素，进行配对，对元素配对共有 $C^{2}{n} $种，考虑每一个配对是否存在，共$ 2^{C{n}^{2}}$种选法
反对称关系有个

我们考虑下面这个表（表示了所有元素）

…

… …

对自反关系上面这个表的对角线元素可能存在，先选择一次，有种选法，再考虑其他元素，进行配对，对元素配对，为满足反对称的条件，有三种情况，①元素存在元素不存在，②元素存在元素不存在，③这个配对不存在。对每一个配对考虑选择一种情况，共种选法

(´-ω-｀)

集合与图论学习笔记01