第9章哥德尔第一不完全性定理 第1节可表示性 引理96(欧几里得.假定a,b为互素的整数。则存在整数a和v使得u+vb=1 通常的证明是利用欧几里得的辗转相除法。我们后面会证明一个在PA中的版本。这 里我们就不证 定理94(中国剩余定理)令d,…,dn为两两互素的自然数、a0,…,an为满足a1<d1 (0≤i≤n)的自然数。则存在自然数c使得对所有的i≤m,a1是的余数。换句话说, c是下列同余方程组的解 证明:我们对n施行归纳。当n=0时是显然的。假定命题对n=k成立。我们考 察n=k+1的情形。根据归纳假定,存在自然数b使得对所有i≤k都有b≡da。 令d为自然数do,…,dk的最小公倍数。不难验证,d和dk+1是互素的。 我们先找到整数r,s使得b+rd=sdk+1+ak+1:由于d和dk+1互素,根据欧几里得 引理,存在整数u和υ使得ud+vdk+1=1。将等式两边都乘上ak+1-b,再通过简单移 项便可以知道,取r=(ak+1-b)u和s=(b-ak+1)v即可。 令z=b+rd=sdk+1+ak+1。一方面,对i<k,我们有 另一方面,2≡a+1sdk+1+ak+1≡ak+1ak+1最后,由于同余方程组的解具有周期D do,…,dk+1的最小公倍数。存在足够大的自然数m使得c=z+mD是非负整数。c就是 我们所要的 要想使用中国剩余定理来将有穷序列(ao,…,an)编码,我们需要足够大的两两互素 的自然数do,…,dn,下面的引理说明怎样找它们。 引理97.对任意的s≥0,下列s+1个自然数 是两两互素的。 证明:假定某个素数p满足p|1+(i+1)s!且pl1+(j+1)s!。则p(-i)s!。所以,或 者p(-i)或者pls!。无论哪种情形,都有pls!,进而p1,矛盾。第 9 章 哥德尔第一不完全性定理 第 1 节 可表示性 引理 9.6 (欧几里得). 假定 a, b 为互素的整数。则存在整数 u 和 v 使得 ua + vb = 1。 通常的证明是利用欧几里得的辗转相除法。我们后面会证明一个在 PA 中的版本。这 里我们就不证了。 定理 9.4 (中国剩余定理). 令 d0, · · · , dn 为两两互素的自然数、a0, · · · , an 为满足 ai < di （0 ≤ i ≤ n）的自然数。则存在自然数 c 使得对所有的 i ≤ n，ai 是 c di 的余数。换句话说， c 是下列同余方程组的解： x ≡d0 a0 x ≡d1 a1 . . . x ≡dn an。 证明: 我们对 n 施行归纳。当 n = 0 时是显然的。假定命题对 n = k 成立。我们考 察 n = k + 1 的情形。根据归纳假定，存在自然数 b 使得 对所有 i ≤ k 都有 b ≡di ai。 令 d 为自然数 d0, · · · , dk 的最小公倍数。不难验证，d 和 dk+1 是互素的。 我们先找到整数 r, s 使得 b + rd = sdk+1 + ak+1：由于 d 和 dk+1 互素，根据欧几里得 引理，存在整数 u 和 v 使得 ud + vdk+1 = 1。将等式两边都乘上 ak+1 − b，再通过简单移 项便可以知道，取 r = (ak+1 − b)u 和 s = (b − ak+1)v 即可。 令 z = b + rd = sdk+1 + ak+1。一方面，对 i ≤ k，我们有 z ≡di b + rd ≡di b ≡di≡di ai。 另一方面，z ≡dk+1 sdk+1 + ak+1 ≡dk+1 ak+1。最后，由于同余方程组的解具有周期 D - d0, · · · , dk+1 的最小公倍数。存在足够大的自然数 m 使得 c = z + mD 是非负整数。c 就是 我们所要的。 要想使用中国剩余定理来将有穷序列 (a0, · · · , an) 编码，我们需要足够大的两两互素 的自然数 d0, · · · , dn，下面的引理说明怎样找它们。 引理 9.7. 对任意的 s ≥ 0，下列 s + 1 个自然数 1 + 1 · s!, 1 + 2 · s!, · · · , 1 + (s + 1) · s! 是两两互素的。 证明: 假定某个素数 p 满足 p|1 + (i + 1)s! 且 p|1 + (j + 1)s!。则 p|(j − i)s!。所以，或 者 p|(j − i) 或者 p|s!。无论哪种情形，都有 p|s!，进而 p|1，矛盾。 9