离散数学-1

设 X 是一个非空集合,A_n ⊆ X, A_n + 1 ⊆ A_n, n ∈ N⁺

证明: ∀n, $A_n=^{}{m=n}(A_mA{m+1}^c)({}_{m=n}A_m) $

[证明]

由于 A_m + 1 ⊆ A_m，故 A_m ∩ A_m + 1^c = A_m \ A_m + 1

因为 m ≥ n，故 A_m ⊆ A_n，显然有 $$ \displaystyle \bigcup\limits_{m=n}^\infty (A_m \cap A_{m+1}^c) \cup \bigcap\limits_{m=n}^\infty A_m \subseteq A_n $$ 对于 ∀x ∈ A_n，假设存在 p(p ≥ n)，使得 x ∈ A_p，必可找到其中最小的值 p₀，使得 x ∈ A_p0 \ A_p0 + 1( x 被丢掉,一定存在丢掉 x 的时候)

故 $$ \displaystyle \forall x \in A_n,x \in \bigcup\limits_{m=n}^\infty (A_m \cap A_{m+1}^c)\subseteq \bigcup\limits_{m=n}^\infty (A_m \cap A_{m+1}^c) \cup \bigcap\limits_{m=n}^\infty A_m $$ (所有被丢掉的 x 都属于这个集合.)

假如不存在 p，则: $\displaystyle x \in \bigcap\limits_{m=n}^\infty A_m$，故 $$ \displaystyle x \in \bigcup\limits_{m=n}^\infty (A_m \cap A_{m+1}^c) \cup \bigcap\limits_{m=n}^\infty A_m $$ (没被丢掉的 x)

综上可得： $$ \displaystyle A_n \subseteq \bigcup\limits_{m=n}^\infty (A_m \cap A_{m+1}^c) \cup \bigcap\limits_{m=n}^\infty A_m $$ 所以 $$ \displaystyle A_n = \bigcup\limits_{m=n}^\infty (A_m \cap A_{m+1}^c) \cup \bigcap\limits_{m=n}^\infty A_m $$

设 A₁, A₂, ⋯ 为一集序列，记 $\overline{A}$ 为这样的元素的全体形成的集合：$x \in \overline{A}$ 当且仅当在序列 A₁, A₂, ⋯ 中有无穷多项 A_n 含有 x。集合 $\overline{A}$ 称为集序列 A₁, A₂, ⋯ 的上极限，记为 $\displaystyle \varlimsup_{n \to \infty} A_n = \overline{A}$。又记 $\underline{A}$ 为这样的元素全体形成的集合:序列 A₁, A₂, ⋯ 中只有有限项不含有这样的元素。称 $\underline{A}$ 为序列 A₁, A₂, ⋯ 的下极限，并记 $\displaystyle \varliminf_{n \to \infty} A_n = \underline{A}$。

证明； $$ (1) \quad \varliminf_{n \to \infty} A_n = \bigcup_{n=1}^{\infty} \bigcap_{k=n}^{\infty} A_k \text{；} $$ $$ (2) \quad \varlimsup_{n \to \infty} A_n = \bigcap_{n=1}^{\infty} \bigcup_{k=n}^{\infty} A_k \text{;} $$ $$ (3)\quad \displaystyle \varliminf_{n \to \infty} A_n \subseteq \varlimsup_{n \to \infty} A_n \text{;} $$

$$ (4)设有单调上升集序列 A_1 \subseteq A_2 \subseteq A_3 \subseteq \cdots\\证明：\varliminf_{n \to \infty} A_n = \varlimsup_{n \to \infty} A_n。 $$

$$ (5)\displaystyle \underline{A}^c = \varliminf_{n \to \infty} A_n^c\quad\overline{A}^c = \varlimsup_{n \to \infty} A_n^c。 $$

[证] （1）$\forall x \in \varliminf_{n \to \infty} A_n$，在序列 A₁, A₂, ⋯ 中只有有限项不含 x，在不含 x 的项中必可找到下标最大的一项 A_p − 1（若各项均含 x，则令 p = 0），有 $x \in \bigcap_{k=p}^{\infty} A_k$，故 $x \in \bigcup_{n=1}^{\infty} \bigcap_{k=n}^{\infty} A_k$，即 $$ \varliminf_{n \to \infty} A_n \subseteq \bigcup_{n=1}^{\infty} \bigcap_{k=n}^{\infty} A_k。 $$

反之，$\forall x \in \bigcup_{n=1}^{\infty} \bigcap_{k=n}^{\infty} A_k$，必 ∃p 使得 $x \in \bigcap_{k=p}^{\infty} A_k$，即 ∀k ≥ p 时，x ∈ A_k。而集合 A₁, A₂, ⋯, A_p − 1 中即使都不含有 x，但也仅有有限项不含 x，故 $x \in \varliminf_{n \to \infty} A_n$。因此

