期末题型

简答题9题 5 * 9

三道纯文字，剩下需要构造

6个大题 9 * 5 + 10 * 1

看哥德尔不完备定理证明的想法，P.200的思路

所有公式都是可编码的

叙述题

简述哥德尔定理的证明思路

ChatGPTChatGPT 如是说：↓\downarrow

哥德尔的证明是基于自指和递归函数的构造，具体思路如下：

第一不完备定理：

构造哥德尔编码 →\rightarrow 构造递归公式 →\rightarrow 不可证明性与自洽性

第二不完备定理：

如果一个系统是自洽的（即不包含矛盾），那么它不能证明自身的自洽性

第二定理的结果基于第一定理，通过系统自洽性 →\rightarrow 构造命题 GG →\rightarrow 证明不完备性

定理30A的证明思路

定理30A: 设 A⊆ThNA \subseteq \text{Th}\mathfrak{N} 是 N\mathfrak{N} 中取值为真的句子集，且 AA 的哥德尔数集合 {#α∣α∈A}\{\#\alpha \mid \alpha \in A\} 是一个在 N\mathfrak{N} 中可定义的集合。则我们可以找到一个在 N\mathfrak{N} 中为真的句子 σ\sigma，但 σ\sigma 不能由 AA 推出。

证明思路：构造一个句子 σ\sigma 来表示 σ\sigma 本身不是 AA 的定理。概括地说，接下来的讨论是这样的：如果 A⊢σA \vdash \sigma，那么 σ\sigma 是假的，这与 AA 是取值为真的句子集相矛盾。因此 σ\sigma 是取值为真的句子但 A⊬σA \not\vdash \sigma。

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

这样定义三元关系 RR:

⟨a,b,c⟩∈R\langle a,b,c\rangle \in R iff aa 是某个公式 α\alpha 的哥德尔数，cc 是从 a(Sb0)a(S^b0) 的 AA 出发的某个推理 G\mathfrak{G} 上的值

推理编码为：

将哥德尔数为 qq 的公式中的变元 v1v_1 换成数字 qq 后所得到的公式的推理

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

如下：

0 不是任何数的后继 $$\forall x, Sx \neq 0$$ (S1S1)。

后继运算的性质：两个数的后继相等，则它们相等 $$\forall x \forall y, (Sx = Sy \rightarrow x = y)$$ (S2S2)。

？ $$\forall x \forall y, (x < Sy \leftrightarrow x \leq y)$$ (L1L1)。

没有小于 0 的数 $$\forall x, (x \not< 0)$$ (L2L2)。

< 是一个全序 $$\forall x \forall y, (x < y \vee x = y \vee y < x)$$ (L3L3)。

任何数加上 0 等于自身 $$\forall x, x + 0 = x$$ (A1A1)。

加法运算的递归定义 $$\forall x \forall y, x + Sy = S(x + y)$$ (A2A2)。

任何数乘以 0 等于 0 $$\forall x, x \cdot 0 = 0$$ (M1M1)。

乘法运算的递归定义 $$\forall x \forall y, x \cdot Sy = x \cdot y + x$$ (M2M2)。

任何数的 0 次方等于 1 $$\forall x, x^{E0} = S0$$ (E1E1)。

幂乘运算的递归定义 $$\forall x \forall y, x^{E}Sy = x^{E}y \cdot x$$。(E2E2)

可表示、可定义是怎么定义的？有什么区别

可定义：设 RR 是 N\mathbb{N} 上的 mm 元关系，公式 ρ\rho （其中只有 a1,⋯,ama_1,⋯,a_m 是自由变元）在 N\mathbb{N} 中定义 RR 当且仅当对于 N\mathbb{N} 中任意的 a1,⋯,ama_1,⋯,a_m，

⟨a1,⋯ ,am⟩∈R  ⟺  ⊨Nρ[a1,⋯ ,am]  ⟺  ⊨Nρ(Sa10,⋯ ,Sam0).\langle a_1, \cdots, a_m \rangle \in R \iff \models_{\mathfrak{N}} \rho[a_1, \cdots, a_m] \iff \models_{\mathfrak{N}} \rho(\mathbf{S}^{a_1} \mathbf{0}, \cdots, \mathbf{S}^{a_m} \mathbf{0}).

可表示：将上述结果写成两个蕴含式：

⟨a1,⋯ ,am⟩∈R⇒⊨Nρ(Sa10,⋯ ,Sam0)⟨a1,⋯ ,am⟩∉R⇒⊨N¬ρ(Sa10,⋯ ,Sam0)\langle a_1, \cdots, a_m \rangle \in R \Rightarrow \models_{\mathfrak{N}} \rho(\mathbf{S}^{a_1} \mathbf{0}, \cdots, \mathbf{S}^{a_m} \mathbf{0}) \\ \langle a_1, \cdots, a_m \rangle \notin R \Rightarrow \models_{\mathfrak{N}} \neg \rho(\mathbf{S}^{a_1} \mathbf{0}, \cdots, \mathbf{S}^{a_m} \mathbf{0})

如果在这两个蕴含式中，“在 N\mathfrak{N} 中为真”的概念可以被更强的概念“从AEA_E中推出”取代，我们称ρ\rho在理论Cn AECn~A_E中可以表示RR

区别：

可表示强调的是某个对象是否可以在某个系统或模型中“存在”并“展示”。表示可以是具体的实例化过程。

可定义则强调的是通过某种规则或逻辑结构来描述一个对象的方式，即能否通过精确的定义或条件来唯一确定一个对象。

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

可表示性：

设f:Nm→Nf: \mathbb{N}^m \rightarrow \mathbb{N}是自然数上的 mm 元函数，公式中只有 $v_1, \cdots, v_{m+1} $是自由变元。我们称 $\varphi $（在 $\text{Cn } A_E $ 中）函数表示 $ f ，当且仅当对于，当且仅当对于 \mathbb{N}$ 中的每一 $ m$ 元组$a_1, \cdots, a_m $，

$ A_E \vdash \forall v_{m+1} [\varphi(\mathbf{S}^{a_1} \mathbf{0}, \cdots, \mathbf{S}^{a_m} \mathbf{0}, v_{m+1}) \leftrightarrow v_{m+1} = \mathbf{S}^{f(a_1, \cdots, a_m)} \mathbf{0}] $

弱可表示性（？）：

我们知道存在公式ρ\rho在 Cn AECn~A_E 中表示 RR 。因此，公式 ∃v2ρ\exists v_2ρ 在 N\mathfrak{N} 中定义了 QQ。这个公式在 CnAECn A_E 中不能表示 QQ，除非 QQ 是递归的。但我们说这个公式几乎可以表示 QQ

不动点定理的证明思路

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

AE⊢[σ↔β(S♯σ0)].A_E \vdash [\sigma \leftrightarrow \beta(\mathbf{S}^{\sharp \sigma} \mathbf{0})].

我们可以认为 σ\sigma 间接地表达“β\beta 是真的我”。当然，实际上 σ\sigma 什么也没说，它只是一些符号串~~（这诗人话？）~~。甚至当我们在 N\mathfrak{N} 中把它翻译成自然语言时，它也仅仅是关于一些数字和它们的后继及运算结果的句子。

解释范式定理中符号e,a,k,Tm,k,k′e,a,k,Tm,k,k'的意思

看不懂，ChatGPTChatGPT如是说：↓\downarrow

  1. ee：是 mm 元部分递归函数
  2. aa：数据
  3. kk：长度为 22 的数字序列，(k)0(k)_0是从 ϕ(Sa10,⋯ ,Sam0,S(k)10)\phi(\mathbf{S}^{a_1}0,\cdots,\mathbf{S}^{a_m}0,\mathbf{S}^{(k)_1}0) 的 AEA_E 推出的哥德尔数 G\mathfrak{G}。
  4. TmTm：代表一个项(Term)
  5. k, k′k,~k'：用来区分不同的元素或者公式。