设 L1 和 L2 是两种语言，这样就不存在同时属于 L1 和 L2 的字符串 w。 我正在努力证明，如果 L1 和 L2 都是可识别的，则存在一种可判定的语言 A，使得 L1 ⊆ A 和 L2 ⊆ A'。 A' - A 的补码
我们可以假设L1和L2都不是可判定的，因为如果任何一个是，解决方案都是微不足道的(让A = L1或A' = L2如果L1或L2分别是可判定的)。特别是，L1和L2都无法识别图灵。
鉴于此，A必须等于集合L1，并添加更多元素(如果要成为超集，它必须至少具有A1中的元素)。因为L2是A'的子集，所以添加到L1以形成A的元素都不能在L2中。此外，我们必须添加无限多个项目，因为添加有限多个项目不能使A可判定，而L1则不是。
将不是L1或L2的东西分成两种语言R1和R2，这样这些语言没有任何共同点，每个字符串都恰好是L1、L2、R1和R2中的一种。此外，选择R1和R2，以便R1是可识别的，R2是图灵可识别的，并且两个集合都是无限的。让A = L1 U R1.现在，A' = L2 U R2.
-
A是共同图灵可识别的。如果w不在L1，我们最终可以认识到这一事实。如果w不在R1，我们可以决定这个事实。因此，我们最终可以认识到w两者都不在。 -
L2是c-图灵可识别的。如果w不在L2，我们最终可以认识到这一事实。如果它不在L2中，那么它要么在A中，要么在R2中。但是我们可以决定w是否R2，因为R2是可判定的。因此，如果我们认识到w不在L2并决定它不在R2，我们已经认识到w在A。因此，A是图灵可识别的。 -
我们在 1 中看到
A是可识别的，在 2 中看到A是图灵可识别的。因此，A是可判定的。因此，A'是可判定的。
请注意，当我们把不是L1或L2的东西"拆分"成两种无限的语言时，我们在那里挥了挥手，一种是共同图灵可识别的，另一种是共同图灵可识别的。似乎可以安全地假设，在任何无限语言中，必须存在该语言的适当子集，该子集是可识别的，但不可判定。您可能需要单独查找和/或证明以进行验证。证明想法：任何无限集合的元素都可以按字典顺序排列，在这种情况下，字母表上所有字符串的语言都有双射;因为所有字符串的集合上都有这种可识别但不可判定的语言，所以在这组字符串上也必须有可识别但不可判定的语言。值得注意的是，(L1 U L2)' 是可识别的，因为可能需要这样做才能使任何参数变得严格。