集合与图论学习笔记01

定义

定义 1.1 幂集

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

容易知道

---

定义 1.2 笛卡尔积

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

---

定义 1.3 关系

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

​ 若则称与有关系，记为

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

​ 记

---

定义 1.4 值域和定义域

的一个子集称为的定义域，记为，称为的前域

​的一个子集称为的值域，记为，称为的陪域

---

定义 1.5 特殊的二元关系

为集合上的二元关系

​ (1) 自反关系 对任意有

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

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

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

​ 或任意若且则

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

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

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

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

对集合

---

定义 1.6 关系矩阵

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

其中

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

---

定义 1.7 关系的逆

的逆关系定义为

注意等式成立

---

课堂小记

1.

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

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

采用第二数学归纳法

1. 当时，结论显然

2. 假设时都成立，当时
   

证毕

---

2.

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

1. 自反关系有个

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

   			…
   …			…

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

2. 反自反关系有个

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

   			…
   …			…

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

3. 对称关系有个

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

   			…
   …			…

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

4. 反对称关系有个

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

   			…
   …			…

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