Exercise 1

先证$\forall x \, (0 + x \equiv x)$。
对 $x$ 归纳。令 $\varphi(x) := 0 + x \equiv x$。
有$0+0 \equiv 0$ 由公理 $\forall x \, x+0 \equiv x$ 得。
若 $0+x \equiv x$，则 $0+(x+1) \equiv (0+x)+1$ $\equiv x+1$。
故 $\forall x\,(0+x\equiv x)$。

再证$\forall x \, (x + 1 \equiv 1 + x)$。
对 $x$ 归纳。令 $\psi(x) := x+1 \equiv 1+x$。
有$0+1 \equiv 1$，$1+0 \equiv 1$，故 $0+1 \equiv 1+0$。
若 $x+1 \equiv 1+x$，则 $(x+1)+1 \equiv (1+x)+1$。
由公理 $1+(x+1) \equiv (1+x)+1$，得 $(x+1)+1 \equiv 1+(x+1)$。
故 $\forall x\,(x+1\equiv 1+x)$。

再证$\forall x \forall y \, ((y+1)+x \equiv (y+x)+1)$。

固定 $y$，对 $x$ 归纳。令 $\chi(x) := (y+1)+x \equiv (y+x)+1$。
$x=0$时，$(y+1)+0 \equiv y+1$，$(y+0)+1 \equiv y+1$。
若 $(y+1)+x \equiv (y+x)+1$，则
$(y+1)+(x+1) \equiv ((y+1)+x)+1$
$\equiv ((y+x)+1)+1$
$\equiv (y+(x+1))+1$
故 $(y+1)+(x+1) \equiv (y+(x+1))+1$，即 $\chi(x+1)$ 成立。
故 $\forall x\,((y+1)+x \equiv (y+x)+1)$

下证$\forall x \forall y \, (x + y \equiv y + x)$。

固定 $x$，对 $y$ 归纳。令 $\theta(y) := x+y \equiv y+x$。
有 $y=0$：$x+0 \equiv x$，$0+x \equiv x$，故 $x+0 \equiv 0+x$。
若 $x+y \equiv y+x$，则
$x+(y+1) \equiv (x+y)+1$
$\equiv (y+x)+1$
$\equiv (y+1)+x$
因此 $x+(y+1) \equiv (y+1)+x$。
故$\forall y\,(x+y \equiv y+x)$，由 $x$ 的任意性得结论。

故 $\Phi_{\text{PA}} \models \forall x \forall y \, x + y \equiv y + x$。

Exercise 2

(a)

如果 $\Gamma, \varphi\frac{y}{x} \models \psi$ 成立，且满足变量限制条件 $y \notin \text{free}(\Gamma \cup \{\exists x \varphi, \psi\})$，那么 $\Gamma, \exists x \varphi \models \psi$ 必成立

(b)

假设前提有效。任取结构 $\mathfrak{A}$ 和赋值 $s$ 使得 $\mathfrak{A} \models \Gamma[s]$ 且 $\mathfrak{A} \models \exists x\varphi[s]$。
则存在 $a \in |\mathfrak{A}|$ 满足 $\mathfrak{A} \models \varphi[s[x\mapsto a]]$。
定义新赋值 $s'$： $s'(y)=a$，且对所有 $z \neq y$，$s'(z)=s(z)$。
由 $y \notin \text{free}(\Gamma)$和coincidence lemma，$\mathfrak{A} \models \Gamma[s']$。
又 $y \notin \text{free}(\psi)$，故 $$\mathfrak{A} \models \psi[s'] \iff \mathfrak{A} \models \psi[s]$$
因为 $y$ 不在 $\varphi$ 的自由变量中，所以

而 $s'[x\mapsto a]$ 与 $s[x\mapsto a]$ 在 $\varphi$ 的自由变量上取值相同，故 $$\mathfrak{A} \models \varphi[s'[x\mapsto a]] \iff \mathfrak{A} \models \varphi[s[x\mapsto a]]$$
因此 $\mathfrak{A} \models \varphi\left[ \frac{y}{x} \right][s']$。
由 $\mathfrak{A} \models \Gamma[s']$ 和 $\mathfrak{A} \models \varphi\left[ \frac{y}{x} \right][s']$ 得 $\mathfrak{A} \models \psi[s']$。
再由coincidence lemma得 $\mathfrak{A} \models \psi[s]$。

Exercise 3

不是的
定义$\varphi = x \equiv 2$，论域为自然数，故$\exists{x}\varphi$为真，而$\forall x \varphi$为假。
所以这个式子不是可推导的。

Exercise 4

(a)

(b)

Exercise 5

由题，

$Φ \vdash (\varphi → ψ) \implies \varphi ∪ {ϕ} \vdash ψ$：

对$4$进行析取：
若 $\neg \varphi$，则有

若 $\psi$，则有

显然等价于

即证

$Φ ∪ {\varphi} \vdash ψ \implies \varphi \vdash (\varphi → ψ)$

即证