帕里斯－哈林顿定理

证明论中的一个著名定理。J．帕里斯(Jeff Paris)和L．哈林顿(Leo Harrington)在1977年发表《皮亚诺算术中的数学不完全性》一文，证明一个组合命题在皮亚诺算术(PA)中不是可证的，为了陈述这个定理，需要先说明几个概念。

［A］=｛B∶BA并且｜B｜=n｝，也就是说，［A］是A的所有n个元素的子集的集合。［A］的一个划分P是指把［A］分成有穷个互不相交的子集。P∶［A］→k表示［A］的一个划分P把［A］分成k个互不相交的子集。自然数的一个有穷集合H称为相对大的，如果它至少有像它的最小的元素那样多的元素，即card(H)≥min(H)。(例如，一个自然数的有穷集合的最小的元素是数99，则元素多于等于99个的，就是相对大的。)如果P∶［A］→k，A的一个子集B称为相对于划分P是齐性的，当且仅当P是［B］上的常函数。换个说法，划分P把［A］分成互不相交的C…，C，A的子集B对划分P是齐性的，当且仅当对某个i而言，1≤i≤k，［B］C。给定自然数k，m，n和集合A，用记法：表示，对于每一划分P∶［A］→n，存在A的一个相对大的子集B，B对于划分P是齐性的并且B至少有k个元素。

定理1．对所有自然数k，m和n，存在一个集合A，使得。

定理1是有穷拉姆齐定理的加强形式。如果删去箭头下面的星号*，即去掉有k个元素的齐性集合是相对大的这一要求，其结果就正是有穷的拉姆齐定理。有穷的拉姆齐定理是在PA中可证的。

定理2．(帕里斯－哈林顿) 定理1的组合原则在PA中不是可证的。

帕里斯和哈林顿找到的这个在PA中不可证的真命题，是一个自然的数学命题，它与哥德尔原来证明的不可判定命题不同，不需要把像可证性这样的逻辑概念编码。它是一个有更深刻的数学意义的命题。

令j→表示：如果A是一个有j个元素的集合，并且P∶［A］→n，那么就存在对P而言的A的一个齐性子集B，B的基数为k。这样，上面的定理1就可写成

(*)kmnj()。存在原始递归函数f(m，n，k)使得f。定义递归函数f：f(n)等于使下式成立的最小的j：。帕里斯和哈林顿证明了另外一个结果：

定理3．如果g是递归函数的一个描述，并且PA┝“g是全函数”，那么对一切充分大的n而言，f(n)＞g(n)。

因此，f(n)超出一切在PA中可证的递归函数g(n)，f(n)比每一个这样的g(n)增长得更快。显然，(*)决定一个递归函数f(k，m，n)，但是它增长得如此之快，以致在PA中没有一个可证的递归函数g具有下述性质：对所有的k，m和n而言，g(k，m，n)≥f(k，m，n)。

帕里斯和哈林顿的工作在证明论研究中开辟了一个新的方向，H．弗里德曼(H．Friedman)、R．索洛维(R．Solovay)等人在这方面的研究中又获得了一些重要的结果。帕里斯－哈林顿定理也可用模型论方法证明。后来大多数这方面的工作也都应用模型论方法。