有限语言集合的可数性证明有什么缺陷？

Question

令 FT 为 {0,1} 上所有有限语言的类。

假设FL是可数的，那么我们可以将FL的所有成员枚举为

FL = {L_0, L_1, L_2, ...}

同时，我们还将字母表上的所有字符串枚举为

\Sigma^*={w_0, w_1, w_2, ...}

现在考虑对角线语言

D={w_i: w_i不在L_i中, i=0,1,2,...}

应该是FL的成员。

然而，对于任意i，D不等于L_i，我们遇到了矛盾。

所以 FT 不可数。

Answer 1

你没有证据证明 D 是有限的。如果 D 是无限的，因此不是 FL 的成员，则不会出现矛盾。 w_i 在 L_i 中的概率很小（|L_i| 超过无穷大），w_i 在 D 中的概率很高。