在第 1 题至第 4 题中，请列举出集合中的元素来描述该集合。

1. \(\{x\in\mathbb{R}\mid x^2=3\}\)

解： \(\{\sqrt{3},-\sqrt{3}\}\)

2. \(\{m\in\mathbb{Z}\mid m^2=3\}\)

解： 空集 \(\varnothing\)

3. \(\{m\in\mathbb{Z}\mid mn=60\text{ for some }n\in\mathbb{Z}\}\)

解： \(\{\pm1,\pm2,\pm3,\pm4,\pm5,\pm6,\pm10,\pm12,\pm15,\pm20,\pm30,\pm60\}\)

4. \(\{m\in\mathbb{Z}\mid m^2-m\lt 115\}\)

解： \(\{-10,-9,-8,-7,-6,-5,-4,-3,-2,-1,0,1,2,3,4,5,6,7,8,10,11\}\)

在第 5 题至第 10 题中，请判断描述的对象是否真的是一个集合（是否明确定义）。为每个集合给出一个替代描述。

5. \(\{n\in\mathbb{Z}^+\mid n\text{ is a large number}\}\)

解： 不是明确定义。

6. \(\{n\in\mathbb{Z}\mid n^2\lt 0\}\)

解： 是明确定义。是空集 \(\varnothing\)。

7. \(\{n\in\mathbb{Z}\mid 39\lt n^3 \lt 57\}\)

解： 是明确定义。是空集 \(\varnothing\)。

8. \(\{x\in\mathbb{Q}\mid x\text{ is almost an integer}\}\)

解： 不是明确定义。

9. \(\{x\in\mathbb{Q}\mid x\text{ may be written with denominator greater than 100}\}\)

解： 是明确定义。是有理数集 \(\mathbb{Q}\)。

10. \(\{x\in\mathbb{Q}\mid x\text{ may be written with positive denominator less than 4}\}\)

解： 是明确定义。集合是所有 1、1/2、1/3 的倍数：

\(\{x\in\mathbb{Q}\mid x=a,x=\frac{a}{2},\text{or }x=\frac{a}{3}\text{ for }a\in\mathbb{Z}\}\)

11. 列出集合 \(\{a,b,c\}\times\{1,2,c\}\) 中的元素。

解：\(\{(a,1),(a,2),(a,c),(b,1),(b,2),(b,c),(c,1),(c,2),(c,c)\}\)

12. 设 \(A=\{1,2,3\}\) 且 \(B=\{2,4,6\}\)。对于给定为 \(A\times B\) 的子集之间的每个关系，判断它是否是一个从 \(A\) 映射到 \(B\) 的函数。如果它是一个函数，判断它是否是一一映射，以及它是否是映射到 \(B\) 的满射。

a. \(\{(1,4),(2,4),(3,6)\}\)

b. \(\{(1,4),(2,6),(3,4)\}\)

c. \(\{(1,6),(1,2),(1,4)\}\)

d. \(\{(2,2),(1,6),(3,4)\}\)

e. \(\{(1,6),(2,6),(3,6)\}\)

f. \(\{(1,2),(2,6),(2,4)\}\)

解：

a 是函数；不是一一映射，值 4 对应两个输入；不是满射，值 2 没有映射。

b 是函数；不是一一映射，值 4 对应两个输入；不是满射，值 2 没有映射。

c 不是函数，对应了多个输入 1。

tips:函数映射需要每个输入只能出现1次。

d 是函数；是一一映射；是满射。

e 是函数；不是一一映射，值 6 对应多个输入；不是满射，值 2、4 没有映射。

f 不是函数，对应了多个输入 2。

14. 请回忆一下，对于 \(a,b\in\mathbb{R}\)，并且 \(a \lt b\)，我们定义在实数集 \(\mathbb{R}\) 上的闭区间 \([a,b]\) 为 \([a,b]=\{x\in\mathbb{R}\mid a \le x \le b\}\)。为了证明给定的区间具有相同的元素数量，请提供一个函数 \(f\)，该函数是从第一个区间到第二个区间的一一映射，并给出其公式。