$$ \bigcup_{n=1}^{\infty} \bigcap_{k=n}^{\infty} A_k \subseteq \varliminf_{n \to \infty} A_n。 $$

综上可得：

$$ \varliminf_{n \to \infty} A_n = \bigcup_{n=1}^{\infty} \bigcap_{k=n}^{\infty} A_k。 $$ (2)$\forall x \in \varlimsup_{n \to \infty} A_n$，因为 A₁, A₂, ⋯ 中有无穷多项含有 x，故 ∃N，当 n ≥ N 时，x ∈ A_n，因此 $x \in \bigcup_{k=n}^{\infty} A_k$，从而 $x \in \bigcap_{n=1}^{\infty} \bigcup_{k=n}^{\infty} A_k$，即 $$ \varlimsup_{n \to \infty} A_n \subseteq \bigcap_{n=1}^{\infty} \bigcup_{k=n}^{\infty} A_k。 $$

反之，$\forall x \in \bigcap_{n=1}^{\infty} \bigcup_{k=n}^{\infty} A_k$，则 $\forall n \geq 1, x \in \bigcup_{k=n}^{\infty} A_k$，即 A₁, A₂, ⋯ 中有无穷多项多含 x，所以 $x \in \varlimsup_{n \to \infty} A_n$，即

$$ \bigcap_{n=1}^{\infty} \bigcup_{k=n}^{\infty} A_k \subseteq \varlimsup_{n \to \infty} A_n。 $$

综上可得：

$$ \varlimsup_{n \to \infty} A_n = \bigcap_{n=1}^{\infty} \bigcup_{k=n}^{\infty} A_k。 $$ (3) $\forall x \in \varliminf_{n \to \infty} A_n$，由 $\varliminf_{n \to \infty} A_n$ 定义可知：序列 A₁, A₂, ⋯ 中只有有限项不含 x，故必可找到不含 x 的下标最大的一项 A_p，可见此时 A_p + 1, A_p + 2, ⋯ 均含 x，即有无限项含 x，故 $x \in \varlimsup_{n \to \infty} A_n$。因此

$$ \varliminf_{n \to \infty} A_n \subseteq \varlimsup_{n \to \infty} A_n。 $$ (4) 由(3)知 $$ \forall x \in \underline{A},x\in \overline{A}\Rightarrow \underline{A} \subseteq \overline{A} $$ 类似地: $$ \forall x \in \varlimsup_{n \to \infty} A_n = \overline{A} $$

因为: A₁ ⊆ A₂ ⊆ A₃ ⊆ ⋯ 所以有一个最大的 p₀: $$ \exist p_0 \in N,\forall n\in N,n \ge p_0,x \in A_n $$

这样满足下极限定义,即有: $$ \forall x \in \overline{A},x\in \underline{A}\Rightarrow \overline{A} \subseteq \underline{A} $$ 综上: $$ \varliminf_{n \to \infty} A_n = \varlimsup_{n \to \infty} A_n $$ (5)

对(1)(2)分别用德摩根定律即可.

设 A ⊆ X, B ⊆ Y，试证：(A × B)^C = (A^C × B) ∪ (A × B^C) ∪ (A^C × B^C)。

[证] ∀(x, y) ∈ (A × B)^C，则 (x, y) ∉ (A × B)，故 x ∉ A 或 y ∉ B。于是

1. 若 x ∉ A，则 x ∈ A^C。因此
   • 1. 若 y ∈ B，则 (x, y) ∈ A^C × B ⊆ (A^C × B) ∪ (A × B^C) ∪ (A^C × B^C)。
   • 2. 若 y ∉ B，则 y ∈ B^C，即 (x, y) ∈ A^C × B^C ⊆ (A^C × B) ∪ (A × B^C) ∪ (A^C × B^C)。
2. 若 x ∈ A，则必有 y ∉ B，故 (x, y) ∈ A × B^C ⊆ (A^C × B) ∪ (A × B^C) ∪ (A^C × B^C)。

综上可得：(A × B)^C ⊆ (A^C × B) ∪ (A × B^C) ∪ (A^C × B^C)。

反之，∀(x, y) ∈ (A^C × B) ∪ (A × B^C) ∪ (A^C × B^C)，则 (x, y) ∈ A^C × B 或 (x, y) ∈ A × B^C 或 (x, y) ∈ A^C × B^C，于是，

