关于逻辑学

若前提100%正确，结论是否保证 100%正确？ 论证过程是否严密，与“前提是否正确”无关

  1. “前提”来自各个领域，其正确性和“逻辑”本身无关
  2. 逻辑学家关心的是：“从某些（假定为真的）论据出发，究竟能不能得到最终的结论”

演绎有效性（非正式定义）：我们称一个推演步骤是有效的当且仅当不存在任何一种可能，令该推演的前提为真且结论为假。同样地，在这种情况下我们称这些前提蕴涵（entails）其结论。即在最弱最弱最弱……（省略无穷次）的情况下，推演的前提为真时，其结论也不可能为假。甚至可以说，前提为真且结论为假的情况是在根本上不自洽的。换句话说，一个有效的推演，其结论一定是前提的必要条件。

一个或多个命题是一致的（consistent），当且仅当在任意可能的情况下，它们都同时为真。

两个命题是等价的（equivalent），当且仅当它们在完全相同的可能情况下才同时为真。

逻辑的目的是系统性地检验论证的有效性：我们称一个推演步骤是逻辑有效的，当且仅当它的有效性仅由其前提与结论中的话题无关词汇决定。对于一个逻辑有效的演绎，我们称其前提逻辑上蕴涵（logically entails）其结论。

培根（Francis Bacon）：亚里士多德《工具论》中的那些纯演绎的方法（三段论）不足以发现科学真理,因此需要《新工具》（Novum Organum Scientiarum）

康德（Immanuel Kant）：分析命题（主项包含谓项）不提供新知识，后天综合命题讲述经验世界的知识，而哲学、数学知识应该是先天综合命题。

0. 集合

良序关系

良序：设 (A,≤) 为全序集，如果任意 A 的非空子集都有 ≤-极小元，则称 (A,≤) 为良序集。

自然数的定义

设 为任意的集合，我们称 为 的后继， 为 的前趋。

自然数的定义：。

无穷公理：所有自然数组成的整体是集合，记为 。

数学归纳法

传递集合：设 是一个集合，如果 的任意元素都是 的子集，则称 是传递集合。

三歧性：。

对任意自然数 定义： 当且仅当 ， 当且仅当 或 。（这一定义在本书的习题中已经被滥用，不仅限于自然数，在序数上都可以使用）

**习题 ：**证明设 为传递集合，则 也是传递集合。

**习题 ：**证明对任意自然数 ，都有 或 。

有穷集合和无穷集合

习题： 证明 与 等势。

**习题：**假设 为满足如下条件的集合：

  1. ；
  2. ；

证明：。

**习题：**设 为两个集合，证明：

  1. 当且仅当 与 的某个子集等势。

**习题：**设 为两个集合，试证明：

（1）如果 有穷，，则 也是有穷集合。

可数集合

**习题：**设 为两个可数集合，且 不相交，即 。证明： 也是可数的。

**习题（不考）：**证明：

  1. 对任意 有， 都是可数集合（约定 ）；
  2. 集合 是可数的。

不可数集合（不考）

序数

具有三歧性的传递集合叫做序数。每个自然数都是序数， 是序数。

本书中对序数的定义并不直观，也没有说明序数的用途。此处补充序数的描述：

在数理逻辑中，序数（ordinal numbers） 是一种用于表示集合的“大小”和“顺序类型”的概念，尤其在集合论、公理集合论和模型论中起着重要作用。序数扩展了自然数的概念，可以用来描述无穷集合的大小和结构，起到了将有限和无限统一到同一框架下的作用。

序数是良序集的等价类。直观地，序数可以理解为一种表示“位置”的标签，且这些标签本身是有序的。

**习题：**设 为序数集合，证明：

（1）如果 是 的最大元，则 ；

（2）如果 中无最大元，则对任何的 属于 ，有 。

超穷归纳法

如果 存在前趋，称 为后继序数。不是后继序数的非零序数称为极限序数。

**习题：**设 为序数，且 。

（1） 是极限序数，当且仅当 ；

（2）如果 ，且 是 的最大元，则 。

可数序数

定义 是可数序数。 是序数，且不可数。

定义 是序数且。

基数

设 是序数，如果对于任意的 都有 ，则称 是基数。

讲义中对基数的定义十分诡异，我们在这里补充教材中对基数的定义。集合 的基数 是与 大小相等的最小序数，基数的意义是用于比较集合的大小：