a. \([0,1]\text{ and }[0,2]\)

b. \([1,3]\text{ and }[5,25]\)

c. \([a,b]\text{ and }[c,d]\)

解：

a. \(f(x)=2x\)

b. \(f(x)=10x-5\)

c. \(f(x)=\frac{d-c}{b-a}(x-a)+c\)

15. 证明集合 \(S=\{x\in\mathbb{R}\mid 0 \lt x \lt 1\}\) 与 \(\mathbb{R}\) 具有相同的基数。【提示：找到一个微积分中的初等函数，该函数将一个区间一一映射到 \(\mathbb{R}\)，然后适当地平移和缩放以使定义域称为集合 \(S\)。】

解： 设 \(f(x)=tanx,-\frac{\pi}{2}\le x\le \frac{\pi}{2}\)，其值域就为 \(\mathbb{R}\)。

现在我们将定义域从 \([-\frac{\pi}{2},\frac{\pi}{2}]\) 到 \([0,1]\) 做线性变换，得 \(y=\frac{1}{\pi}(x+\frac{\pi}{2})\)。

令 \(g:S\to\mathbb{R}\)，\(g(y)=f(\pi y-\frac{\pi}{2})=tan(\pi(y-\frac{1}{2}))\)

对于任何集合 \(A\)，我们用 \(\mathscr{P}(A)\) 来表示 \(A\) 的所有子集的集合。例如，如果 \(A=\{a,b,c,d\}\)，那么 \(\{a,b,d\}\in\mathscr{P}(A)\)。集合 \(\mathscr{P}\) 被称为 \(A\) 的幂集。练习题 16 到 19 与集合 \(A\) 的幂集概念有关。

16. 列出所给集合的幂集的所有元素，并指出幂集的基数。

a. \(\varnothing\)

b. \(\{a\}\)

c. \(\{a,b\}\)

d. \(\{a,b,c\}\)

解：

a. \(\mathscr{P}=\{\varnothing\}\)；\(\lvert\mathscr{P}\rvert=1\)。

b. \(\mathscr{P}=\{\varnothing,\{a\}\}\)；\(\lvert\mathscr{P}\rvert=2\)。

c. \(\mathscr{P}=\{\varnothing,\{a\},\{b\},\{a,b\}\}\)；\(\lvert\mathscr{P}\rvert=4\)。

d. \(\mathscr{P}=\{\varnothing,\{a\},\{b\},\{c\},\{a,b\},\{a,c\},\{b,c\},\{a,b,c\}\}\)；\(\lvert\mathscr{P}\rvert=8\)。

17. 假设 \(A\) 是一个有限集合，且 \(\lvert A\rvert=s\)。基于前面的练习，对 \(\lvert \mathscr{P}(A)\rvert\) 的值提出一个猜想。然后尝试证明你的猜想。

解： \(\lvert\mathscr{P}(A)\rvert=2^s\)。因为 \(C(s,0)+C(s,1)+\ldots+C(s,s)=2^s\)

18. 对于任何集合 \(A\)，无论是有限的还是无限的，定义 \(B^A\) 为所有从 \(A\) 到集合 \(B=\{0,1\}\) 的函数的集合。请证明 \(B^A\) 的基数与 \(A\) 的幂集 \(\mathscr{P}(A)\) 的基数相等。【提示：\(B^A\) 中的每个元素都可以自然地与 \(A\) 的某个子集相对应。】

解： 先理解概念，以 \(A=\{a,b\}\) 举例。\(B^A\) 就是将 \(A\) 中的元素映射到 \(B=\{0,1\}\) 的函数。可以得：

\(f_1:f_1(a)=0,f_1(b)=0\)

\(f_2:f_2(a)=0,f_2(b)=1\)

\(f_3:f_3(a)=1,f_3(b)=0\)

\(f_4:f_4(a)=1,f_4(b)=1\)

我们可以发现 \(B^A\) 是可以映射到 \(\mathscr{P}(A)\) 的，还是以上述例子举例：

