证明有限字母上的所有语言集都是无可数的

Question

试图进行一些修订，但不确定这一点：

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

我有一种感觉需要使用 cantor对角 方法 - 但是我不确定如何将其用于此问题。

Answer 1

我在计算理论课程中发现了此证明，希望它对您有用

| n | <|语言（n）|

SUPOSE | n | > = |语言（n）|。因此，语言（n）的每个元素都可以与N的一个元素有关。因此它们可以按顺序排序：

语言（n）= {s_1，s_2，s_3，...}

我们定义了一个类似的d：

d = {n in n / n不在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）| ！<= | n |，因此|语言（n）| > | n |