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

Question

试图做一些修改，但不确定这一点:

Prove that the set of all languages over a finite alphabet is uncountable.

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

Answer 1

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

|N| < |语言(N)|

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

语言(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(再次矛盾)

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