• 1. 若 (x, y) ∈ A^C × B，则 x ∉ A 且 x ∈ B，即 (x, y) ∉ A × B，于是 (x, y) ∈ (A × B)^C。
• 2. 若 (x, y) ∈ A × B^C，则 x ∈ A 且 x ∉ B，即 (x, y) ∉ A × B，于是 (x, y) ∈ (A × B)^C。
• 3. 若 (x, y) ∈ A^C × B^C，则 x ∉ A 且 x ∉ B，即 (x, y) ∉ A × B，于是 (x, y) ∈ (A × B)^C。

综上可得：(A^C × B) ∪ (A × B^C) ∪ (A^C × B^C) ⊆ (A × B)^C。

一个人写了十封信,有十个信封.随机将信装进信封求每封信都装错了的概率

考虑一个更加一般的情形: n 封信, n 个信封.

一个递推关系：第i封信是否装错信封的概率与前i − 1封信是否装错有关系.立刻想到使用数学归纳法,记i封信完全错排的方法数为D_i：

• ①先放置第1封信,有n − 1种方法.假设第一封信被放入第k个信封中.
• ② 1.若把第k封信放入第1个信封中.则1, k的位置确定.剩下n − 2封信.错排数为D_n − 2 2.若不把第k封信放入第1个信封中.则1的位置确定,剩下n − 1封信,错排数为D_n − 1

由加法原理和乘法原理,错排数

$$ \begin{align*} D_n - nD_{n-1} &= (n-1)(D_{n-1} + D_{n-2}) - nD_{n-1} \\ &= -[D_{n-1} - (n-1)D_{n-2}] \\ &= (-1)^2[D_{n-2} - (n-3)D_{n-3}] \\ &= \cdots \\ &= (-1)^{n-2} (D_2 - 2D_1) \\ &= (-1)^n \\ \\ &\Rightarrow D_n = nD_{n-1} + (-1)^n \end{align*} $$ 两边同时除以n!

$$ \begin{align*} \frac{D_n}{n!} = \frac{D_{n-1}}{(n-1)!} + \frac{(-1)^n}{n!}\\ \Rightarrow \frac{D_n}{n!} - \frac{D_{n-1}}{(n-1)!} = \frac{(-1)^n}{n!} \end{align*} $$

累加有：

$$ \begin{align*} D_n = n! \sum_{i=0}^n \frac{(-1)^i}{i!} \end{align*} $$

故装错所有n封信的概率 $$ \begin{align*} P_n = \sum_{i=0}^n \frac{(-1)^i}{i!} \end{align*} $$

由e^x的麦克劳林展开$\displaystyle \sum_{i=0}^n \frac{(x)^i}{i!}$,可知在 n 很大时,P_n ≈ e⁻¹

毕业舞会上，小伙子与姑娘跳舞，已知每个小伙子至少与一个姑娘跳过舞，但未能与所有姑娘跳过。同样地，每个姑娘也至少与一个小伙子跳舞，但也未能与所有的小伙子跳过舞。

证明：在所有参加舞会的小伙与姑娘中，必可找到两个小伙子和两个姑娘，这两个小伙子中的每一个只与这两个姑娘中的一个跳过舞，而这两个姑娘中的每一个也只与这两个小伙中的一个跳过舞。

提示:试着画个图吧.

[证] 设 F = {f₁, f₂, ⋯, f_n} 是小伙的集合，G = {g₁, g₂, ⋯, g_m} 是姑娘的集合。

与 f₁ 跳舞的姑娘的集合用 G_f1 表示；

与 f₂ 跳舞的姑娘的集合用 G_f2 表示；

⋮  ⋮  ⋮

与 f_n 跳舞的姑娘的集合用 G_fn 表示；

于是，由题意：G_f1 ∪ G_f2 ∪ ⋯ ∪ G_fn = G 且 G_fi ≠ ∅ 且 G_fi ≠ G，i = 1, 2, 3, ⋯, n。

若存在 G_fi, G_fj(i ≠ j)，使得 G_fi ⊈ G_fj 且 G_fj ⊈ G_fi，则结论成立。

反证法：假设不存在 G_fi 和 G_fj 满足 G_fi ⊈ G_fj 且 G_fj ⊈ G_fi。于是 ∀i, j(i ≠ j), G_fi 与 G_fj 应满足：G_fi ⊆ G_fj 或 G_fj ⊆ G_fi 必有一个成立。

因此把 G_f1, G_f2, ⋯, G_fn 重新排列有：G_fi1 ⊆ G_fi2 ⊆ ⋯ ⊆ G_fin。从而 f_in 与所有的姑娘都跳过舞，矛盾。

因此假设不成立，本题得证。