{0,1}上有限语言类可数性证明的漏洞是什么？

• 核心错误：证明里错误认定构造出的对角线语言D属于有限语言类FT。
• 具体拆解：
  • 有限语言的本质是仅包含有限个字符串的集合，而D的构造规则是：对每个索引i，若w_i ∉ L_i就把w_i加入D。
  • 因为枚举的FL（即FT）里全是有限语言，每个L_i只能覆盖有限个w_j。这意味着存在无穷多个i，满足w_i不在L_i里。
  • 这么一来，D会包含无穷多个字符串，变成无穷语言，完全不属于FT。原证明的矛盾前提（D属于FT）根本不成立，所以推导的“FT不可数”结论无效。

额外补充：实际上{0,1}上的所有有限语言类是可数的——每个有限语言对应一个有限字符串集合，有限集合的可数并仍是可数的，也可以通过给每个有限语言编码为自然数的方式证明其可数性。

内容的提问来源于stack exchange，提问作者Cyberpunk2020