**习题：**设 为基数，κ 为集合 是序数且与等势是序数且与等势 的最小元。证明： 是基数。

**习题：**对任意的 都有，。

1. 命题逻辑

如果能谈论命题和命题的真假，我们应该也能谈论命题“并非”和“并且”的真假。

在逻辑学中，命题逻辑可以看作是一种 “零阶逻辑” (相比于一阶逻辑和高阶逻辑)，也就是不含任何变量绑定的逻辑。

1.1 命题逻辑的语言

合式公式（Well-Formed Formulas）：

  1. 每个命题符号都是合式公式（原子公式，atomic formula）

  2. 若 ，是合式公式，那么和也是合式公式。其中是和 中的一个

  3. 除此以外都不是合式公式。

**习题 ：**证明不存在长度为 2、3、6 的合式公式，但其他任意正整数长度的合式公式都可能存在。

**习题 ：**设 是一个合式公式， 是二元连接符（）出现的次数， 是命题符合出现的次数（例如，若 ，则 ）。使用归纳法证明：。

1.2 真值指派

对于命题符号集合 ，真值指派 是函数：

设 是由 通过 5 种公式构造运算得到的合式公式的集合，我们将 扩展到 ：

我们称真值指派 满足 ，当且仅当 。

重言蕴含： 当且仅当满足 中每个合式公式的真值指派也满足 。 也记为 。

重言式： 也记为 。

重言等价： 并且 ，记为 。

紧致性定理：设 是合式公式的无限集合，如果对于 中的任意有限子集 ，都存在一个真值指派满足 中的每个合式公式，那么，就存在一个真值指派满足 的所有合式公式（即，如果 的任意有限子集可满足，则 可满足）。

习题：(a) 证明：如果两个真值指派 , 与在合式公式 中出现的命题符号的指派是一致的，那么 。（使用归纳法则）。

习题：（置换）, ,… 一个合式公式的序列，对每个合式公式 ，令 是用 置换 （对所有 ）后得到的结果。

  1. 设 是所有命题符号的真值指派，定义 u 为满足 的真值指派，证明 使用归纳法。
  2. 证明如果 是重言式，那么 也是。（例如， 是一个重言式，因此对任意的合式公式 ，通过置换可得 是重言式）

1.3 解析算法

输入：命题逻辑wff

输出： 的解析树

**习题 （不考）：**证明引理 13B 中关于运算 的情形。

**习题 ：**假定将合式公式的定义修改为去掉其中所有的右括号。对于，我们写成： 。证明这种记法具有唯一可读性（即每个合式公式只有一个可能的分解方法）。提示：这种表达式具有的括号数和联结符号数相同。

1.4 归纳与递归

递归定义：

  • 自上而下：
    包含所有命题符号且关于五种公式构造运算封闭

  • 自下而上：


$S^=S_$

关于命题逻辑的归纳原理：

令 为一个关于命题逻辑的性质。假设：

  1. 对所有命题符号 ，性质 成立
  2. 对所有的命题公式 和 ，若 和 成立，则 和 也成立，其中 是 、、 和 中的任意一个

那么对于所有的命题公式 有性质 成立。

**习题 ：**设 是由集合 在二元运算 和一元运算 的作用下生成的。试列出 中的所有元素。 和 中各有多少元素

**习题 ：**本节中关于要求 仅是 上的关系类的讨论可以进行推广。 如前定义，但是如果对于每个 ，我们有 或者对某个 以及某些小于 的数 有 ，那么我们说 是一个构造序列。请给出 的正确定义，并证明 。

1.5 命题连接词

只用 五个联结词就可以实现任意 元布尔函数

**习题 ：**设 是三元布尔函数，定义如下：

（a）给出一个仅使用 的能够实现的合式公式；

（b）给出一个合式公式，其联结词最多出现 5 个。

**习题 ：**证明 是不完备的。提示：证明任意使用这些联结词和命题符号 的合式公式在 的 4 种可能的取值下有偶数个取值为 。说明：另一种方法是使用域 ，， 上的代数，任意使用这些联结词的可实现的布尔函数具有线性的特性。

1.7 紧致性和能行性（不考）

2. 一阶逻辑

在逻辑学中, 谓词逻辑是在命题逻辑的基础上加入量词得到的逻辑，量词包括全称和存在两个逻辑连接词。根据量词的强大程度，谓词逻辑可以进一步被分类为一阶逻辑、二阶逻辑乃至高阶逻辑等。

