离散数学-3

设 A 和 B 是两个集合，f : 2^A → 2^B。如果对 A 的任何子集 E 与 F 有 f(E ∪ F) = f(E) ∪ f(F)，则称 f 是可加的。

试证：一个从 A 到 B 的二元关系可定义为从 2^A 到 2^B 的一个可加映射。

[证]

考虑 (x, y) ∈ R ⊆ A × B

令 f(E) = {y|xRy, x ∈ E, E ⊆ A, y ∈ B} f : 2^A → 2^B,

令 E ⊆ A, F ⊆ A

若 y ∈ f(E ∪ F)

则, $ xE or x F $

• x ∈ E, y ∈ f(E)
• x ∈ F, y ∈ f(F)

即: $$ \forall y\in f(E\cup F),y\in f(E) \cup f(F)\\ f(E\cup F) \subseteq f(E) \cup f(F) $$ 反之亦然.问题得证

设 f : A → B，由 f 定义 A 上二元关系 Ker(f) 如下： Ker(f) = {(x, y)|(x, y) ∈ A × A 且 f(x) = f(y)}. 令 g, h : A → A，

证明：Ker(g) ⊇ Ker(h) 当且仅当存在 r : A → A 使得 g = r ∘ h。

[证]

⇒ 设 Ker(h) ⊆ Ker(g)。定义 r : A → A 如下：∀x ∈ h(A)，则定义 r(h(x)) = g(x)，若 $x Ah(A) $ ,则 r(x) = h(x) 于是，r 已定义好。

现在证明 r 已定义好：由于 Ker(h) ⊆ Ker(g)，所以 if (x, y) ∈ Ker(h)，则 (x, y) ∈ Ker(g)，从而 h(x) = h(y) ⇒ g(x) = g(y)

因此，∀x ∈ h(A). r(h(x)) = g(x) 合理

其次，∀x ∈ A \ h(A), r(x) = x，基于类似的原因,也是合理的

⇐ 设 g = r ∘ h，往证 Ker(h) ⊆ Ker(g)。

设 (x, y) ∈ Ker(h)，则 h(x) = h(y)，于是 g(x) = r ∘ h(x) = r(h(x)) = r(h(y)) = r ∘ h(y) = g(y)

因此，(x, y) ∈ Ker(g)，故 Ker(h) ⊆ Ker(g).

提示:比较抽象,建议通过绘图直观理解. 若学习过 『3.6等价关系与集合的划分』 则本题更易理解 此处不妨这么想: 我们将 Ker 集合按照像来划分为不同的部分,将所有经过映射后具有相同像的元素划入同一个部分记为 E ,这样有 Ker = {E₁ × E₁} ∪ {E₂ × E₂} ∪ ⋯{E_n × E_n}

结合题目.Ker(h) ⊆ Ker(g) 当且仅当 N_h > N_g 其中 N_h, N_g 分别为 Ker(h), Ker(g) 的划分数,关于这个『当且仅当』的正确性请自行证明

⇒ 考察 g 的导出映射, 其正是将 Ker 按上面的思路划分为若干个集合后,将这个由集合构成的集合作为自变量的映射.这样只要构造一个 r 使得经过 r 的作用,h 的导出映射变为 g 即可,若已知 Ker(h) ⊆ Ker(g),则 N_h > N_g, 映射 r 的存在性得到保证.

⇐ 十分简单,不再赘述.

设 f, g : A → A，

证明：|f(A)| ≤ |g(A)| 当且仅当存在 u, v : A → A，使得 f = u ∘ g ∘ v。

提示: 如无必要能力精力,不建议花费时间在此.本题需学习『3.6等价关系与集合的划分』 『3.7映射按等价关系分解』后才可理解部分符号和证明方法.

[证] ⇐ 设 f = u ∘ g ∘ v，则 f(A) = u(g(v(A)))，则 |f(A)| ≤ |g(v(A))| ≤ |g(A)|.

⇒ 设 |f(A)| ≤ |g(A)|，往证 f = u ∘ g ∘ v，但证明较复杂.

首先构造一个映射 t : A → A 使得 Ker(t) = Ker(f) 且 t(A) ⊆ g(A)：

因为 |f(A)| ≤ |g(A)|，所以存在一个子集 P ⊆ g(A) 使得 f(A) ∼ P，设此一一对应为 φ。

