computation-theory - 证明有限字母表上所有语言的集合是不可数的

Question

试图做一些修改，但不确定这个：

证明有限字母表上所有语言的集合是不可数的。

我觉得它需要使用Cantor Diagonalization方法 - 但我不确定你将如何使用它来解决这个问题。

Answer 1

我在我的计算理论课上发现了这个证明，我希望它对你有用

|N| < |语言(N)|

假设 |N| >= |语言(N)|。因此，languages(N) 的每个元素都可以与 N 的一个元素相关联。因此可以将它们排序：

语言（N）= {S_1，S_2，S_3，...}

我们定义一个集合 D 像：

D = {n 中的 n / n 不在 S_n 中}

D 是有效的并且 D 是 N 的子集，因此 D 属于语言 (N)。因此，必须存在一个D = S_k的k

1）如果k属于D，那么根据D的定义，k不属于S_k。而 k 不属于 D 因为 D = S_k（我们发现矛盾）

2）如果k不属于D，那么：k属于S_k（根据D的定义）并且k属于D，因为D = S_k（再次矛盾）

像假定的那样的序列是不存在的。因此，为语言（N）的每个元素分配 N 元素的单射函数是不可能的。结论 |languages(N)| !<= |N|，所以 |语言(N)| > |N|