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

Question

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

证明有限字母表中的所有语言集都是不可数的.

我有一种感觉它需要使用Cantor对角化方法 - 但我不确定如何使用它来解决这个问题.

Answer 1

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

| N | <| languages(N)|

设置| N | > = | languages(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 |