又因为 A/Ker(f) ∼ f(A)，所以不妨设此一一对应为 ψ，γ 是 A 到 A/Ker(f) 的自然映射。

令 t : A → P, ∀x ∈ A

t(x) = φψγ(x), 即 t = φψγ = ηγ.

显然，t(A) = φψγ(A) = φψ(A/Ker(f)) = φ(f(A)) = P ⊆ g(A).

其次，证明 Ker(t) = Ker(f)。实际上，∀(x, y) ∈ Ker(t) 有 t(x) = t(y)，即 ηγ(x) = ηγ(y)，由 η 的单射性便有 γ(x) = γ(y)

从而有 [x] = [y]，即 f(x) = f(y)，所以 (x, y) ∈ Ker(f)，因此，Ker(t) ⊆ Ker(f)。

其次，设 (x, y) ∈ Ker(f)，则 f(x) = f(y)，故 [x] = [y]。于是，t(x) = ηγ(x) = η([x]) = η([y]) = ηγ(y) = t(y)，从而 (x, y) ∈ Ker(t).

即，Ker(t) ⊇ Ker(f)。因此，Ker(t) = Ker(f)。

由 Ker(t) = Ker(f) 及上题知存在 u : A → A 使得 f = u ∘ t。

再由 t(A) ⊆ g(A) 知存 v : A → A 使得 t = g ∘ v，从而 f = u ∘ g ∘ v。

设 R 与 S 为 X 上的任两个集合，下列命题哪些为真？

• 1. 若 R, S 都是自反的，则 R ∘ S 也是自反的。
• 2. 若 R, S 都是对称的，则 R ∘ S 也是对称的。
• 3. 若 R, S 都是反自反的，则 R ∘ S 也是反自反的。
• 4. 若 R, S 都是反对称的，则 R ∘ S 也是反对称的。
• 5. 若 R, S 都是传递的，则 R ∘ S 也是传递的。

答案：真假假假假

设 R₁ 是 A 到 B，R₂ 和 R₃ 是 B 到 C 的二元关系，则一般情况下 R₁ ∘ (R₂ \ R₃) ≠ (R₁ ∘ R₂) \ (R₁ ∘ R₃) 但有人声称等号成立，他的证明如下：设 (a, c) ∈ R₁ ∘ (R₂ \ R₃)，则 ∃b ∈ X，使得 (a, b) ∈ R₁ 且 (b, c) ∈ R₂ \ R₃。于是 (b, c) ∈ R₂ 且 (b, c) ∉ R₃。从而 (a, c) ∈ R₁ ∘ R₂ 且 (b, c) ∉ R₁ ∘ R₃，所以 (a, c) ∈ (R₁ ∘ R₂) \ (R₁ ∘ R₃)，即 R₁ ∘ (R₂ \ R₃) ⊆ (R₁ ∘ R₂) \ (R₁ ∘ R₃)。同理可证相反的包含关系成立，故等式成立，这个证明错在什么地方？

[解] 由 (a, c) ∈ R₁，(b, c) ∈ R₂ 且 (b, c) ∉ R₃，只能得到 (a, b) ∈ R₁ ∘ R₂。但 (a, c) ∉ R₁ ∘ R₃ 不一定成立。 例如 (a, a) ∈ R₁，(a, c) ∈ R₃ 时，(a, c) ∈ (R₁ ∘ R₃) 故这步推理错误

设 R, S 是 X 上的满足 R ∘ S ⊆ S ∘ R 的对称关系，证明 R ∘ S = S ∘ R.

[证]

证法1：设 (x, z) ∈ S ∘ R，则 ∃y ∈ X，使得 (x, y) ∈ S 且 (y, z) ∈ R。

因为 R，S 均对称，所以 R = R⁻¹, S = S⁻¹

于是 (y, x) ∈ S⁻¹ = S, (z, y) ∈ R⁻¹ = R

从而 (z, x) ∈ R ∘ S, (x, z) ∈ (R ∘ S)⁻¹ ⊆ (S ∘ R)⁻¹ = R⁻¹ ∘ S⁻¹ = R ∘ S

因此 S ∘ R ⊆ R ∘ S

故 S ∘ R = R ∘ S

