集合与图论学习笔记01

定义

定义 1.1 幂集

设\(A\) 是任意集合，\(A\) 的所有子集所组成的集合称为集合 \(A\) 的幂集，记为 \(P(A)\) 或 \(2^{A}\) ，即 \(P(A) = \{ B|B\subseteq A\}\)

容易知道 \(\left | P(A) \right | =2^{|A|}\)

---

定义 1.2 笛卡尔积

集合 \(A\) 和 \(B\) 的笛卡尔积(直积)为 \(A\times B= \{ (a,b)|a\in A,b\in B \}\)

---

定义 1.3 关系

对集合 \(A\) 和 \(B\) ，\(A\times B\) 的子集 \(R\) 称为从\(A\) 到 \(B\) 的二元关系。特别地，当 \(A=B\) 时，称 \(R\) 为 \(A\) 上的二元关系

​ 若 \((a,b)\in R\) 则称 \(a\) 与 \(b\) 有关系 \(R\) ，记为 \(aRb\)

​ 若 \(R=\emptyset\) ， \(R\) 为空关系，\(R=A\times B\) ，\(R\) 为全关系

​ 记 \(\overline{R} = A\times B -R\)

---

定义 1.4 值域和定义域

\(A\) 的一个子集 \(\{ a|存在b，使得(a,b)\in R\}\) 称为 \(R\) 的定义域，记为 \(Dom R\) ，\(A\) 称为 \(R\) 的前域

​ \(B\) 的一个子集 \(\{ b|存在a，使得(a,b)\in R\}\) 称为 \(R\) 的值域，记为 \(Ran R\)，\(B\) 称为 \(R\) 的陪域

---

定义 1.5 特殊的二元关系

\(R\) 为集合 \(A\) 上的二元关系

​ (1) 自反关系 对任意 \(a\in A\) 有 \((a,a)\in R\)

\[ iff \space I_{A} \subseteq R \]

​ (2) 反自反关系 对任意 \(a\notin A\) 有 \((a,a)\in R\)

\[iff \space R \cap I_{A} = \emptyset\]

​ (3) 对称关系 对任意 \(a,b\in A\) 若 \((a,b)\in R\) 则 \((b,a)\in R\)

\[iff \space R=R^{-1}\]

​ (4) 反对称关系 对任意 \(a,b\in A\) 若 \((a,b)\in R\) 且 \((b,a)\in R\) 则 \(a=b\)

​ 或任意 \(a,b\in A\) 若 \((a,b)\in R\) 且 \(a \ne b\) 则 \((b,a)\notin R\)

\[iff \space R\cap R^{-1}\subseteq I_{A}\]

​ (5) 传递关系 或任意 \(a,b,c\in A\) 若 \((a,b)\in R\) 且 \((b,c)\in R\) 则 \((a,c)\in R\)

\[iff \space R \cdot R \subseteq R\]

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

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

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

\(e.g:\) 对集合 \(A=\{1,2,3\}\) \(R = \{(1,1),(1,2),(2,1),(2,2)\}\)

---

定义 1.6 关系矩阵

对集合设 \(|A|=m, |B|=n\)，\(R\) 为它们之间的二元关系，称 \(m\times n\) 阶矩阵 \(M_{R}=(m_{i,j})\) 为 \(R\) 的关系矩阵

其中 \(m=\begin{cases}1（a_{i},b{i}）\in R\\\\0（a_{i},b{i}）\notin R\end{cases}\)

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

---

定义 1.7 关系的逆

\(R\) 的逆关系 \(R^{-1}\) 定义为 \(R^{-1}=\{ (b,a)|(a,b)\in R) \}\)

注意等式 \(\overline{R}^{-1}=\overline{R^{-1}}\) 成立

---

课堂小记

1.

证明集合 \(A_i\) (\(i=1,2,...,n\)) 的广义结合律

记 \(\bigcup_{k=1}^{n}A_{k}=A_{1}\cup A_{2}\cup ...\cup A_{n}\) 为一种任意的结合方法，我们只需证明 \(\bigcup_{k=1}^{n}A_{k} = ((((A_{1}\cup A_{2})\cup A_{3})\cup...)\cup A_{n-1}) \cup A_{n}\)

采用第二数学归纳法

1. 当 \(n=1,2,3\) 时，结论显然

