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

Question

尝试做一些修改，但不确定这一点：

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

我有一种感觉，需要使用 Cantor Diagonalization 方法 - 但我不确定如何你会用它来解决这个问题。

Answer 1

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

|N| < |语言(N)|

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

languages(N) = {S_1 , S_2, S_3, ...}

我们定义一个集合D 就像：

D = {n in N / n not in S_n}

D 是有效的，并且 D 是 N 的子集，因此 D 属于语言（N）。
因此，必须存在一个 k，其中 D = S_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(又矛盾了）

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