证法2：S ∘ R = S⁻¹ ∘ R⁻¹ = (R ∘ S)⁻¹ ⊆ (S ∘ R)⁻¹ = R⁻¹ ∘ S⁻¹ = R ∘ S，故 S ∘ R ⊆ R ∘ S，于是 R ∘ S = S ∘ R

设 R 为 X 上的对称关系，证明：∀n ∈ N, Rⁿ 是对称关系。

[证]

证法1：(Rⁿ)⁻¹ = (R ∘ R ∘ ⋯ ∘ R)⁻¹ = R⁻¹ ∘ R⁻¹ ∘ ⋯ ∘ R⁻¹ = R ∘ R ∘ ⋯R = Rⁿ，故 R 对称。

证法2：∀(x, y) ∈ Rⁿ，则 ∃y₁, y₂, ⋯, y_n − 1 ∈ X，使得
(x, y₁) ∈ R, (y₁, y₂) ∈ R, ⋯, (y_n − 1, y) ∈ R。
因为 R 对称，所以
(y, y_n − 1) ∈ R, (y_n − 1, y_n − 2) ∈ R, ⋯, (y₂, y₁) ∈ R, (y₁, x) ∈ R，因此 (y, x) ∈ Rⁿ，故 R 对称。

证法3：用数学归纳法对n进行归纳。

• 当 n = 1 时，Rⁿ = R 显然是对称的。
  
• 假设当 n = k 时，R^k 对称。
  当 n = k + 1 时，R^k + 1 = R^k ∘ R = R ∘ R^k。
  ∀(x, y) ∈ R^k + 1，则 ∃z ∈ X，使得 (x, z) ∈ R^k, (z, y) ∈ R。
  因为 R^k，R 均是对称的，所以 (y, z) ∈ R, (z, x) ∈ R^k，于是
  (y, x) ∈ R ∘ R^k = R^k + 1。

因此 R^k + 1 对称。
综上，Rⁿ 对 n ∈ N 都是对称关系。

设 R 是 X 上的二元关系，试证

• (R⁺)⁺ = R⁺,
• (R^*)^* = R^*
• R ∘ R^* = R^* ∘ R = R⁺
• (R⁺)^* = (R^*)⁺ = R^*

[证]

1. 因为 R⁺ ⊆ (R⁺) 显然成立。

其次，设 (a, b) ∈ (R⁺)，因为 (R⁺)⁺ 是一切包含 R⁺ 的传递关系的交，而 R⁺ ⊆ R⁺ 且 R⁺ 是传递的，故 (a, b) ∈ R⁺，即 (R⁺)⁺ ⊆ R⁺。

因此 (R⁺)⁺ = R⁺

2. 因为 R^* ⊆ (R^*) 显然成立。

其次，设 (a, b) ∈ (R^*)，因为 (R^*) 是一切包含 R^* 的自反传递关系的交，而 R^* 本身是自反的也是传递的且 R^* ⊆ (R^*)，故 (a, b) ∈ R^*，即 (R^*) ⊆ R^*，因此 (R^*) = R^*

3. R ∘ R^* = R ∘ (R⁰ ∪ R ∪ R² ∪ ⋯) = R ∪ R² ∪ R³ ∪ ⋯ = R⁺

R^* ∘ R = (R⁰ ∪ R ∪ R² ∪ ⋯) ∘ R = R ∪ R² ∪ R³ ∪ ⋯ = R⁺

4. 先证 (R⁺)^* = R^*

(R⁺)^* = (R⁺)⁰ ∪ (R⁺)⁺ = I_X ∪ R⁺ = R^*

再证 (R^*)⁺ = R^*

因为 (R^*)⁺ 是包含 R^* 的一切传递关系的交，又因为 R^* ⊆ (R^*) 且 R^* 是传递的，所以 (R^*)⁺ = R^*

因此 (R⁺)^* = (R^*)⁺ = R^*

设 R, S 为 X 上的二元关系，试证：

• (R ∪ S)⁺ ⊇ R⁺ ∪ S⁺
• (R ∪ S)^* ⊇ R^* ∪ S^*。