\(f_1:f_1(a)=0,f_1(b)=0\to\varnothing\)

\(f_2:f_2(a)=0,f_2(b)=1\to\{b\}\)

\(f_3:f_3(a)=1,f_3(b)=0\to\{a\}\)

\(f_4:f_4(a)=1,f_4(b)=1\to\{a,b\}\)

基于上述特例我们可以发现存在以下映射：

\(B^A\to\mathscr{P}(A):\Phi(f)=\{x\in A\mid f(x)=1\}\)

我们现在证明这个映射是双射。

(1)\(\Phi(f)\) 是单射：f 是函数是单射，也确保了 \(\Phi(f)\) 是单射。这确保了映射没有重复。

(2)\(\Phi(f)\) 是满射：对于 \(\mathscr{P}(A)\) 中的每个元素，我们定义 \(h:h(x)=\begin{cases}1 & x\in A \\ 0 & x\notin A\end{cases}\)。可以看出 \(\Phi(f)\) 必然是包含 \(h\) 中的各个情况的。这确保了映射没有遗留。

证明了 \(\Phi(f)\) 是双射，自然 \(\lvert B^A\rvert=\lvert\mathscr{P}(A)\rvert\)。

19. 请证明集合 \(A\)（无论是有限的还是无限的）的幂集所含元素超过了集合 \(A\) 本身。解释为什么这在直觉上意味着有无限多的无限基数。【提示：假设存在一个一一映射的函数 \(\phi\) 将 \(A\) 映射到 \(\mathscr{P}(A)\)。 通过考虑每个 \(x\in A\) 是否 \(x \in\phi(x)\)，并使用这个想法定义 \(A\) 的一个子集 \(S\)，来证明 \(\phi\) 不能满射 \(\mathscr{P}(A)\)。】“所有事物构成的集合”在逻辑上是一个可以被接受的观念吗？为什么可以或者为什么不行？

解： 定义 \(\phi:A\to \mathscr{P}(A)\)。

构造一个集合 \(Z=\{x\in A\mid x\notin \phi(x)\}\)，即 \(x\) 不在 \(\phi(x)\) 中的话就在 \(Z\) 中。

因为 \(Z\) 也是由 \(A\) 中元素构成的，所以 \(Z \in\mathscr{P}(A)\)。现在要证明 \(Z\) 这个集合是映射不到的：

如果存在某个 \(a\in A\)，使得 \(\phi(a)=Z\)，那么

(1)\(a\in Z\)，那么根据 \(Z\) 的定义，\(a \notin (\phi(a)=Z)\)。矛盾。

(2)\(a\notin Z\)，那么根据 \(Z\) 的定义，\(a \in (\phi(a)=Z)\)。矛盾。

所以不存在某个 \(a\in A\)，使得 \(\phi(a)=Z\)，即不是满射，即 \(A\) 的幂集所含元素超过了集合 \(A\) 本身。

基于以上结论，\(\mathbb{Z}\) 的基数是无限的，但是 \(\mathscr{P}(\mathbb{Z})\) 的基数比它还大，也是无限的；以此类推，其幂集的幂集的基数更大。所以有无限多的无限基数。

同样，如果有“所有事物构成的集合”，它们这个集合的幂集比它的数量还多，就不是“所有事物”了。所以“所有事物构成的集合”的概念不可行。

20. 令 \(A=\{1,2\}\) 和 \(B=\{3,4,5\}\)。

a. 使用集合 \(A\) 和 \(B\) 来说明我们为什么认为 \(2+3=5\)。采用相似的方式，使用你自己选择的集合来推断以下数值的结果：

i. \(3+\aleph_0\)

ii. \(\aleph_0+\aleph_0\)

b. 通过在平面 \(\mathbb{R}\times\mathbb{R}\) 中绘制集合 \(A\times B\) 的点来说明我们为什么认为 \(2\cdot3=6\)。参考书中的相关图形，推测 \(\aleph_0\cdot\aleph_0\) 的值。

解： a. 因为 \(A\cup B=\{1,2,3,4,5\}\) 中有 5 个元素，所以 \(\lvert A\rvert+\lvert B\rvert=2+3=\lvert A\cup B\rvert=5\)。