2. 假设 \(n \le k\) 时都成立，当 \(n = k+1\) 时 \[ \begin{align*} \bigcup_{i=1}^{k+1}A_{i} &= (\bigcup_{i=1}^{t}A_{i}) \cup (\bigcup_{i=t+1}^{k+1}A_{i})\\\\ &=(\bigcup_{i=1}^{t}A_{i}) \cup (((((A_{t+1}\cup A_{t+2})\cup...)\cup A_{k}) \cup A_{k+1})\\\\ &=(\bigcup_{i=1}^{t}A_{i}) \cup ((((A_{t+1}\cup A_{t+2})\cup...)\cup A_{k}) \cup A_{k+1} \\\\ &=((\bigcup_{i=1}^{t}A_{i}) \cup ((((A_{t+1}\cup A_{t+2})\cup...)\cup A_{k})) \cup A_{k+1} \\\\ &=(((((A_{1}\cup A_{2})\cup A_{3})\cup...)\cup A_{k-1}) \cup A_{k}) \cup A_{k+1} \\\\ \end{align*} \]

证毕

---

2.

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

1. 自反关系有 \(2^{n^{2}-n}\) 个

   我们考虑下面这个表（表示了 \(A^{2}\) 所有元素）

   	\(a_{1}\)	\(a_{2}\)	…	\(a_{n}\)
   \(a_{1}\)	\((a_{1},a_{1})\)	\((a_{1},a_{2})\)		\((a_{1},a_{n})\)
   \(a_{2}\)	\((a_{2},a_{1})\)	\((a_{2},a_{2})\)		\((a_{2},a_{n})\)
   …			…
   \(a_{n}\)	\((a_{n},a_{1})\)	\((a_{n},a_{2})\)		\((a_{n},a_{n})\)

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

2. 反自反关系有 \(2^{n^{2}-n}\) 个

   我们考虑下面这个表（表示了 \(A^{2}\) 所有元素）

   	\(a_{1}\)	\(a_{2}\)	…	\(a_{n}\)
   \(a_{1}\)	\((a_{1},a_{1})\)	\((a_{1},a_{2})\)		\((a_{1},a_{n})\)
   \(a_{2}\)	\((a_{2},a_{1})\)	\((a_{2},a_{2})\)		\((a_{2},a_{n})\)
   …			…
   \(a_{n}\)	\((a_{n},a_{1})\)	\((a_{n},a_{2})\)		\((a_{n},a_{n})\)

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

3. 对称关系有 \(2^{n}2^{C_{n}^{2}}\) 个

   我们考虑下面这个表（表示了 \(A^{2}\) 所有元素）

   	\(a_{1}\)	\(a_{2}\)	…	\(a_{n}\)
   \(a_{1}\)	\((a_{1},a_{1})\)	\((a_{1},a_{2})\)		\((a_{1},a_{n})\)
   \(a_{2}\)	\((a_{2},a_{1})\)	\((a_{2},a_{2})\)		\((a_{2},a_{n})\)
   …			…
   \(a_{n}\)	\((a_{n},a_{1})\)	\((a_{n},a_{2})\)		\((a_{n},a_{n})\)

   对自反关系 \(R\) 上面这个表的对角线元素可能存在，先选择一次，有 \(2^{n}\) 种选法，再考虑其他元素，进行配对，对元素 \(a,b\in A\) 配对 \(((a,b),(b,a))\) 共有 \(C^{2}_{n}\) 种，考虑每一个配对是否存在，共 \(2^{C_{n}^{2}}\)种选法

4. 反对称关系有 \(2^{n}3^{C_{n}^{2}}\) 个

   我们考虑下面这个表（表示了 \(A^{2}\) 所有元素）

   	\(a_{1}\)	\(a_{2}\)	…	\(a_{n}\)
   \(a_{1}\)	\((a_{1},a_{1})\)	\((a_{1},a_{2})\)		\((a_{1},a_{n})\)
   \(a_{2}\)	\((a_{2},a_{1})\)	\((a_{2},a_{2})\)		\((a_{2},a_{n})\)
   …			…
   \(a_{n}\)	\((a_{n},a_{1})\)	\((a_{n},a_{2})\)		\((a_{n},a_{n})\)

   对自反关系 \(R\) 上面这个表的对角线元素可能存在，先选择一次，有 \(2^{n}\) 种选法，再考虑其他元素，进行配对，对元素 \(a,b\in A\) 配对 \(((a,b),(b,a))\) ，为满足反对称的条件，有三种情况，①元素 \((a,b)\) 存在元素 \((b,a)\) 不存在，②元素 \((b,a)\) 存在元素 $ (a,b)$ 不存在，③这个配对不存在。对每一个配对考虑选择一种情况，共 \(3^{C_{n}^{2}}\) 种选法