[证] (1) 因为 R ⊆ R ∪ S, S ⊆ R ∪ S，所以 R⁺ ⊆ (R ∪ S)⁺, S⁺ ⊆ (R ∪ S)⁺。因此 R⁺ ∪ S⁺ ⊆ (R ∪ S)⁺。

2. 因为 R ⊆ R ∪ S, S ⊆ R ∪ S，所以 R^* ⊆ (R ∪ S)^*, S^* ⊆ (R ∪ S)^*。因此 R^* ∪ S^* ⊆ (R ∪ S)^*。

设 R₁, R₂ 是 X 上的二元关系，证明：

• r(R₁ ∪ R₂) = r(R₁) ∪ r(R₂)
• s(R₁ ∪ R₂) = s(R₁) ∪ s(R₂)
• t(R₁ ∪ R₂) ⊇ t(R₁) ∪ t(R₂)

[证]

1. 因为 r(R₁) 和 r(R₂) 都是 A 上的自反关系，所以 r(R₁) ∪ r(R₂) 也是 A 上的自反关系。

由 R₁ ⊆ r(R₁), R₂ ⊆ r(R₂)，得 R₁ ∪ R₂ ⊆ r(R₁) ∪ r(R₂)，所以 r(R₁) ∪ r(R₂) 是包含 R₁ ∪ R₂ 的自反关系。由自反闭包的定义可知：r(R₁ ∪ R₂) ⊆ r(R₁) ∪ r(R₂)

又 R₁ ⊆ R₁ ∪ R₂, R₂ ⊆ R₁ ∪ R₂，故 r(R₁) ⊆ r(R₁ ∪ R₂)，r(R₂) ⊆ r(R₁ ∪ R₂)，因此 r(R₁) ∪ r(R₂) ⊆ r(R₁ ∪ R₂)。从而 r(R₁ ∪ R₂) = r(R₁) ∪ r(R₂)

2. 同 (1) 的证明。

3. 因为 R₁ ⊆ R₁ ∪ R₂, R₂ ⊆ R₁ ∪ R₂，故 t(R₁) ⊆ t(R₁ ∪ R₂), t(R₂) ⊆ t(R₁ ∪ R₂)，因此 t(R₁) ∪ t(R₂) ⊆ t(R₁ ∪ R₂)。

例如：设 X = {a, b, c}，A 上的两个关系 R₁ = {(a, b)}, R₂ = {(b, c)}。于是 t(R₁) = {(a, b)}, t(R₂) = {(b, c)}， 故 t(R₁) ∪ t(R₂) = {(a, b), (b, c)}，但 R₁ ∪ R₂ = {(a, b), (b, c)}, t(R₁ ∪ R₂) = {(a, b), (b, c), (a, c)}。 因此 t(R₁ ∪ R₂) ⊇ t(R₁) ∪ t(R₂)。

设 R 是 X 上的二元关系. 证明: R 的传递闭包 R⁺ 可定义为:

• 若 (a, b) ∈ R 则 (a,,b) ∈ R⁺
• 若 (a, b), (b, c) ∈ R⁺ 则 $ (a,c) R^+$
• 除上述序对外,无其他序对.

[证]

本质就是证明等价.

第一条表明 R ⊆ R⁺

第二条表明 R⁺ 是传递的

第三条表明 R⁺ 是最小的

完全等价于其定义

设 X 是一个集合，|X| = n，试求：

• X 上自反二元关系的个数为 2^n2 − n
  
• X 上反自反二元关系的个数为 2^n2 − n
• X 上对称二元关系的个数为 $2^{\frac{n^2 + n}{2}}$
• X 上自反或对称关系的个数为 $2^{n^2 - n} + 2^{\frac{n^2 + n}{2}} - 2^{\frac{n^2 - n}{2}}$
• X 上等价关系的个数为 ???

这里只讲解等价关系个数的求解. 其余关系的个数都可以用布尔矩阵方便地求解.

如无必要精力和能力,请跳过本题.

在阅读正文前，建议观看:

【乐正垂星】母函数是可以被理解的？！

指数生成函数 - OI Wiki

柯西乘积 - 维基百科，自由的百科全书

[解]

结合第一个视频的讲解,不难发现指数生成函数本质上就是预先除以了全排列数以避免重复,进而通过多项式计算模拟了选择的过程

现在考察 X 中的划分数,不妨计为 B_n ,立刻发现相当于对 n − 1 个元素增加一个元素 , 使用乘法法则即有.