i. 设 \(A=\{a,b,c\}\)，\(B=\{e_0,e_1,e_2,\cdots\}\) 是可数集合。我们重新建立 \(A\cup B\) 到自然数的映射：

令 \(f(a)=0,f(b)=1,f(c)=2\)，接着让 \(B\) 中原先的映射往后挪 3 个位置，即 \(f(e_i)=i+3,i\in\mathbb{N}\)。

所以 \(3+\aleph_0=\aleph_0\)。

ii. 设 \(A=\{x_0,x_1,x_2,\cdots\}\) 是可数集合，\(B=\{y_0,y_1,y_2,\cdots\}\) 是可数集合。我们重新建立 \(A\cup B\) 到自然数的映射：

令 \(f(x_i)=2i,f(y_i)=2i+1,i\in\mathbb{N}\)，即把 \(A\) 映射到自然数偶数集合，\(B\) 映射到自然数的奇数集合。

所以 \(\aleph_0+\aleph_0=\aleph_0\)

b. 把两个集合元素按二维表格样式排列开，按书中 0.15 Figure 样式遍历，可以将笛卡尔积结果按顺序依次遍历，即映射到自然数。

所以 \(\aleph_0\cdot\aleph_0=\aleph_0\)

21. 在区间 \(0\le x\le 1\) 之间，有多少数能以 .## 的形式表示，其中每个 # 代表数字 \(0,1,2,3,\cdots,9\)？以 .##### 形式表达的数又有多少呢？基于此思路以及第 15 题的内容，你认为 \(10^{\aleph_0}\) 的值是多少？\(12^{\aleph_0}\) 和 \(2^{\aleph_0}\) 呢？

解： .## 形式的数字有 \(10^2\) 个；.##### 形式的数字有 \(10^5\) 个。

扩展开来，区间 \(0\le x\le 1\) 之间的数有 \(\aleph_0\) 位，即 \(10^{\aleph_0}\)。自然猜想，\(10^{\aleph_0}\) 就等于区间 \(0\le x\le 1\) 中数的个数。我们来证明一下。

以上按位数计算得到的 \(10^{\aleph_0}\ge\lvert [0,1]\rvert\)。原因是，里面会有数是重复的，比如 \(0.01=0.0\dot{9}\)。

如果我们将其当成，比如 12 进制的话，我们会得到 \(12^{\aleph_0}\)。因为底数更大，起码是要 \(10^{\aleph_0}\le\lvert [0,1]\rvert\)。所以 \(10^{\aleph_0}=\lvert [0,1]\rvert\)。

再看到第 15 题，我们已经证明 \(\lvert [0,1]\rvert=\lvert\mathbb{R}\rvert\)。所以 \(10^{\aleph_0}=\lvert\mathbb{R}\rvert\)。

同样按照改变进制基数的方式，可以得到 \(12^{\aleph_0}=2^{\aleph_0}=\lvert\mathbb{R}\rvert\)。

22. 继续前一个练习中的想法，并结合练习 18 和 19，使用指数记法填写下列三个空白，目的是列出五个基数，每一个都大于前一个。

\(\aleph_0,\lvert\mathbb{R}\rvert ,\underline{\hspace{10pt}},\underline{\hspace{10pt}},\underline{\hspace{10pt}},\)

解： \(\aleph_0,\lvert\mathbb{R}\rvert ,2^{\lvert\mathbb{R}\rvert},2^{2^{\lvert\mathbb{R}\rvert}},2^{2^{2^{\lvert\mathbb{R}\rvert}}}\)

在练习 23 到 27 中，找出具有给定元素数量的集合可以有多少种不同的划分方式。

23. 1 个元素

24. 2 个元素

25. 3 个元素

26. 4 个元素

27. 5 个元素

解： 1 个元素：1 种。

2 个元素：\(S(2,1)+S(2,2)=1+1=2\) 种。

3 个元素：

\(S(3,1)=1\)

