集图问题集

在担任集图助教的过程中遇到了各种各样的问题,这里记录一些常见的,或是值得被记下来的问题.


PART 1: Set Theory

所有归纳集为什么不是集合

书和课件中都只说了“这会导致集合论悖论”,十分笼统. 这里给出一个简短的证明:

证明:在 ZF 公理系统中,所有归纳集不构成一个集合.

用 ZF 公理系统中的正则公理来证明:

  • 正则公理(Axiom of Regularity)\(\forall A,\exists x:(\exists z:z\in A)\Rightarrow (x\in A\wedge (\neg\exists y: y\in A\wedge y\in x))\).

假设所有的归纳集构成一个集合 \(D\),则我们可以将 \(D\) 扩充成一个归纳集 \(X\)(将 \(D\) 子集的所有内容物全部加入 \(X\) 中). 此时,由 \(D\)\(X\) 的定义,有 \(D\in X\in D\). 构造集合 \(\{D,X\}\)(容易验证这是一个集合),则对 \(\forall Y\in \{D,X\}\),均有 \(Y\cap \{D,X\}\) 非空. 这与正则公理矛盾. 因此 \(D\) 不是一个集合.

这里再强调一次李老师课件中的一个辨析:

  • 自然数属于所有归纳集的集合;
  • 自然数集 \(\mathbb{N}\)包含于所有归纳集的集合.

基数和序数

通俗地说,就是:

  • 序数是表示次序的数(数数的时候会数到的数):\[1,2,\ldots,n,\ldots,\aleph_0,\aleph_0+1,\ldots,\aleph_1,\ldots,\aleph_n,\ldots\]
  • 基数是序数的等价类:\[1,2,\ldots,n,\ldots,\aleph_0,\aleph_1,\aleph_2,\ldots,\aleph_n,\ldots\]

有关序数,有各种严格的定义. 较早的版本规定“序数”是良序集在保序映射下的等价类,而 ZF 系统中无法接受如此大的“集合”(现代会将其称为一个 class),因此“序数”的现行定义为“对 \(\in\) 关系构成良序集的传递集”. 现行定义使用代表元来描述序数,这样就避开了“良序集等价类”这一宏大的概念. 限于篇幅,这里不再展开.

2018 期中问题集

填空题 (4)

  1. 直线上所有开区间的集合的基数是?
  2. 平面上所有曲线的集合的基数是?(曲线是闭区间在连续映射下的像)

答案:(i) \(\aleph_1\);(ii) \(\aleph_1\).

  1. 这个比较显然,左右端点都有 \(\aleph_1\) 种取法,因此开区间有 \(\aleph_1\times\aleph_1=\aleph_1\) 种取法;

  2. 由于是连续映射,因此曲线完全由该映射在有理点处的取值确定(由闭区间套原理立得),故其基数为 \({\aleph_1}^{\aleph_0}=\aleph_1\).

2020 期中问题集

第 33 题

考虑如 \(\mathscr{P}(\mathbb{N})\) 中的等价关系:\(A\sim B\) 当且仅当 \(A\triangle B\) 为有限集.

  1. 给定 \(A\in \mathscr{P}(\mathbb{N})\),求 \(A\) 的等价类 \([A]\) 的势;
  2. 求商集 \(\mathscr{P}(\mathbb{N})/\sim\) 的势.

答案:1. \(\aleph_0\);2. \(\aleph_1\).

  1. 事实上,\(A\) 的等价类中的所有元素均可通过“删掉有限个元素,再添加有限个新元素”得到,易见这两步的操作方案数都是可数的,因此 \(|[A]|=\aleph_0\)
  2. 易见上界是 \(\aleph_1\),确定下界的方法有两种,分述如下:
    • 由第 1 问,容易构造单射 \(f\colon \mathscr{P}(\mathbb{N})\to \mathscr{P}(\mathbb{N})/\sim \times \mathbb{N}\),结合 \(|\mathscr{P}(\mathbb{N})|=\aleph_1\) 可知 \(|\mathscr{P}(\mathbb{N})/\sim|\times \aleph_0\geqslant \aleph_1\)
    • 考虑集族 \(S_m=\{p^k~|~k\in\mathbb{N},p~为第~m~个素数\}\),易见该集族有 \(\aleph_0\) 个不相交集合,且对不同的 \(T\subseteq \mathbb{N}\)\(\bigcup\limits_{m\in T} S_m\) 均属于不同的等价类. 由于 \(T\)\(\aleph_1\) 种选法,因此 \(|\mathscr{P}(\mathbb{N})/\sim|\) 至少为 \(\aleph_1\).

2021 期中问题集

第 29 题

判断:对于任意有穷基数 \(n\) 和无穷基数 \(\kappa\),总有 \(\kappa^n=\kappa\).

错误. 当 \(n=0\) 时,显然不成立. (当 \(n\neq 0\) 时,该断言是正确的)