注意到这种递推特性,写出递推式: $$ B_n=\sum_{i=0}^{n-1}C^i_{n-1}B_{i} $$ 初值: B₀ = B₁ = 1

注意到组合数,联想指数生成函数的形式

令: $$ \hat{B}(x)=\sum^{\infty}_{n=0}\frac{B_n}{n!}x^n \\ =1+\sum^{\infty}_{n=0}\frac{B_{n+1}}{(n+1)!}x^{n+1} \\ \frac{\text{d}\hat{B}}{\text{d}x}=\sum^{\infty}_{n=0}\frac{B_{n+1}}{n!}x^{n} $$ 由上面的递推公式: $$ \frac{B_{n+1}}{n!}=\sum_{i=0}^{n}\frac{B_{i}}{i!(n-i)!} $$ 从而有: $$ \begin{align}\frac{\text{d}\hat{B}}{\text{d}x}&=\sum^{\infty}_{n=0}\frac{B_{n+1}}{n!}x^{n}\\ &=\sum^{\infty}_{n=0}\sum_{i=0}^{n}\frac{B_{i}}{i!(n-i)!}x^n\\ &=\sum^{\infty}_{n=0}\sum_{i=0}^{n}\frac{B_{i}}{i!}x^i\cdot \frac{x^{n-i}}{(n-i)!}\\ &\Rightarrow \sum^{\infty}_{n=0}\sum_{i=0}^{n}\frac{B_{i}}{i!}x^i\cdot \frac{x^{n-i}}{(n-i)!}=\hat {B(x)}\cdot e^x \end{align} $$ 这是一个一阶微分方程: $$ \begin{align}\frac{\text{d}\hat{B}}{\hat{B}}&=e^x \cdot \text{d}x \\ &\Rightarrow \ln \hat{B}=e^x+\mathbb{C}\end{align} $$ 不妨带入初值,由前知: $$ \begin{align}\hat{B(0)}&=\sum^{\infty}_{n=0}\frac{B_n}{n!}x^n\\&=1+\sum^{\infty}_{n=0}\frac{B_{n+1}}{(n+1)!}x^{n+1}=1 \end{align} $$

求出常数 ℂ = −1

综上: $$ \hat{B(x)}=e^{e^x-1}=\exp(\exp(x)-1) $$ 这样就可以给出 B_n 的计算公式: $$ \begin{align}\hat{B}&=\frac{1}{e}\sum^{\infty}_{j=0} \frac{1}{j!}e^{jx}\\ &=\frac{1}{e}\sum^{\infty}_{j=0} \frac{1}{j!}\sum^{\infty}_{i=0}\frac{(jx)^i}{i!}\\ &=\sum^{\infty}_{n=0}\frac{B_n}{n!}x^n\\ &\Rightarrow B_n=\frac{1}{e}\sum^{\infty}_{j=0} \frac{j^n}{j!} \end{align} $$

设 C 为全体复数所构成的集合，R₀ 为全体非负实数之集。令
f : C → R₀,
具体地，∀z ∈ C，
f(z) = |z|₀.

C 上的等价关系 Ker(f) 的几何意义是什么？

[解]

以原点为圆心的同心圆环。

顺带一提,其商集是所有可能的半径集合 即ℝ

令 g : C \ {0} → C，∀z ∈ C \ {0}，
g(z) = z|z|⁻¹

C \ {0} 上的关系 Ker(g) 的几何意义是什么？等价类是什么？商集
(C \ {0})/Ker(g) 是什么？

[解]

角度/方向

以原点为端点但挖去原点的射线

单位圆

设 [a, b] 是一个有限区间。令 S 是区间 [a, b] 上的有限划分的集合，[a, b] 的一个划分 π 是形如 a = x₁ < x₂ < ⋯ < x_n = b, n ∈ N 的点的集合。在 S 上定义二元关系 R 如下：

∀π₁, π₂ ∈ S, π₁Rπ₂ ⇔ π₂的每个分点也是 π₁的分点。

证明：R 是 S 上的偏序关系（注意，这里的划分与等价关系中的划分不同）。

[证]

∀π ∈ S, π 的每个分点也是 π 的分点，故 πRπ，因此 R 是自反的；