\(S(3,2)=S(2,1)+2\cdot S(2,2)=1+2=3\)

\(S(3,3)=1\)

共计 5 种。

4 个元素：

\(S(4,1)=1\)

\(S(4,2)=S(3,1)+2\cdot S(3,2)=1+2\cdot 3=7\)

\(S(4,3)=S(3,2)+3\cdot S(3,3)=3+3=6\)

\(S(4,4)=1\)

共计 15 种。

5 个元素：

\(S(5,1)=1\)

\(S(5,2)=S(4,1)+2\cdot S(4,2)=1+2\cdot 7=15\)

\(S(5,3)=S(4,2)+3\cdot S(4,3)=7+3\cdot 6=25\)

\(S(5,4)=S(4,3)+4\cdot S(4,4)=6+4\cdot 1=10\)

共计 52 种。

28. 考虑一个集合 \(S\) 的划分。在定义 0.18 之后的段落中解释了为什么

关系 \(x\ \mathscr{R}\ y\) 当且仅当 \(x\) 和 \(y\) 在同一个单元格中

满足等价关系的对称性条件。请编写类似的解释，说明为什么反射性和传递性属性也同样满足。

解：

1. 反射性：\(x\) 和 \(x\) 必然在同一个单元中，所以 \(x\ \mathscr{R}\ x\)。

2. 对称性：如果 \(x\ \mathscr{R}\ y\)，则代表 \(x\) 和 \(y\) 在同一个单元中，这不依赖于顺序，必然也有 \(y\ \mathscr{R}\ x\)。

3. 传递性：如果 \(x\ \mathscr{R}\ y\)，\(y\ \mathscr{R}\ z\)，则代表 \(x\) 和 \(y\) 在同一个单元格中，\(y\) 和 \(z\) 在同一个单元格中。划分的话，\(y\) 只能在一个单元格中，不会同时出现在多个单元格中。即 \(x\) 和 \(z\) 都处在 \(y\) 所在的单元格中，且这个单元格是唯一的，所以 \(x\ \mathscr{R}\ z\)。

在练习 29 至 34 中，确定给定的关系是否是集合上的等价关系。描述由每个等价关系产生的划分。

29. \(n\ \mathscr{R}\ m\ \text{in}\ \mathbb{Z}\ \text{if}\ nm>0\)

解： 不是等价关系。比如，\(n = 0\)，\(nn=0\)，不满足反射性。

30. \(x\ \mathscr{R}\ y\ \text{in}\ \mathbb{R}\ \text{if}\ x\ge y\)

解： 不是等价关系。比如，\(3\ge 2\)，但是 \(2\ngeq 3\)，不满足对称性。

31. \(x\ \mathscr{R}\ y\ \text{in}\ \mathbb{R}\ \text{if}\ \lvert x\rvert=\lvert y\rvert\)

解： 是等价关系。

1. 反射性：\(\lvert x\rvert=\lvert x\rvert\)。

2. 对称性：如果 \(\lvert x\rvert=\lvert y\rvert\)，那么 \(\lvert y\rvert=\lvert x\rvert\) 也成立。

3. 传递性：如果 \(\lvert x\rvert=\lvert y\rvert\)，\(\lvert y\rvert=\lvert z\rvert\)，那么 \(\lvert x\rvert=\lvert z\rvert\) 也成立。

产生的划分即是相反数：

\(\overline{0}=\{0\}\)，\(\overline{a}=\{a,-a\}\ \text{for}\ a \in\ \mathbb{R}\ \text{and}\ a \ne 0\)

32. \(x\ \mathscr{R}\ y\ \text{in}\ \mathbb{R}\ \text{if}\ \lvert x-y\rvert\le 3\)

解： 不是等价关系。比如 \(\lvert 6-3\rvert\le 3\)，\(\lvert 3-0\rvert\le 3\)，但是 \(\lvert 6-0\rvert\nleq 3\)。不满足传递性。

33. \(n\ \mathscr{R}\ m\ \text{in}\ \mathbb{Z^+}\)，如果 \(n\) 和 \(m\) 在通常的十进制表示中有相同数量的位数