2.1 一阶语言

一阶语言是一类形式语言, 是一阶逻辑使用的语言。 大部分现代数学都基于一阶逻辑（一阶语言包含集合论语言，一切数学都可被嵌入在集合论中）。

表达式是符号的任意有限序列。大多数表达式没有意义，项和合式公式是具有特定意义的表达式。

项定义为在常数符号和变量之前加上函数符号构成的表达式，如 。

原子公式的做用相当于命题逻辑中的命题符号，原子公式是具有如下形式的表达式：

没有联结符号和量词符号的合式公式，项+谓词。

合式公式（或公式）是指由原子公式通过使用 0 次或多次连接符号和量词符号构成的表达式。

原子公式通过0次或多次联结符号和量词符号构成的表达式

自由变量是“没有量词约束”的变量。

2.2 真值与模型

一阶语言的结构 是一个函数，把一些语法上的符号映射到有实际意义的元素。

形式上，一阶语言的一个结构是一个函数，其定义域为参数的集合，且满足以下条件：

  1. 全称量词
  2. n 元谓词符号
  3. 常数符号
  4. 元函数符号

结构的基本思想就是给参数赋予意义。

若句子 在 中为真，则称 是 的一个模型，记为 。

对于结构 ，函数 满足合式公式 记为 。

一阶逻辑中全程量词的语义解释：对于合式公式 ， 当且仅当 ， 。其中 是一个函数，其取值在变量 处为 ，其他取值与 相同。这一定义相当于把全称量词 从 右侧转移到了左侧，常用于证明带全称量词的命题。

当且仅当或者 或者或者二者都成立。

逻辑蕴涵

合式公式集合 逻辑蕴含合式公式 记作 ，当且仅当对语言中的每个结构 和每个函数 ，使得 以 满足 的每个元素时， 也以 满足 。

在命题逻辑中表示重言蕴含，在一阶语言中表示逻辑蕴含。

这里的逻辑蕴涵使用的（元语言）符号 与第二章《命题逻辑》里一模一样。由于一阶逻辑包含 （subsumes）命题逻辑（只需允许0元谓词存在），因此逻辑蕴涵包含重言蕴涵，也更接近我们在第一章《非形式化逻辑》里的定义

下面这段话来自教材：

逻辑蕴涵的定义与第1章中的重言蕴涵非常相似，但是其复杂性却大大不同。在命题逻辑中想要判定一个合式公式是否是重言式，只需要考虑有限个真值指派，其中每一个都是有限函数。对每个真值指派，只要计算 ，这可以在有限长的时间内完成。（如前所述，重言式的集合是可以判定的）

如果要判定一阶语言中的合式公式是否恒真，则需要考虑每一个结构 。（特别地，这需要使用每个非空集合，而每个集合都有很多元素）对于每个结构，还要考虑每个从变量集合 到 的函数 。并且对每一个给定的结构 和 ，还需要判定 是否以 满足 。如果 是无限的，其本身就是一个非常复杂的概念。

**习题：**证明：

**习题：**证明：如果 在 中不是自由出现的，那么 。

**习题：**设语言具有相等和二元谓词符号 。对下面的条件中的每一个，找出一个句子 使得结构 是 的模型，当且仅当条件被满足。

​ (a) 中恰好有两个元素。

**习题： **全称公式 是形式为 的公式, 存在 公式 是形式为 的公式。其中 是无量词. 设 是 的子 结构，.

​ (a) 证明:

如果 $⊨ \mathfrak{A} ψ[s]且ψ是存在公式，那么⊨\mathfrak{B} ψ[s]$.

如果 且 是全称公式，那么 .

**习题： **设语言有等号和二元谓词符号 . 考虑两个结构 和 :

​ (a) 试找出一个句子，它在一个结构中是真的，在另外一个中是假的.

习题： 设 是结构且 是函数, . 证明存在结构 ，使得 是一个从 到 上的同态。提示: 取 = . 一般地，需要使用选择公理在 中定义函数， 除非 是一对一的.

​ 说明: 该结果产生“不含等号的升洛文海–斯科伦定理”(见习题 2.6). 即，不含等号时, 任意一个结构 A 都有任意更高基数的扩充结构 、使得 与 是初等等价的，除了相等。除非加入等号，否则这个结论是最强的.

