语言的数量

以有涯随无涯，殆已！

定义

• 给定一个有限长字母表 $\Sigma$, 例如英文字母表

• $\Sigma$上的一个单词w定义为: $\Sigma$中元素构成的有限长序列

• 字母表$\Sigma$上的一个语言L的定义为: 由$\Sigma$上的单词构成的集合。

Q.有多少个可能的单词？

• 单词的长度可以为0,1,2,3,…,n,….
• 对于每个长度i,可能的单词数都是有限的(如对于英文字母表，长度为i的单词有$26^i$个)
• 单词的长度是可数的（n对应自然数）
• 可数个有限集合的并集仍然是可数的。
• 因此字母表上单词的数量是可数的。
• 如果单词的长度可以为任意长，那么单词的数量是可数无穷多，对应的势$|\Sigma^*|=\aleph_0$

Q:字母表$\Sigma$上能定义出多少种语言？

结论是 $|\mathbb{N}^*|=|\mathbb{R}|=\aleph_1$，也即,任意有限非空字母表上，语言的数量是不可数无穷多 (Continuum hypothesis)

一个构造性的证明：

• 假设语言的数量是可数的，记L1,L2,L3 …

• 单词的已经证明是可数的，记w1,w2,w3 …

• $$L_d:=\lbrace w_i|i \in \mathbb{N}, w_i \notin L_i \rbrace$$

• 用人话讲, 如果w1不在L1里,就把w1放进Ld,如果w2不在L2里，就把w2放进Ld，以此类推

• 显然，Ld与之前任何一个Li都不相同

• 出现矛盾，假设不成立

Q:说了这么多，你tm到底想表达什么？

在一个有限的字母表上，有可数无穷个单词，不可数无穷个语言。可数无穷可以理解为自然数的数量，不可数无穷可以理解为实数的数量。

这tm意味着什么？

自然语言文本是一个（很长的）词
同理英语课本是词
计算机程序是词
数学公式是词

我们对语言的描述，本质上就是词。我们不可能通过[用语言描述]的方式，一一列举出所有的语言！不可能存在能够识别全部语言的计算机程序！

又或者说，语言的数量，超越了语言所能描述的范围。

吾生也有涯，而知也无涯。以有涯随无涯，殆已！
吾所言可数，而语言不可数，以可数随不可数，没有满射已！