解： 是等价关系。产生的划分：所有 1 位数的集合、所有 2 位数的集合、所有 3 位数的集合、……

34. \(n\ \mathscr{R}\ m\ \text{in}\ \mathbb{Z^+}\)，如果 \(n\) 和 \(m\) 在十进制表示下具有相同的最后一位数

解： 是等价关系。产生 10 个划分：以 1 结尾的正整数 \(\overline{1}=\{1,11,21,\cdots\}\)；以 2 结尾的正整数 \(\overline{2}=\{2,12,22,\cdots\}\)；……；以 0 结尾的正整数 \(\overline{10}=\{10,20,30,\cdots\}\)。

35. 使用形式为 \(\{\texttt{#},\texttt{#},\texttt{#},\cdots\}\) 的集合表示法来表示无限集合，根据示例 0.17 中讨论的，在 \(\mathbb{Z^+}\) 中写出模 \(n\) 的剩余类，对于指定的 \(n\) 值。

a. \(n=2\)

b. \(n=3\)

c. \(n=5\)

解：

a. \(n=2\)：

\(\overline{0}=\{2,4,6,8,10,\cdots\}\)

\(\overline{1}=\{1,3,5,7,9,\cdots\}\)

a. \(n=3\)：

\(\overline{0}=\{3,6,9,12,15,\cdots\}\)

\(\overline{1}=\{1,4,7,10,13,\cdots\}\)

\(\overline{2}=\{2,5,8,11,14,\cdots\}\)

a. \(n=5\)：

\(\overline{0}=\{5,10,15,20,25,\cdots\}\)

\(\overline{1}=\{1,6,11,16,21,\cdots\}\)

\(\overline{2}=\{2,7,12,17,22,\cdots\}\)

\(\overline{3}=\{3,8,13,18,23,\cdots\}\)

\(\overline{4}=\{4,9,14,19,24,\cdots\}\)

36. 设 \(n \in \mathbb{Z^+}\)，并在整数集 \(\mathbb{Z}\) 上定义关系 \(\sim\)，使得 \(r\sim s\) 当且仅当 \(r-s\) 可以被 \(n\) 整除，即当且仅当 \(r-s=nq\)，对于某个 \(q \in \mathbb{Z}\)。

a. 证明 \(\sim\) 是 \(\mathbb{Z}\) 上的等价关系。（它被称为“模 \(n\) 同余”，就像它在 \(\mathbb{Z^+}\) 上一样。见 b 部分。）

b. 证明当这个关系 \(\sim\) 限制在 \(\mathbb{Z}\) 的子集 \(\mathbb{Z^+}\) 上时，这个 \(\sim\) 是示例 0.20 中提到的模 \(n\) 同余的等价关系。

c. 这个 \(\mathbb{Z}\) 的划分的单元是 \(\mathbb{Z}\) 中的模 \(n\) 剩余类。重复练习 35，但对于 \(\mathbb{Z}\) 中的模 \(n\) 剩余类，而不是 \(\mathbb{Z^+}\) 中的剩余类，使用表示无限集合的符号 \(\{\cdots,\texttt{#},\texttt{#},\texttt{#},\cdots\}\)。

解：

a.

1.反射性：因为 \(r-r=0\)，可以被 \(n\) 整除，即 \(r\sim r\)。

2.对称性：如果 \(r\sim s\)，即 \(r-s=nq\)，则 \(s-r=n\cdot(-q)\)。即 \(s\sim r\) 也成立。

3.传递性：如果 \(r\sim s\)，\(s\sim t\)，即 \(r-s=nq_1\)，\(s-t=nq_2\)，则 \(r-t=n(q_1+q_2)\)。即 \(r\sim t\) 也成立。

b.

设 \(h,k\in\mathbb{Z^+}\)，它们模 \(n\) 同余，即除以 \(n\) 的余数相等，则有

\(h=nq_1+r\)，\(k=nq_2+r\)

即 \(h-k=n(q_1-q_2)=nq\)，所以是等价的。

c. 只要加上负数的情况即可。