2.3 解析算法

项是通过符号函数对变量和常数的运算得到的。定义符号函数 ，使得对符号 ，，其中 是项的个数。

**习题：**证明对于一个合式公式 的真的初始段 ，

**习题：**设 是包含变量、常数符号和函数符号的表达式。证明： 是项当且仅当 且对 的任意终段 ，我们有 。提示：证明更强一些的结果：如果对 的任意终段 ，，那么 是 个项的连接。

2.4 演绎计算

替换、可替换

**证明的定义：**从 到 的证明（推导）是一个有穷的 wff 序列 ，其中 就是 且对任意 有：

  1. 属于 （ 为公理集）, 或者
  2. 是由序列中位于它前面的两个 wff 经过 MP 规则推导而得；即存在 有 为

若以上证明存在，我们就说 是从 出发可证的（provable, deducible or derivable）, 或称 是 中的定理（theorem of ）, 记为 .

假言推理（Modus Ponen，又称 MP 规则或直言三段论）：

逻辑公理的集合 ：

  1. 重言式；
  2. ，其中 是 在 中的替换，即把 中出现的 换成 ；
  3. ；
  4. ，其中 在 中不是自由出现的（自由出现的意思是无量词限定，例如 中 是自由出现的， 不是）；
  5. ；
  6. ，其中 是原子的， 是有限次的将 中的 替换为 得到的。

由 和假言推理可以获得的公式集叫做 的定理集合。

概化定理：如果 且 x 不在 的任何公式中自由出现，则 。

**规则 **：如果 ，且 重言蕴含 ，那么 。

演绎定理：如果 ，那么 。从右到左叫做演绎，从左到右叫演绎定理。

习题： (a) 设 是结构，且令 ，在基本公式集上定义真值指派 如下：

iff

​ 证明，对于任意公式（基本与否均可），有： iff 。说明: 这个结论说明联结词 ¬与 → 在第二章与在第一章中的含义是一样的

​ (b)如果 重言蕴含 ，则 逻辑蕴涵 。

习题： 设 x 不在 中自由出现，证明 Q2b：；在同样的假设下，证明 Q3a：

习题：（再替换引理）(a) 试证： 一般不相等，而且以下两种情况均有可能发生： 在 中的某个位置上出现，而在 中同样的位置上不出现；或者反过来， 在 中的某个位置上出现，而在 中同样的位置上不出现。

​ (b)证明：如果 不在 中出现，那么在 和 中 可替换 。提示：对 使用归纳法。

**习题（不考）：**证明 Eq3：

2.5 可靠性与完备性理论

**可靠性定理：**如果 ，那么 。

**引理 25A：**逻辑公理都是恒真的。

完备性定理（哥德尔 1930）：

  1. 如果 ，那么 。
  2. 任意和谐的公式集都是可满足的。

紧致性定理：

  1. 如果 ，那么存在某个有限的 ，有 。
  2. 如果 的每个有限子集 都是可满足的，那么 是可满足的。特别地，句子集 有模型当且仅当其每个有限子集有模型。

可枚举定理：

对合理的语言，恒真（valid）合式公式的集合是能行可枚举的。

**定理 26A：**如果句子集合 有任意大的计数的有限模型，那么就有一个无限模型。

**定理 26C：**对有限语言中的有限结构 ， 是可判定的。

习题：（语义规则 EI）假设常数符号 不在 、 和 中出现，，证明：。（不使用可靠性定理和完备性定理）

**习题（不考）：**证明完备性定理 (a) 与 (b) 等价。提示： 当且仅当 是不可满足的，且 是可满足的当且仅当 ，其中 Δ 是某个不可满足的、可批驳的公式集，如 。

说明：类似地，可靠性定理也适用于每个可满足的公式集是和谐的。

**习题：**设 ，且 是不在 和 中出现的谓词符号。是否存在不出现 的从 到 的演绎？提示：这个问题有两种不同的方法。“软”方法使用两个不同的语言，一个含有 ，另一个不含 ；“硬”方法则考虑是否能够可以从 到 的演绎中消去 。

意味着 。对于不含 且 的语言的每个结构 ，使得 ，考虑含 的语言的对应结构 ，它通过定义 扩展了 。然后 （因为 中没有 wff 使用 P ），因此 ，意味着 （出于同样的原因）。因此，不含 的语言中的 和 。

