Exercise 1
由完备性定理知：
$$ T^{\vdash} =\{ \varphi \in L_{0}^{S} \mid T \vdash \varphi \}=\{ \varphi \in L_{0}^{S} \mid T \models \varphi \} = T^{\models} $$由课上推论知：
$$ T^{\models} \text{ is a theory} \iff T^{\models} \ne L_{0}^{S} $$故有：
$$ T^{\vdash} \text{ is a theory} \iff T^{\vdash} \ne L_{0}^{S} $$Exercise 2
(a) $\Phi^{\models}$ is R-axiomatizable
欲证 $\Phi^{\models}$ 是 R-axiomatizable, 即说明 $\Phi$ 是 R-deciable 的。
我们考虑读入任意一个算术句子 $\psi$
先将 $\psi$ 与 $\varphi$ 作对比，如果一致就输出，不一致再将 $\psi$ 与 $\Phi_{PA}$ 作对比，首先比较 $\psi$ 是否是 $\Phi_{PA}$ 的6条基本公理之一，如果一致就输出，不一致再验证 $\psi$ 是否是归纳公理生成（模式与归纳公理一致），如果是就输出，不一致就判断出了不在 $\Phi$ 里。故 $\Phi$ 是 R-deciable 的，即 $\Phi^{\models}$ 是 R-axiomatizable 的。
(b) $\Phi_{PA}^{\models} \subsetneq \Phi^{\models} \subsetneq \text{Th}(\mathfrak{N})$
先证 $\Phi_{PA}^{\models} \subsetneq \Phi^{\models}$：
由于 $\Phi_{PA} \subsetneq \Phi$， 所以有 $\Phi_{PA}^{\models} \subseteq \Phi^{\models}$
又有 $\varphi \not\in \Phi_{PA}^{\models}$，且 $\varphi \in \Phi \subseteq \Phi^{\models}$
所以 $\Phi_{PA}^{\models} \subsetneq \Phi^{\models}$
再证 $\Phi^{\models} \subsetneq \text{Th}(\mathfrak{N})$：
由于 $\text{Th}(\mathfrak{N})$ 是 complete 的，且 $\Phi \subseteq \text{Th}(\mathfrak{N})$
所以 $\Phi^{\models} \subseteq \text{Th}(\mathfrak{N})$
由前一问知 $\Phi^{\models}$ 是 R-axiomatizable 的。又由讲义知 $\text{Th}(\mathfrak{N})$ 不是 R-axiomatizable 的。
所以 $\Phi^\models \ne \text{Th}(\mathfrak{N})$。
故有 $\Phi^{\models} \subsetneq \text{Th}(\mathfrak{N})$。
Exercise 3
对 Ackermann function ，引入一个类似 configuration 的操作：
$$ C_{0}=(a_{0},b_{0},c_{0})\dots C_{s} =(a_{s},b_{s},c_{s}) $$展开成自然数序列：
$$ \underbrace{a_{0},a_{1},a_{2}}_{C_{0}},\underbrace{a_{3}, a_{4}, a_{5}}_{C_{1}},\dots,\underbrace{a_{3s},a_{3s+1},a_{3s+2}}_{C_{s}} $$使得：
- $a_{0}=0, a_{1}=0, a_{2}=1$
- $a_{3s}=a,a_{3s+1}=b,a_{3s+2}=c$
- 对所有 $i < s$ 我们有：
于是可以用 $\beta$ 函数写出以下式子：
$$ \begin{align} \exists t\exists p \exists s ( &\varphi_{\beta}(t,p,0,0) \land \varphi_{\beta}(t,p,1,0) \land \varphi_{\beta}(t,p,2,1) \\ &\land \varphi_{\beta}(t,p,3s,a) \land \varphi_{\beta}(t,p,3s+1,b) \land \varphi_{\beta}(t,p,3s+2,c) \\ &\land \forall i (i< s\to \forall a'\forall b'\forall c'(\varphi_{\beta}(t,p,3i,a')\land \varphi_{\beta}(t,p,3i+1,b')\land \varphi_{\beta}(t,p,3i+2,c') \\ &\to \text{Cons}(i, a',b',c')) \end{align} $$接下来完成 Cons：
- $$\text{Cons1}(i,a',b',c') \coloneqq a'\equiv 0 \to c'\equiv b'+1$$
- $$\text{Cons2}(i,a',b',c') \coloneqq \neg a'\equiv 0 \land b'\equiv 0 \to \exists i'(i'
- $$\text{Cons3}(i,a',b',c') \coloneqq \neg a'\equiv 0 \land \neg b' \equiv 0 \to \exists i_{1}\exists i_{2}(i_{2}
- $$\text{Cons3}(i,a',b',c') \coloneqq \neg a'\equiv 0 \land \neg b' \equiv 0 \to \exists i_{1}\exists i_{2}(i_{2}
令 $\text{Cons(i,a',b',c')} \coloneqq \text{Cons1}(i,a',b',c') \land\text{Cons2}(i,a',b',c') \land \text{Cons3}(i,a',b',c')$，即完成了 $\varphi_{\text{ack}}[a, b, c]$的表示。
由于 ackermann function 按照 a, b 双重递降，故一定能在有限步内解出答案。故有：
$$ c = \text{ACK}(a, b) \iff \mathfrak{N} \models \varphi_{\text{ack}}[a,b,c] $$