∀π₁, π₂ ∈ S，若 π₁Rπ₂ 且 π₂Rπ₁，则 π₂ 的每个分点也是 π₁ 的分点且 π₁ 的每个分点也是 π₂ 的分点，故 π₁ = π₂。因此 R 是反对称的；

∀π₁, π₂, π₃ ∈ S，若 π₁Rπ₂ 且 π₂Rπ₃，则 π₂ 的每个分点是 π₁ 的分点，而且 π₃ 的每个分点也是 π₂ 的分点，因此 π₃ 的每个分点也是 π₁ 的分点，故 π₁Rπ₃。因此 R 是传递的。

综上可知：R 是 S 上的偏序关系。

设 (S, ≤₁), (T, ≤₂) 是偏序集。在 S × T 上定义二元关系 (S × T, ≤₃) 如下： ∀(s, t), (s^′, t^′) ∈ S × T,  (s, t)≤₃(s^′, t^′) ⇔ (s≤₁s^′, t≤₂t^′). 证明： （1）≤₃ 是 S × T 上的偏序关系； （2）若 (s, t)≤₃(s^′, t^′) ⇔ s≤₁s^′ 或 t≤₂t^′，则 ≤₃ 是 S × T 上的偏序关系吗？

[证]

1. ∀(s, t) ∈ S × T，则 s ∈ S, t ∈ T。由于 (S, ≤₁), (T, ≤₂) 是偏序集，故有 s≤₁s, t≤₂t ⇔ (s, t)≤₃(s, t) 从而 ≤₃ 是自反的；

2. ∀(s₁, t₁), (s₂, t₂) ∈ S × T，若 (s₁, t₁)≤₃(s₂, t₂) 且 (s₂, t₂)≤₃(s₁, t₁)，则

(s₁≤₁s₂ 且 s₂≤₁s₁) 且 (t₁≤₂t₂ 且 t₂≤₂t₁)。

由 (S, ≤₁), (T, ≤₂) 是偏序集可知，s₁ = s₂ 且 t₁ = t₂，故 (s₁, t₁) = (s₂, t₂)。

因此”≤₃“是反对称的。

3. ∀(s₁, t₁), (s₂, t₂), (s₃, t₃) ∈ S × T，若 (s₁, t₁)≤₃(s₂, t₂) 且 (s₂, t₂)≤₃(s₃, t₃)，有
   (s₁≤₁s₂, s₂≤₁s₃) 且 (t₁≤₂t₂, t₂≤₂t₃)。

由 (S, ≤₁), (T, ≤₂) 是偏序集可知 ≤₁ 与 ≤₂ 是传递的，所以 s₁≤₁s₃ 且 t₁≤₂t₃。故 (s₁, t₁)≤₃(s₃, t₃)，因此 ≤₃ 是传递的。

综上可知：≤₃ 是 S × T 上的一个偏序关系。

存在一个偏序关系 ≤，使得 (X,  ≤ ) 中有唯一的极大元素，但没有最大元素？若有请给出一个具体例子；若没有，请证明之。

[解]

存在。

设 X = {i, 1, 2, 3, ⋯}，其中 $i = \sqrt{-1}$。在 X 上定义的小于或等于关系”≤“，则 (X,  ≤ ) 就是一个没有最大元素，但却有唯一极大元 i 的偏序集。

设 R 是 X 上的偏序关系，证明：

R 是 X 上的全序关系 ⇔ X × X = R ∪ R⁻¹

[证]

⇒ ∀(x, y) ∈ X × X，由于 R 是 X 上的全序关系，故 (x, y) ∈ R 或 (y, x) ∈ R⁻¹ 必有一个成立。所以 (x, y) ∈ R ∪ R⁻¹，即 X × X ⊆ R ∪ R⁻¹；

反之，因为 R 是 X 上的关系，故 R ⊆ X × X，R⁻¹ ⊆ X × X，所以 R ∪ R⁻¹ ⊆ X × X 因此 X × X = R ∪ R⁻¹。

⇐ ∀(x, y) ∈ X × X = R ∪ R⁻¹，有 (x, y) ∈ R 或 (x, y) ∈ R⁻¹，即 xRy 与 yRx 必有一个成立，故 R 是 X 上的全序关系。