这题太坑了,我在考场上随手做了一下就被坑到了(

第 31 题

题面写得不太严谨,这里给出一个(我自认为)较为严谨的版本:

\(R\) 是集合 \(A\) 上的偏序关系,且其最长链和最长反链长度均为 \(3\),则 \(A\) 的最小基数是多少?在此基数下,画出 \(R\) 互不同构的所有可能哈斯图.

易知 \(A\) 最少有 \(5\) 个元素(不难证明 \(4\) 个元素无法满足条件). 共 16 种哈斯图同构类,分类如下:

  1. 除最长链外,至多有一条边的,共 5 种

    0
    1
    2
    3
    4
    1 2 3 3 3
  2. 除最长链外,还有两条边的,共 7 种

    11
    12(最长反链只有 2)
    13
    14
    1 2 3 3
    21
    22
    23(最长反链只有 2)
    24
    同 12
    4 5 6
    31
    32
    33
    34(最长反链只有 2)
    同 13
    同 23
    7 8
    41
    42
    43
    44
    同 14
    同 24
    同 34
    9
  3. 有多条最长链(有环)的,共 4 种

    1
    2
    3
    4
    2 3 3 3

应该不难看出我的分类依据,也很容易验证这是不重不漏的. 阅卷时好像是写出至少 11 个就基本给满分了.

第 32 题

\(\oplus\) 表示对称差,求证:\(\left(\bigcap\limits_{i=1}^n A_i\right)\oplus \left(\bigcap\limits_{i=1}^n B_i\right)=\bigcup\limits_{i=1}^n(A_i\oplus B_i)\).

标答做法:(应该是最好的证法)由对称差的定义,对于 \(\forall x\in \operatorname{LHS}\),有且仅有两种情况:

  1. \(x\) 属于所有的 \(A\),但至少不属于某一个 \(B\). 不妨设 \(x\notin B_i\),则 \(x\in A_i\oplus B_i\subseteq \operatorname{RHS}\)
  2. \(x\) 属于所有的 \(B\),但至少不属于某一个 \(A\). 不妨设 \(x\notin A_j\),则 \(x\in A_j\oplus B_j\subseteq \operatorname{RHS}\).

OK. 这样证明就结束了,简洁又直观.

归纳法:归纳方法可能不唯一,不过本质应该都是 \(n=2\) 的情形.

  1. \(n=1\) 时,\(\operatorname{LHS}=\operatorname{RHS}\)

  2. 设当 \(n=k\) 时原式成立,则 \(n=k+1\) 时(令 \(A=\bigcap\limits_{i=1}^k A_i\)\(B=\bigcap\limits_{i=1}^k B_i\)),有: \[ \begin{align} \operatorname{LHS} &= (A\cap A_{n+1})\oplus (B\cap B_{n+1}) \\ &= \big((A\cap A_{n+1})\setminus (B\cap B_{n+1})\big) \cup \big( (B\cap B_{n+1})\setminus (A\cap A_{n+1}) \big) \\ &= \big((A\cap A_{n+1})\cap \overline{B\cap B_{n+1}}\big) \cup \big((B\cap B_{n+1})\cap \overline{A\cap A_{n+1}}\big) \\ &= \big((A\cap A_{n+1})\cap (\overline{B}\cup \overline{B_{n+1}})\big) \cup \big((B\cap B_{n+1})\cap (\overline{A}\cup \overline{A_{n+1}})\big) \\ &= (A\cap A_{n+1}\cap \overline{B})\cup (A\cap A_{n+1}\cap \overline{B_{n+1}}) \cup (B\cap B_{n+1}\cap \overline{A})\cup (B\cap B_{n+1}\cap \overline{A_{n+1}}) \\ &= (A_{n+1}\cap A\setminus B)\cup (A\cap A_{n+1}\setminus B_{n+1}) \cup (B_{n+1}\cap B\setminus A)\cup (B\cap B_{n+1}\setminus A_{n+1}) \\ &\subseteq (A\setminus B)\cup (A_{n+1}\setminus B_{n+1}) \cup (B\setminus A)\cup (B_{n+1}\setminus A_{n+1}) \\ &= (A\oplus B)\cup (A_{n+1}\oplus B_{n+1}) = \operatorname{RHS}. \end{align} \]

证明过程不困难,但有一点复杂,应该需要一些耐心(阅卷时感觉很多同学写得或多或少都有点问题)

另一种直接的证明:将对称差拆成 \(A\setminus B\)\(B\setminus A\) 两部分,则有: \[ \begin{align} \bigcap\limits_{i=1}^n A_i\setminus \bigcap\limits_{i=1}^n B_i &= \bigcap\limits_{i=1}^n A_i\cap \overline{\bigcap\limits_{i=1}^n B_i} = \bigcap\limits_{i=1}^n A_i\cap \bigcup\limits_{i=1}^n\overline{B_i} \\ &= \bigcup\limits_{i=1}^n \left(\overline{B_i}\cap \bigcap\limits_{j=1}^n A_j\right) \\ &= \bigcup\limits_{i=1}^n \left(\bigcap\limits_{j=1}^n A_j \setminus B_i\right) \\ &\subseteq \bigcup\limits_{i=1}^n \left(A_i \setminus B_i\right) \end{align} \] 另一半同理,合并起来即可完成证明. 该做法是阅卷时看到的,也是比较直观的一种做法.


PART 2: Graph Theory

所有奇圈共点 \(\Rightarrow\) 可被 5-染色

若一个图 \(G\) 中任意两个奇数长度的回路都有公共点,证明该图可被 \(5\)-染色.

\(\chi(G)\geqslant 6\),考虑颜色 \(1,2,3\) 的导出子图 \(G_1\) 和颜色 \(4,5,6\) 的导出子图 \(G_2\),则 \(G_1\cap G_2=\varnothing\). 由于 \(\chi(G_1)=\chi(G_2)=3\),故二者均不是二部图,因此 \(G_1\)\(G_2\) 均含有奇圈. 又由于 \(G_1\)\(G_2\) 无公共点,故这两个奇圈也无公共点,矛盾. 因此 \(\chi(G)\leqslant 5\).