离散数学-1

设 $X$ 是一个非空集合,$A_n \subseteq X,A_{n+1} \subseteq A_n,n\in N^+$

证明: $\forall n$, $\displaystyle A_n=\bigcup^{\infty}_{m=n}(A_m\bigcap A_{m+1}^c)\bigcup(\bigcap^{\infty}_{m=n}A_m)$

[证明]

由于 $A_{m+1} \subseteq A_m$，故 $A_m \cap A_{m+1}^c = A_m \setminus A_{m+1}$

因为 $m \geq n$，故 $A_m \subseteq 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$$

对于 $\forall x \in A_n$，假设存在 $p(p \geq n)$，使得 $x \in A_p$，必可找到其中最小的值 $p_0$，使得 $x \in A_{p_0} \setminus A_{p_0+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_1, A_2, \cdots$ 为一集序列，记 $\overline{A}$ 为这样的元素的全体形成的集合：$x \in \overline{A}$ 当且仅当在序列 $A_1, A_2, \cdots$ 中有无穷多项 $A_n$ 含有 $x$。集合 $\overline{A}$ 称为集序列 $A_1, A_2, \cdots$ 的上极限，记为 $\displaystyle \varlimsup_{n \to \infty} A_n = \overline{A}$。又记 $\underline{A}$ 为这样的元素全体形成的集合:序列 $A_1, A_2, \cdots$ 中只有有限项不含有这样的元素。称 $\underline{A}$ 为序列 $A_1, A_2, \cdots$ 的下极限，并记 $\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_1, A_2, \cdots$ 中只有有限项不含 $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$，必 $\exists p$ 使得 $x \in \bigcap_{k=p}^{\infty} A_k$，即 $\forall k \geq p$ 时，$x \in A_k$。而集合 $A_1, A_2, \cdots, 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_1, A_2, \cdots$ 中有无穷多项含有 $x$，故 $\exists N$，当 $n \geq N$ 时，$x \in 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_1, A_2, \cdots$ 中有无穷多项多含 $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_1, A_2, \cdots$ 中只有有限项不含 $x$，故必可找到不含 $x$ 的下标最大的一项 $A_p$，可见此时 $A_{p+1}, A_{p+2}, \cdots$ 均含 $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_1 \subseteq A_2 \subseteq A_3 \subseteq \cdots$$

所以有一个最大的 $p_0$:

$$\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 \subseteq X, B \subseteq Y$，试证：$(A \times B)^C = (A^C \times B) \cup (A \times B^C) \cup (A^C \times B^C)$。

[证] $\forall (x, y) \in (A \times B)^C$，则 $(x, y) \not\in (A \times B)$，故 $x \not\in A$ 或 $y \not\in B$。于是

1. 若 $x \not\in A$，则 $x \in A^C$。因此

   • (1) 若 $y \in B$，则 $(x, y) \in A^C \times B \subseteq (A^C \times B) \cup (A \times B^C) \cup (A^C \times B^C)$。
   • (2) 若 $y \not\in B$，则 $y \in B^C$，即 $(x, y) \in A^C \times B^C \subseteq (A^C \times B) \cup (A \times B^C) \cup (A^C \times B^C)$。

2. 若 $x \in A$，则必有 $y \not\in B$，故 $(x, y) \in A \times B^C \subseteq (A^C \times B) \cup (A \times B^C) \cup (A^C \times B^C)$。

综上可得：$(A \times B)^C \subseteq (A^C \times B) \cup (A \times B^C) \cup (A^C \times B^C)$。

反之，$\forall (x, y) \in (A^C \times B) \cup (A \times B^C) \cup (A^C \times B^C)$，则 $(x, y) \in A^C \times B$ 或 $(x, y) \in A \times B^C$ 或 $(x, y) \in A^C \times B^C$，于是，

• (1) 若 $(x, y) \in A^C \times B$，则 $x \not\in A$ 且 $x \in B$，即 $(x, y) \not\in A \times B$，于是 $(x, y) \in (A \times B)^C$。

• (2) 若 $(x, y) \in A \times B^C$，则 $x \in A$ 且 $x \not\in B$，即 $(x, y) \not\in A \times B$，于是 $(x, y) \in (A \times B)^C$。

• (3) 若 $(x, y) \in A^C \times B^C$，则 $x \not\in A$ 且 $x \not\in B$，即 $(x, y) \not\in A \times B$，于是 $(x, y) \in (A \times B)^C$。

综上可得：$(A^C \times B) \cup (A \times B^C) \cup (A^C \times B^C) \subseteq (A \times 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 \approx e^{-1}$

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

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

提示:试着画个图吧.

[证] 设 $F = \{f_1, f_2, \cdots, f_n\}$ 是小伙的集合，$G = \{g_1, g_2, \cdots, g_m\}$ 是姑娘的集合。

与 $f_1$ 跳舞的姑娘的集合用 $G_{f_1}$ 表示；

与 $f_2$ 跳舞的姑娘的集合用 $G_{f_2}$ 表示；

$\vdots \quad \vdots \quad \vdots$

与 $f_n$ 跳舞的姑娘的集合用 $G_{f_n}$ 表示；

于是，由题意：$G_{f_1} \cup G_{f_2} \cup \cdots \cup G_{f_n} = G$ 且 $G_{f_i} \neq \emptyset$ 且 $G_{f_i} \neq G$，$i=1,2,3,\cdots,n$。

若存在 $G_{f_i}, G_{f_j} (i \neq j)$，使得 $G_{f_i} \not\subseteq G_{f_j}$ 且 $G_{f_j} \not\subseteq G_{f_i}$，则结论成立。

反证法：假设不存在 $G_{f_i}$ 和 $G_{f_j}$ 满足 $G_{f_i} \not\subseteq G_{f_j}$ 且 $G_{f_j} \not\subseteq G_{f_i}$。于是 $\forall i,j (i \neq j), G_{f_i}$ 与 $G_{f_j}$ 应满足：$G_{f_i} \subseteq G_{f_j}$ 或 $G_{f_j} \subseteq G_{f_i}$ 必有一个成立。

因此把 $G_{f_1}, G_{f_2}, \cdots, G_{f_n}$ 重新排列有：$G_{f_{i_1}} \subseteq G_{f_{i_2}} \subseteq \cdots \subseteq G_{f_{i_n}}$。从而 $f_{i_n}$ 与所有的姑娘都跳过舞，矛盾。

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