**习题：**设 ， 是否和谐？是否可满足？

2.6 理论的模型

紧致性定理：

  1. 如果 ，那么存在某个有限的 ，有 ；
  2. 如果 的每个有限子集 都是可满足的，那么 是可满足的。特别地，句子集 有模型当且仅当其每个有限子集有模型。

**习题 （不考）：**证明下述句子是有限恒真的（即在每个有限结构中是真的）：

(a)

**习题：**设 , 是同一语言的两个理论，使得、 是完备的、 是可满足的。证明:

**习题 （不考）：**给出与如下公式等价的前束公式

(a)

**习题：**考虑带有二元谓词符号 的语言，设 是包含（通常序的）自然数的结构。证明：存在某个初等等价于 的 ，使得 具有降序链。（即在 中存在 ，使得对所有 有 。）说明：该习题的目的在于说明在这个语言中无法表达“不存在降序链。”

**习题：**设有一个不带函数符号的有限语言，

（b）证明：恒真的 句子集是可判定的。（ 公式是指具有形式 的公式，其中 是无量词的公式。）

说明：在一阶逻辑中，“判定问题”（Entscheidungs 问题）就是在给定一个公式后判定其是否恒真。由于丘奇定理（3.5 节），这一问题通常是无解的。这个习题给出的是判定问题中的一个可解的情形。

2.7 理论之间的解释（不考）

**习题：**假设 L0 和 L1 含有相同参量的语言，但 L0 中有一个 n 元函数符号 f 不在 L1中，同时 L1 中有一个 (n+1) 元谓词符号 P 不在 L0 中。证明对于 L0 的任意理论 T，存在一个忠实解释将 T 解释到 L1 上。

**习题：**设 L0 是含有等号及二元函数符号 + 和 ⋅ 的语言，L1 也一样，只不过用三元谓词符号表示加法和乘法。令 Mi=(N;+,⋅)(i=0,1) 分别是包含自然数和加法、乘法的语言 Li 的结构。证明在 M0 中由 L0 公式定义的任何关系都能在 M1 中由 L1 公式定义。

3. 不可判定性

3.0 数论

**定理 30A：**设 是 中取值为真的句子集，且 的哥德尔数集合 是一个在 中可定义的集合。则我们可以找到一个在 中为真的句子 ，但 不能由 推出。

Q: 定理30A的证明思路。

Q: 定理30A中三元关系R是怎么定义的？其中的符号a,b,c,\alpha分别代表什么？其中的推理是如何编码的？

3.3 数论的子理论

