1．数论函数的通常定义，由n推到n+1 1
1.多加1，当作初等数论中最重要的方法；数论函数的定义亦可用此法而得。 1
2.和、积、方冪的定义 1
3.算术差n÷n 2
4.可变多个项的和与可变多个因子的积 3
5.m＞n，m=0，0＜m≤n的特征函数。算术上的符号函数及其相反：sg（n）与—sg（n） 4
6.由多种情形“凑合”的函数 5
7.“在某界限之下一切i均有……”以及“在某界限之下有一个i使得……”藉助於Σ与Π来表示 6
8.算术商：[a/n] 7
9.“在某界限之下最小的i使得……”藉助於Σ与Π来表示 9
10.除式a/n的剩余，——res（a，n）。可整除性的特征函数 9
11.因子个数，因子和。质数性的特征函数。n以下的质数的个数。 9
12.差的绝对值：|a—b|. 10
13.质数的种种特征 10
14.质数的种种特征 11
15.质数的种种特征 11
16.第n个质数：p0=2；pn是第n+1个质数 12
17.在n的质因子分解式中pa的方冪（指数）：expa（n） 13
18.n的质因子分解式的“长度”：long（n） 13
19.欧拉的〓函数 14
20.min（a，b）与max（a，b） 15
21.函数的最大公因子与最小公倍数。在一个定义式中有同样作用的两变元。 15
22.组合论中的例。排列的个数：n！。用遞归式计算在一值位的函数值。 16
23.（n/a）的定义。定义的一例，其中不参与遞归的变元并不仍旧不变 17
24.斐波那奇序列的定义。不由直接的前行者出发，而由一些以前的值位推到后面的值们。 18
25.由解析学所得出的数论函数。〓的遞归定义。对最近的不大的平方数的偏差：quadres（n）。平方性的特征函数：quad（n） 19
26.[e·n]依照遞归而定义。 20
27.由集论所得出的函数的一例：将数偶排成一列。两函数的联立定义。 22
2．递归函数与递归关系 24
1.遞归函数的概念及其功用。 24
2.原始遞归式，原始遞归函数。 26
3.与原始遞归模式稍有不同的定义。 27
4.遞归关系与原始遞归关系的概念。a＞b；a=b；“a可被b整除”；“a是一质数”；“a是一平方数”都是原始遞归关系。 28
5.原始遞归关系的结合。—B，即B的否定。 29
6.B1与B2：B1＆B2。 29
7.B1或B2：B1∨B2 30
8.由B1推得B2：B1→B2 30
9.“n以下一切i均有……”：（i）[i≤n→……]“n以下有一个i使得…”：（Ei）[i≤n…] 31
10.“凑合”定义 32
11.“n以下最小的或最大的i使得……”：μi[i≤n＆…]或μ′i[i≤n＆…] 33
12.常用的原始遞归函数与遞归关系表 35
3．串值递归式 35
1.斐波那奇序列的定义的推广：一般的串值遞归式 35
2.串值遞归式归约於原始遞归式与代入 41
4．联立递归式 41
1.把一个联立遞归式，由於把数偶排成一列而出现的，归约为串值遞归式 41
2.一般联立遞归式并没有超出原始遞归函数类以外 43
5．递归式，其中参数的值亦要求代入 44
1.构成所定义的函数时用到的“砖石”。 44
2.ψ（n，a），以这些砖石为值的，可藉串值遞归式来定义 45
3.嵌套的ψ值可表成非嵌套的表示式的补助定理 47
4.所定义的函数的值可由ψ（n，a）的值而得到 48
5.结果的推广：这一种遞归式并没有超出原始遞归函数类以外 50
6．多重递归式 50
1.dv（m，n）的定义。按一变元的串值遞归式 50
2.按另一变元的串值遞归式 52
3.第二个串值遞归式定义的构成 53
4.因第二个串值遞归式为原始遞归致第一个以及dv（m，n）亦然。 54
5.一般说来，这种定义不超出原始遞归函数类以外 55
7．归约 55
1.把一般的代入归约为1的代入 55
2.这是因为在遞归模式中包括有代入之故。它之消除，却是以再引入一个参数为代价的 57
3.参数个数的减少 57
4.归约到一个遞归模式，其中出现最多只有二元的函数 59
5.在新模式中把代入消除；这时已经不增加变元个数 60
6.消去最后的参数 61
7.迄今尚未确定的补助函数ι，κ与λ的定义 62
8.遞归式的归约为一个一元函数在值位0復迭式 63
9.这归约的成功是以增加开始函数为代价的。我们可证明，三个开始函数已经够了，例如（A2）：n+1，a+n，quadres（n） 64
10.在（A2）上n2之作成 65
11.差的作成。 67
12.[n/2]的作成 67
13.[〓n]的作成 69
14.a+n之归约於|a-n| 69
15.结果：由三个开始函数出发，我们可藉代入与复迭式而作出一切原始遞归函数，多元的可仅用代入而由一元的与a+n而作成 70
16.一元原始遞归函数可藉两个开始函数，不用多元函数，仅藉三个简单的模式而作出 71
8．初等函数 72
1.复迭式是否可以消除？由四则所定义的“初等函数”类亦包含有初等数论内扎使用的函数的大部分 72
2.复迭式合增长加强，方幂的复迭式ψ（n，a）看来“优超”於一切初等函数 73
3.精确地探讨：对每一个n1与n2都有一个m，使得ψ（m，a）不小於：ψ（n1，a）+ψ（n2，a） 74
4.ψ（n1，a）·ψ（n2，a） 76
5.ψ（n1，a）ψ(n2，a） 76
6.ψ（n1，ψ（n2，a） 77
7.ψ（n，a）优超於开始的初等函数 78
8.当应用四则时这个性质是留传的 78
9.当构成和与积时亦然 79
10.方幂复迭式是原始遞归的且超出初等函数类以外 80
9．非原始递归的数论函数的一例 81
1.如果把方幂复迭式再行复迭，可以预期得到一个函数，优超於所有的原始遞归函数 81
2.可以期望有同样性质的二元函数ψ（m，n）的定义 82
3.ψ（m，n）的增长的探讨 82
4.ψ（m，n）的增长的探讨 83
5.ψ（m，n）的增长的探讨 83
6.一元原始遞归函数是由一些开始函数出发，藉助於一些模式而构成，这便使得关于这些函数的命题可与关于自然数的命题作同样的证 84
7.所有一元原始遞归函数都被ψ（m，n）所优超 84
8.ψ（m，n）不可能是原始遞归 85
9.所有任意多元的原始遞归函数都被ψ（m，n）所优超 86
10．嵌套递归式 87
1.嵌套多重（依照多元而变的遞归式超出原始遞归函数类以外；非嵌套的则否 87
2.嵌套单重遞归式亦不超出原始遞归函数类以外 88
3.如果把这里所描写的过程用于多重遞归式，则得一个只含一层嵌套的正规开 90
4.开始值的正规化 90
5.开始值的正规化 91
6.就某函数而言的遞归函数的概念，多重，准确些的κ重遞归函数与其构成 92
11．对角过程与多重递归式 93
1.基于势而言亦必有非原始遞归函数；甚至于[τ·n]形的函数中亦有，其中τ为非负实数 93
2.对无理娄τ而言[τ·n]为遞归，当而只当τ的“階乘展式”的系数an为原始遞归，在第一界限之后均有an＜n-1，这性质在证明中是有判定性的 94
3.应用康托对角过程於一元原始遞归函数序列上 96
4.把这些函数用函数〓（m，n）来有效地计数 97
5.把这些函数用函数〓（m，n）来有效地计数 98
6.函数〓（m，n）的定义是一个嵌套二重遞归式：因此再得到，后者是超出原始遞归函数类之外的 99
7.同样可定义一个r+2元函数，当它的第变元适当地选择时，可等于任意一个r+1元原始遞归函数 99
8.对角过程应用于κ重遞归式指出了，κ+1重遞归式是超出κ重遞归函数类以外的 99
12．超穷递归式 100
1.在多元函数的定义中，如果我们限于单重递归式，那将是一个很随意的限制 100
2.κ元函数的值位的自然序列是一个ωk型的序列 101
3.ω2型的数的序列 102
4.这序列的“特征函数”的特征特性 102
5.超穷递归，ω2型递归的一例 103
6.一函数值由在更大的值位所取的函数值来计算的一例，用超穷递归式所定义的函数其值可在有穷次步骤内计算出 105
7.ω2型的递归式可归约为一个通常的二重递归式，其中需用到，一函数可由其原始递归模式而唯一地确定 107
8.ω2型的递归式可归约为一个通常的二重递归式，其中需用到，一函数可由其原始递归模式而唯一地确定 109
9.反之，二重递归式可归约为一个ω2型的单重递归式 110
10.自然数之依照ω3型的序列；以上过程之继续：ωk型与ωω型的序列 112
11.通常κ重递归式与ωk型的超穷递归式可以彼此互相归约，多重超穷递归式可以归约为单重超穷递归式 113
12.超穷递归式的特点：一元函数的定义亦可以是嵌套的；而其嵌套一般是不能解出的 113
13.对三元多重递归式所用的对角过程指出了：ωω型的递归式超出多重递归函数类以外 114
13．高阶递归式 116
1.复迭式当作函元函数，把由从乘积出发的复迭式所得出的二重递归式分解为有函元出现的单重递归式 116
2.最简单的函元函数：Vx（n，f（x））=f（n） 118
3.高阶递归式与高阶递归函数 119
4.所有一阶的二重递归式可分解为两个二阶的单重递归式 119
5.证明的精确作出 120
6.一个一阶的多重递归函数都属于二阶的单重递归函数 121
7.把二阶的函数表示为一阶的多重递归函数之一例 122
14．多重递归式的正规形 124
1.函元函数的应用可使最复杂的嵌套递归式有一致的写法；因此现在可以处理§10所提出的多重递归式的正规形，由递归式的“成分”所构成的“代入项” 124
2.以定义中的砖石为值的函数ψ的三个条件 126
3.ψ的定义，其中有暂未确定的κ（n），这个ψ满足前两个条件 127
4.解出嵌套式的补助定理 128
5.递归性假设；如果它成立，则ψ亦满足第三条件，而且更多 130
6.递归性推到底：κ（n）的定义 130
7.所有多重递归式可变成一正规形，其中只有一层嵌套 132
15．高阶递归式的“算术化” 132
1.用高阶递归式所定义的函数ψ的值的计算 132
2.计算的顺序，亦可应用于更复杂的情形 134
3.在计算中所用的形式步骤的注意 135
4.在计算中所用的形式步骤的注意 136
5.在计算中所用的形式步骤的注意 136
6.在计算中所用的形式步骤的注意 137
7.在计算中所用的形式步骤的注意 137
8.在计算中所用的形式步骤的注意 137
9.计算永远在有穷多次步骤内结束 137
10.构成一字典，其中一切所用的记号与号序列都对应于数 138
11.计算的形式步骤译为（应用字典）自然数的语言，其中定义了，在款11，Sbn（a b）；在款12，a*b；在款17，Substn（n，v m） 139
12.计算的形式步骤译为（应用字典）自然数的语言，其中定义了，在款11，Sbn（a b）；在款12，a*b；在款17，Substn（n，v m） 140
13.计算的形式步骤译为（应用字典）自然数的语言，其中定义了，在款11，Sbn（a b）；在款12，a*b；在款17，Substn（n，v m） 142
14.计算的形式步骤译为（应用字典）自然数的语言，其中定义了，在款11，Sbn（a b）；在款12，a*b；在款17，Substn（n，v m） 142
15.计算的形式步骤译为（应用字典）自然数的语言，其中定义了，在款11，Sbn（a b）；在款12，a*b；在款17，Substn（n，v m） 142
16.计算的形式步骤译为（应用字典）自然数的语言，其中定义了，在款11，Sbn（a b）；在款12，a*b；在款17，Substn（n，v m） 143
17.计算的形式步骤译为（应用字典）自然数的语言，其中定义了，在款11，Sbn（a b）；在款12，a*b；在款17，Substn（n，v m） 144
18.计算的形式步骤译为（应用字典）自然数的语言，其中定义了，在款11，Sbn（a b）；在款12，a*b；在款17，Substn（n，v m） 145
19.计算的形式步骤译为（应用字典）自然数的语言，其中定义了，在款11，Sbn（a b）；在款12，a*b；在款17，Substn（n，v m） 146
20.计算的形式步骤译为（应用字典）自然数的语言，其中定义了，在款11，Sbn（a b）；在款12，a*b；在款17，Substn（n，v m） 147
21.计算的形式步骤译为（应用字典）自然数的语言，其中定义了，在款11，Sbn（a b）；在款12，a*b；在款17，Substn（n，v m） 147
22.计算的形式步骤译为（应用字典）自然数的语言，其中定义了，在款11，Sbn（a b）；在款12，a*b；在款17，Substn（n，v m） 150
23.把一阶的定义中各步骤总结于一个数论函数r（n），从它，经过代入一个原始递归函数后我们便得到ψ 150
24.r（n）的定义只是“部分”的，它亦完全不似递归的，但是用r的定义等式却能够计算ψ在任意一值位的值 151
16．一般递归函数 152
1.藉助于最近的、较大的平方数而作的[〓]的定义 152
2.这定义不矛盾地给出函数值 153
3.加入补助函数的定义等式 154
4.由完全定义计算函数值；计算之步骤 157
5.一般递归式与一般递归函数的概念 157
17．一般递归函数的显式 158
1.如果对i没有上界但具有该性质的i的确存在时，μi是一般递归的 158
2.把一般递归函数表以顯式的计划，新字典 161
3.一数之哥德两数 163
4.把在计算中所允许的代入分解为基本步骤 163
5.基本的归约代入步骤的哥德两数 164
6.其它的归约步骤与其结果的哥德两数 165
7.归约结果的总结 166
8.推演的哥德函数的特征 166
9.值〓（a1，…，ar）的哥德两数 167
10.顯式 168
11.一般递归函数由开始原始递归函数与两个运算而构成，所得的顯式是全能的 169
12.顯式的种种形式 170
18．显式再行简约的可能性 177
1.一般递归函数〓可以变成一个更简约的顯式（不用ψ）的条件是〓（a1，…，ar）=m的原始递归性 177
2.非原始递归函数之一例，对它来说，这关系是原始递归的 178
3.这里出现一种递归式，其函数值不是由确定多个而是由可变多个以前的两数值而构成的 180
4.一般递归函数之一例，对它来说，这关系是非原始递归的 183
5.其它有关的结果 184
6.马尔科夫的证明，并不是所有一般递归函数都可以写成更简的顯式，“广延”函数 185
7.“全能”ψ函数的概念，全能性的必要条件 186
8.补助定理，用以证明这条件亦是充分的 188
9.马乐科夫命题的证明，即“广延”函数ψ，对每一种变元个数来说，都是“全能”的 189
19．非一般递归函数之一例 190
1.顯式可使对角过程能应用于一般递归函数 190
2.对角函数能够在某一个更一般的意义上是递归的或者根本是可计算的么？ 192
20．可计算函数 192
1.一计算，可重复且可信托于他人的，只能是机械的，用以演出计算的机器的想法 192
2.机器的记号与布局，它活动的基本动作；函数值〓（0），〓（1），〓（2），…出现于纸片上 194
3.计算〓（n）=1的机器 195
4.计算〓（n）=n+1机器 196
5.计算〓（n）=n+1机器 198
6.杜令机器可以计算第一个一般递归函数，但亦可计算有效给出的实数 200
7.如果杜令机器计算一个数论函数〓（n）的值，则它活动的基本动作以及它环境的情况可用原始递归函数来描述 201
8.如果杜令机器计算一个数论函数〓（n）的值，则它活动的基本动作以及它环境的情况可用原始递归函数来描述 202
9.如果杜令机器计算一个数论函数〓（n）的值，则它活动的基本动作以及它环境的情况可用原始递归函数来描述 203
10.如果杜令机器计算一个数论函数〓（n）的值，则它活动的基本动作以及它环境的情况可用原始递归函数来描述 205
11.从写0的情况起到第n个情况止，所写1的个数亦是n的原始递归函数 205
12.如果这机器在第ξ（n）情况下写第n+1个0，则ξ（n）是一般递归的；因此得出由机器所计算的函数的一般递归性 206
13.因此很可以提出，一般递归函数是在最一般的意义上可计算的数论函数 207
21．历史与应用 207
1.递归函数的历史是与数学基础探讨的历史有密切关联的 207
2.递归数论无须用到无穷集来构成 208
3.证明论的计划；递归数论在无数学上的可用性 208
4.希尔伯说对证明连续统假设的计划；用永远“更高”类的递归式来作出数论函数 209
5.哥德尔命题，用所讨论的系统的工具不能证明不矛盾性；算术化方法 209
6.在数化系统内不能塑述的一个方法：超穷递归式 211
7.最一般的可计算函数与一般递归函数之等同，应用 211
8.在概率论上 212
9.在直觉主义逻辑上 213
10.在递归函数部门上的一例表明了：为什么直觉主义的慎重是必要的 214
11.在集论上 217
12.在特征超穷序数上 218
13.在证明某些问题的不能有效判定上（例如，判定问题，半羣的“字的问题”） 219
22．以下问题是不能有效判定的：那一个等式系定义一个一般递归函数 221
1.定义一般递归函数的自然数（因而可代替定义等式系） 221
2.这些数是不能有效计数的 223
3.我们不能有效判定，那一个数定义一般递归函数 224
23．算术问题的可一般判定性的问题 225
1.算术式，哥尔德巴哈臆测的算术式 225
2.恒等式y=ax与某一序列的存在是同意义的，任意一个有穷项的序列可当作一数被一等差级数各项除后的剩余来处理 225
3.y=ax因此可变成算术式 227
4.所有原始递归关系是算术的 228
5.所有一般递归关系是算术的 229
6.相反方向的归约亦是可以的：量词的总括 230
7.不可能给出一个有效的一般过程来判定甚至只含一个自由变元的算术问题 230
24．递归性概念的推广．在解析学上的应用 231
1.对应于一误差限的高积数当作递归函数，有效的收敛，递归的收敛，递归的有理数序列，递归实数 231
2.给出一个单调的、有界的原始递归有理数序列，其中用到一个原始递归函数ρ（m，n），而且μx[ρ（m，x）=0]为非一般递归 233
3.这个序列不能有效收敛 234
4.并非所有递归实数都有一个递归小数展式，有递归阶乘展式的实数确定一个递归分划 235
5.如果一数确定递归分划，则它可展成一系列有递归系数的级数 237
6.在这些级数中亦包括了小数与阶乘展式 239
7.如果递归实数r是“递归无理”的，则它决定一递归分划 240
8.在这部门上的其它探讨 243
附录 递归证法的若干形式 244
参考文献 249
中德译名对照表 256
德中译名对照表 257
人名对照表 258