对角线元素与不同复杂度的系统的关系，本文主要内容关键词为：对角线论文,复杂度论文,元素论文,关系论文,系统论文，此文献不代表本站观点，内容供学术参考，文章仅供参考阅读下载。
对角线方法是指德国学者康托尔(G.Cantor)在证明实数集不可数时所运用的一种技术方法。在这种意义上，康托尔的实数集不可数论本身便是对角线方法的一种重要运用。此外，对角线方法还有两种重要运用，即哥德尔对角线定理和汤姆逊引理的证明。哥德尔对角线定理又叫“哥德尔自指定理”，是美国学者哥德尔(K.G
del)在证明他的不完全性定理时使用的关键定理。汤姆逊引理则是英国学者汤姆逊(J.F.Thomson)通过考察悖论运用对角线方法所获得的关于语形悖论与语义悖论具有统一的对角线结构的一项重要成果。
集合论的创始者康托尔提出，如果两个集合之间能够建立起一一对应，那么这两个集合就具有相同的基数；如果一个无穷集与自然数集具有相同基数，那么该集合就是可数集，否则就是不可数的。(克林，第7-8、2页)1873年，康托尔证明，实数集的基数大于自然数集的基数，即实数集是不可数的。(张建军、黄展骥，第146页)康托尔没有满足于此。1891年，他找到一种新的方法，即对角线方法，十分简洁地证明了实数集的不可数性。(同上)
直觉上，新实数b不是上述实数矩阵之内的实数，而是该矩阵之外的实数。这表明，该矩阵不能包括区间[0，1]的所有实数。然而，尽管新实数b不在上述实数矩阵内，但它却可以与该矩阵共同组成一个新的实数矩阵。这种技术行为可以反复进行，从而形成一个个新实数，组成一个个新的实数矩阵。康托尔之所以认为即使亡羊补牢地把新实数b加入上述实数矩阵，但仍然可以按照同样的方法而构造出另一个新实数，根本原因就在于此。
从语言层次上讲，新实数b之所以不同于上述实数矩阵内的任何实数，是因为它与该矩阵内的那些实数处于不同的语言层次；其根本原因则在于，新实数b的语境不同于该矩阵内的实数的语境，即该矩阵及其之内的实数仅仅是新实数b的一个语境因素。
矩阵根本不同于区间。康托尔所构造出来的新实数是区间[0，1]内的实数，但该实数却不处于康托尔最初构造的那个实数矩阵内。实数矩阵源于对实数做出的归纳假设。从根本上讲，这样便把实数矩阵归于一种类型(type)，以涵盖一定范围内的所有对象。也就是说，康托尔的实数矩阵实际上就是实数的一种类型或真类。类型本质上是以少数具象(token)为样品通过技术抽象而得到的含有未定量的抽象对象，具象则是不同于其他任何对象的具体对象。正因为如此，存在不属于某种给定类型的具象(贾国恒，2011年，第37页)，可称之为该类型的自由具象(free token)(同上，2012年a，第85页)。因此，如果把区间[0，1]的所有实数都视为具象，那么存在不属于某种给定实数矩阵的实数，可称之为该实数矩阵的自由实数。请注意自由实数的层次相对性：自由实数是相对于给定的实数矩阵而言的，不是相对于任何实数矩阵而言的。
简言之，矩阵不同于区间：实数矩阵内的任何实数都是相应区间内的实数，但该区间内的实数却不一定是该矩阵内的实数。具体地讲，运用对角线方法构造出来的那些实数都不在特定实数矩阵内，因为该实数不同于特定实数矩阵内的任何实数。换言之，实数矩阵内的实数集是可数的，而区间内的实数则是不可数的，即实数集是不可数的。
如果一个系统的所有有效公式都是该系统的定理，即该系统的所有有效公式在该系统中都是可证的，那么该形式系统就是完全的；否则就是不完全的。1929年，哥德尔证明了一阶逻辑系统的完全性，即哥德尔完全性定理。(Gdel，1967a，pp.582-591)1930年，哥德尔又证明，对于包括由一阶逻辑系统和五个皮亚诺公理而构成的算术系统PA，如果该系统是相容的，那么必定存在闭公式G及其否定
G在该系统中均不可证。(ibid，1967b，pp.595-616)也就是说，如果形式算术系统PA是相容的，则必定存在闭公式G及其否定G在系统PA中可表达，但却不能证明它们是系统PA的定理。这就是著名的哥德尔不完全性定理。
公式G表达的命题是自指命题，因为它说自己是不可证的，所以又被称为不可证命题。不同于说谎者命题的是，自指命题在哥德尔那里不导致悖论(贾国恒，2008年，第34-36页)，尽管自指命题不是在任何时候都不导致悖论(同上，2012年b，第7-8页)。在哥德尔不完全性定理的证明中。最难的是证明不可证命题G是不可证的。为此，哥德尔提出并证明如下定理：
这就是哥德尔对角线定理。按照哥德尔对角线定理，算术形式系统可以谈论它自身的语形。因此，哥德尔对角线定理又叫哥德尔自指定理。
最终，基于哥德尔自指定理，哥德尔证明了他的不完全性定理。按照哥德尔，即使把自指命题G作为新公理而加入形式算术系统PA，由此所形成的扩充形式系统PA＇也是不完全的。因为按照相似的程序，还可以在系统PA＇中找到另一个不可证命题G＇。
1962年初，哲学家和逻辑学家汤姆逊运用对角线方法证明：
如果S是任意集合，R是定义在S上的任意2-元关系，那么S中不存在这样的元素，它与并且只与S中所有那些同自身没有R关系的元素具有R关系。(Thomson，pp.104-106)
这就是对角线引理，又称汤姆逊引理。它可以用符号表示为：
(1)
汤姆逊引理与哥德尔完全性定理是相呼应的，因为哥德尔完全性定理是说一阶逻辑系统的所有有效公式在一阶逻辑系统内都是可证的，汤姆逊引理则是说一阶逻辑系统内不存在对角线元素。
康托尔对角线方法、汤姆逊引理与哥德尔对角线定理这三者既相互区别，又具有非常密切的相互联系。
康托尔对角线方法强调按照对角线方法可以构造出新的实数，但新的实数不在矩阵内，而在矩阵外，即实数区间内，或者直接说在实数内。汤姆逊引理则强调一阶逻辑系统内根本不存在具有对角线性质的元素，两者似乎不存在可比性。然而，汤姆逊引理的获得实质上是康托尔对角线方法的一种运用，因为它们相对于不同系统而言，正像康托尔利用对角线方法所构造出来的新实数不是实数矩阵内的实数那样，汤姆逊引理表明一阶逻辑系统内不存在对角线性质的元素(因此，定理应当严格地称作系统的内定理)。
同样，哥德尔的相关定理之所以被称为哥德尔对角线定理，是因为它也是对康托尔对角线方法的一种运用。(张建军，第100页)然而，与康托尔对角线方法和汤姆逊引理不同，虽然哥德尔对角线定理表明，足够复杂的形式系统，即复杂度不低于形式算术系统PA的系统，可以谈论其自身，例如，算术系统PA的自指命题G；但基于哥德尔对角线定理，哥德尔不完全性定理表明，足够复杂的相容的形式系统内存在自指命题G，而它的真假在该系统内却是不可证的。
总之，汤姆逊引理、康托尔对角线方法和哥德尔对角线定理是对角线方法的三次重要运用，它们按照对角线方法所排斥或者构造的东西可以统称为对角线元素。首先，按照汤姆逊引理，由一阶逻辑系统构造不出对角线元素，更谈不上一阶逻辑系统内存在对角线元素。其次，实数矩阵是一种系统。康托尔对角线方法蕴涵，对角线元素即新实数，虽然可以在实数矩阵内构造出来，但它不在构造它的那个实数矩阵系统之内，而在构造它的那个实数矩阵系统之外，即实数区间之内。再次，基于哥德尔对角线定理的哥德尔不完全性定理则更进一步表明，虽然足够复杂的相容的形式系统内存在对角线元素；但它的真假在该系统中却是不可证的。
换言之，第一，实数矩阵是比一阶逻辑系统更复杂的系统，因为由一阶逻辑系统构造不出对角线元素，更谈不上一阶逻辑系统内存在对角线元素；而由实数矩阵则可以构造出新的实数，尽管由它构造出来的新实数不在它自身之内而在之外。第二，实数矩阵的基数低于实数区间，因为实数矩阵是可数的，由它构造出来的新实数不在该矩阵内，而在实数区间内，即实数区间是不可数的。显然，从基数性上讲，实数区间比实数矩阵更复杂。第三，实数区间的复杂度低于形式算术系统PA的复杂度。尽管形式算术系统PA的五个皮亚诺公理都是关于自然数的公理，而实数区间是关于实数的系统，实数比自然数复杂，但由于实数区间仅仅是实数的一种排列系统，这意味着新实数只要构造出来就是真的，而哥德尔不完全性定理则表明系统PA内的自指命题G的真假在该系统内是不可证的，所以从所构造出来的对角线元素在相应的系统内部是否可证的意义上讲，形式算术系统PA比实数矩阵更复杂。
进一步，我认为，对于对角线元素与不同系统的关系而言，一个系统要么根本构造不出对角线元素；要么能够构造出对角线元素，不过所构造出的对角线元素虽然可以证明为真，这些元素却不在该系统之内；要么能够构造出对角线元素，并且不但所构造出的对角线元素可以证明为真，而且这些元素在该系统之内；要么能够构造出对角线元素，但这些元素的真假在该系统内却是不可证的——以上四种情况必居其一。第四种情况显然最为复杂，甚至可以包含矛盾，因为只要把“可证”理解为谓词，就会导致悖论。(贾国恒，2012年b，第7-8页)