**习题 ：**证明：在结构 中，我们能够定义加法关系 。进一步证明在此结构中 ，序关系 ，后继关系 都是可定义的。(说明：如果把结构 简化为 ，这个结果还能加强。在此处，乘法关系可以通过指数运算的一个法则: 来定义）

叙述题

1.简叙Goedel定理的证明思路

哥德尔第二不完全性定理（1931）: 设 是一个足够强的递归可公理化理论，则 当且仅当 是不和谐的。

证明思路：

哥德尔第二不完备定理表明，如果一个足够强大的公理系统是相容的，那么它不能证明它自身的相容性。以下是该定理的证明思路，分为几个关键步骤：

可证明性公式：首先，我们定义一个公式 ，它表示“ 在系统 中是可证明的”。这个公式通过哥德尔编码来表示公式和证明的过程。

相容性公式：接下来，我们定义系统的相容性公式 ，它表示“系统 是相容的”，即不存在可证明的矛盾。具体来说， 可以表示为 ，即系统 不能证明 。

不动点引理：利用不动点引理，我们可以构造一个自指命题 ，使得 等价于 。这个命题 可以被理解为“我不可证明”。

假设系统证明相容性：假设系统 能够证明其相容性，即 。根据 的定义，我们有：

利用反射性质：通过反射性质，我们可以证明如果 ，那么 。然而，根据 的定义，这会导致矛盾，因为 不能同时证明 和 。

ö 定理的应用：ö 定理指出，如果 证明“”，那么 证明 。在这个情境下，如果 证明 ，那么根据 ö 定理， 会证明 ，即 本身。

结论：如果 是相容的，它不能证明 ，因为如果 能证明 ，那么根据上述推理， 会变得不相容。因此，哥德尔第二不完备定理成立：如果 是相容的，它不能证明自身的相容性。

总结：哥德尔第二不完备定理的证明思路是通过构造自指命题 ，利用可证明性和相容性的表达，结合反射性质和 ö 定理，最终得出系统无法证明自身相容性的结论。

一个基于哥德尔第一不完备定理的更简单的证明思路：

哥德尔第一不完备定理可以简化为对“若公理体系具有一致性，则构造的自指命题 为真”这一命题的否定；哥德尔第二不完备定理可以简化为对“从公理可推出公理体系具有一致性”这一命题的否定。

若“从公理可推出公理体系具有一致性”这一命题成立，则有从公理出发可推出自指命题 为真，这本身就是一个推导出（证明出） 的过程，与第一不完备定理相悖。因此“从公理可推出公理体系具有一致性”这一命题为假。

2.定理30A的证明思路。

  1. 利用哥德尔数构造自指句子 ；
  2. 使用反证法，通过假设推出矛盾以证明假设的反面；
  3. 得出结论。

3.定理30A中三元关系R是怎么定义的？其中的符号分别代表什么？其中的推理是如何编码的？

4.AE公理集有哪些？分别是什么？

5.可表示、可定义是怎么定义的？他们有什么区别？

**可定义关系：**设 是 上的 m 元关系，即 。我们已经知道，公式 （其中只有 是自由变元）在 中定义 当且仅当对于 中任意的 ，

.

（后两个条件等价是根据替换引理）我们可以把上述结果写成两个蕴涵式：

**可表示关系：**如果在上述两个蕴涵式中，“在 N 中为真”的概念可以被更强的概念“从 AE 中推出”取代，我们称 ρ 在理论 Cn AE 中可以表示 R。

在理论 中表示 当且仅当 在 中定义 。

一个关系在 中是可表示的，当且仅当存在一个公式，在 中表示该关系。

定理 33E 公式 在 中表示关系 R 当且仅当

  1. 由 数字确定
  2. 在 中定义 。

“定义”意味着创造了新的概念，而“表示”并不创造新的概念。 作为一个封闭的理论，无法在其中创造更多的概念，因此使用“表示”这一术语。结构 本身并不包含句子，因此用“定义”这一术语。

6.可表示函数、弱可表示的定义

可表示函数: 设 是自然数上的 m 元函数，公式 中只有 是自由变元。我们称 （在 中）函数表示 ，当且仅当对于 中的每一 元组 ，

弱可表示: 考虑递归可枚举集 ，其中对于递归 :

我们知道存在公式 在 中表示 。因此，公式 在 中定义了 。这个公式在 中不能表示 ，除非 是递归的。但我们说这个公式几乎可以表示 。

7.不动点定理的证明思路？

不动点引理：对于只含有自由变元 的公式 ，我们可以找到句子 使得

我们可以认为 间接地表达 “ 是真的我。” 当然，实际上 什么也没说，它只是一些符号串而已。甚至当我们在 中把它翻译成自然语言时，它也仅仅是关于一些数字和它们的后继及运算结果的句子。正是因为我们把数字和表达式联系起来，我们才能把 看作一个公式。

8.解释范式定理中符号e,a,k,T_m,k,k’的意思

范式定理（Kleene，1943）

（a）在 的值是 的 元部分函数是部分递归函数）

（b）对于每个 ， 是 m 元部分递归函数

（c）对于任意 元部分递归函数, 都存在某个 , 使得这个部分递归函数等于

在范式定理中，符号 , 和 的含义如下：

  1. : 这是递归函数的索引或编码，通常对应于一个程序或计算过程的标识符。它表示一个递归函数或其对应的程序。
  2. : 这是输入向量，通常表示为 ，是递归函数的输入参数。
  3. : 这是一个编码，表示从公式 推导出结果的推理过程的哥德尔数。它包含了推理过程和结果的信息。
  4. : 这是一个 元关系，包含 。它定义了计算步骤，表示 、输入 和编码 之间的关系，其中 编码了从公式 推导出结果的推理过程。
  5. : 这是在 之前的某个值，用于确保 是满足条件的最小值。在最小化操作 中， 代表比 k 更小的值，用于检查是否有更小的 满足条件。

范式定理的核心思想是，对于任意递归函数 ，存在一个索引 ，使得 可以表示为 ，其中 提取编码 中的结果部分。通过这些符号和关系，定理描述了递归函数的计算过程和其通用性。