证明必须回应 statement 的确切要求。“对所有”要求论证适用于任意输入；“存在”要求我们证明有满足条件的对象；“如果”允许我们先假设 hypothesis 成立；“当且仅当”则要求证明两个方向。先读懂这层逻辑结构，才能知道哪些条件可以假设、哪些对象可以选择，以及还需要证明什么。

这些 proof methods 建立在 predicate 与 quantifier 的基础上。

Quantifier 的顺序与依赖关系

考虑下面两个关于实数的 statements，其中 $\mathbb R$ 表示实数集：

$$\forall x\in\mathbb R\;\exists y\in\mathbb R\;(x+y=0),$$ $$\exists y\in\mathbb R\;\forall x\in\mathbb R\;(x+y=0).$$

Equation 完全相同，但 quantifier 的顺序改变了 statement 的意思。

• 第一个说，每个实数 $x$ 都有一个 additive inverse $y$，也就是与 $x$ 相加得到零的数。我们可以为不同的 $x$ 选择不同的 $y$。
• 第二个说，存在一个固定的实数 $y$，它与每个实数 $x$ 相加都得到零。

第一个为真。给定任意 $x\in\mathbb R$，选择 $y=-x$。它是实数，而且

$$x+y=x+(-x)=0.$$

第二个为假。不论提出哪个实数 $y$，都可以选择 $x=1-y$。这样

$$x+y=(1-y)+y=1\ne0.$$

这反驳了每一个可能提出的 $y$，而不只是某一个特定选择。一般不能交换 universal quantifier 和 existential quantifier，并期待 statement 的意思不变。

Game semantics

Game semantics 用两位玩家从左到右读取 quantified statement 的方式，把这种依赖关系说清楚：

• 遇到 universal quantifier $\forall$ 时，由 Adam 选择变量的值。
• 遇到 existential quantifier $\exists$ 时，由 Eve 选择变量的值。
• 每次选择都必须属于相应 quantifier 的 domain。选择可以依赖此前已经发生的行动，但不能依赖尚未发生的行动。

对上面的两个 formulas，双方选完数值后，检查 equation 是否成立。若成立，Eve 获胜；否则 Adam 获胜。

Winning strategy 是一条规则，不管对手作出什么合法选择，都能保证自己获胜。赢一次还不够。在这个 quantifier game 中，statement 为真时，Eve 有 winning strategy；statement 为假时，Adam 有 winning strategy。

对 $\forall x\,\exists y\,(x+y=0)$，Adam 先行动，Eve 再选择 $y=-x$。对 $\exists y\,\forall x\,(x+y=0)$，Eve 必须先确定自己的选择，Adam 再选择 $x=1-y$。顺序决定了谁可以根据谁的选择作出回应。

写证明时，这个角度提醒我们：所给的选择规则或论证必须对任意 universally quantified inputs 都有效。只展示几个方便的取值成立，还不够。

哪些 quantifiers 可以交换顺序

两个相邻的 universal quantifiers 可以交换，两个相邻的 existential quantifiers 也可以交换。这里要求它们各自的 domain 固定，不依赖另一个变量。设 $A$、$B$ 是 sets，$P(x,y)$ 是一个 predicate，其中 $x\in A$、$y\in B$。那么

$$\bigl(\forall x\in A\;\forall y\in B\;P(x,y)\bigr) \equiv \bigl(\forall y\in B\;\forall x\in A\;P(x,y)\bigr),$$ $$\bigl(\exists x\in A\;\exists y\in B\;P(x,y)\bigr) \equiv \bigl(\exists y\in B\;\exists x\in A\;P(x,y)\bigr).$$

前两个 universal statements 都要求每一对元素满足 $P$；后两个 existential statements 都要求至少有一对元素满足 $P$。交换同类 quantifiers 不会改变这个要求。从 game 的角度看，两次都是同一位玩家选择：两个 universal quantifiers 由 Adam 选择，两个 existential quantifiers 由 Eve 选择。

例如，$\mathbb R^2$ 是所有实数 ordered pairs 组成的 set。下面三个 statements 都说，每一对实数都满足给定 equation：

$$\begin{aligned} &\forall x\in\mathbb R\;\forall y\in\mathbb R\;(x^2+y^2=1),\\ &\forall y\in\mathbb R\;\forall x\in\mathbb R\;(x^2+y^2=1),\\ &\forall(x,y)\in\mathbb R^2\;(x^2+y^2=1). \end{aligned}$$

三者等价，而且全都为假。Adam 可以选择 $x=10$、$y=4$，因为

$$10^2+4^2=116\ne1.$$

一个 counterexample 就足以推翻 universal claim。这与交换 $\forall$ 和 $\exists$ 不同：后者可能改变双方选择之间的依赖关系，从而改变 statement 的真值。

根据 statement 选择证明方法

Direct proof 从给定的 assumptions 出发，逐步证明 conclusion。具体步骤取决于 statement 的逻辑结构。

设 $U$ 是当前讨论对象的 universe，$P(x)$ 是 $U$ 上的 predicate，$p$ 和 $q$ 是 propositions。使 existential claim 成立的对象称为 witness。面对不同目标，可以这样着手：

对于 conjunction，两部分都必须经得起检验，因为 Adam 可以要求检查其中任意一部分。对于 disjunction，Eve 可以选择证明哪一部分；其中每一部分都叫 disjunct。Connective $\lor$ 是 inclusive OR，所以两部分都证明也可以，但并非必须。

这些是可用的 proof strategies，不是说每个目标只有这一种方法。例如，existence claim 也可以间接证明，不一定要明确构造 witness。

Conjecture 是一个尚未确定为真的 claim。证明之后，它就成为 theorem。研究 conjecture 时，先把 assumptions 和 conclusion 写准确；definitions 往往能直接告诉我们证明需要构造什么。

例：odd integer 的平方

用 $\mathbb Z$ 表示整数集。对于整数 $n$，even 和 odd 的定义是

$$\begin{aligned} n\text{ is even} &\quad\Longleftrightarrow\quad \exists k\in\mathbb Z\;(n=2k),\\ n\text{ is odd} &\quad\Longleftrightarrow\quad \exists k\in\mathbb Z\;(n=2k+1). \end{aligned}$$

每个整数都恰好属于 even 或 odd 其中一种。一个整数是 even 还是 odd，称为它的 parity。后面会用到这一点：对于整数，“不是 odd”就意味着“是 even”，“不是 even”就意味着“是 odd”。

我们要证明：

如果 $n$ 是 odd integer，那么 $n^2$ 也是 odd。

把 odd 的定义展开，可以看清 assumption 提供了什么 witness，以及 conclusion 要求什么 witness：

$$\forall n\in\mathbb Z\; \left[ \left(\exists k\in\mathbb Z\;(n=2k+1)\right) \Rightarrow \left(\exists\ell\in\mathbb Z\;(n^2=2\ell+1)\right) \right].$$

这两个 witnesses 的作用不同：assumption 给出表示 $n$ 的整数 $k$；conclusion 要求我们构造表示 $n^2$ 的整数 $\ell$。

Direct proof

任取 $n\in\mathbb Z$，并假设 $n$ 是 odd。那么存在整数 $k$，使 $n=2k+1$。目标是写成 $n^2=2\ell+1$，其中 $\ell\in\mathbb Z$。

将 $n$ 的表达式平方，再把结果写成一个 even 项加一：

$$\begin{aligned} n^2 &=(2k+1)^2\\ &=4k^2+4k+1\\ &=2(2k^2+2k)+1. \end{aligned}$$

选择 $\ell=2k^2+2k$。因为 $k$ 是整数，整数的乘积与和仍然是整数，所以 $\ell$ 也是整数。现在有 $n^2=2\ell+1$，这正是 odd 的定义。因此，对每个 odd integer $n$，结论都成立。

这里要分清哪些值可以选择。不能为了方便随意给 $k$ 赋值：一旦给定 $n$，$k$ 就必须满足 $n=2k+1$。我们可以利用这个 $k$ 构造 $\ell$。选择 witness 不是随便选一个数，而是要满足指定 equation 和 domain。

证明 disjunction

要证明 $p\lor q$，只需证明一个 disjunct。有时无法保证某一个 disjunct 总是成立，就可以根据 $p$ 的真值分情况：

• 如果 $p$ 为真，disjunction 已经成立。
• 如果 $p$ 为假，就证明 $q$。

对应的 logical equivalence 是

$$p\lor q\equiv(\neg p\Rightarrow q).$$

因此，可以通过假设 $\neg p$ 并推出 $q$ 来证明 $p\lor q$。这不是说只有在 $p$ 为假时才允许证明 $q$：无论何时，只要证明任意一个 disjunct 都足够；这个 equivalence 只是提供了一种有用的 conditional strategy。

例：由乘积上界限制其中一个因子

设 $a$、$b$、$c$ 是正实数。我们要证明，如果 $ab\le c$，那么

$$a\le\sqrt c\quad\text{or}\quad b\le\sqrt c.$$

Conclusion 只要求至少一个因子满足上界，并不要求两个都满足。如果第一个因子大于 $\sqrt c$，乘积的上界就会迫使第二个因子小于 $\sqrt c$。

任取正实数 $a$、$b$、$c$，并假设 $ab\le c$。如果 $a\le\sqrt c$，结论已经成立。否则，

$$\neg(a\le\sqrt c)\quad\Longleftrightarrow\quad a>\sqrt c.$$

由于 $b>0$，在这个 strict inequality 两边乘以 $b$ 不会改变不等号方向：

$$\sqrt c\,b<ab\le c.$$

又因为 $c>0$，所以 $\sqrt c>0$。因此，两边可以除以 $\sqrt c$，不等号方向仍保持不变：

$$b<\frac{c}{\sqrt c}=\sqrt c.$$

特别地，$b\le\sqrt c$，所以另一个 disjunct 成立。无论哪种情况，所需的 OR statement 都成立。

也可以用分式更快地说明。在正分子固定时，正分母越大，分式就越小。由 $ab\le c$ 和 $a>\sqrt c>0$，得到

$$b\le\frac ca<\frac c{\sqrt c}=\sqrt c.$$

第一个 inequality 来自将乘积上界两边除以 $a>0$；第二个使用了 $a$ 是较大分母这一点。

Proof by contrapositive

对于 implication $p\Rightarrow q$，要区分下面两个 statements：

Contrapositive 把 implication 的方向反过来，同时对两边的 propositions 取 negation。它与原 implication logically equivalent：

$$(p\Rightarrow q)\equiv(\neg q\Rightarrow\neg p).$$

两者都只在 $p$ 为真、$q$ 为假时为假。因此，proof by contrapositive 可以通过假设 $\neg q$ 并推出 $\neg p$，来证明原 implication。

Converse 只把方向反过来。它一般不与原 implication 等价，需要单独证明。例如，$p$ 为假、$q$ 为真时，$p\Rightarrow q$ 为真，但 $q\Rightarrow p$ 为假。

例：平方为 odd 的整数本身也是 odd

对于整数 $n$，现在要证明

$$n^2\text{ is odd}\quad\Longrightarrow\quad n\text{ is odd}.$$

这是前面 odd-square 结论的 converse，不能仅凭前面的证明就认定它成立。

如果尝试 direct proof，可以从某个整数 $k$ 满足 $n^2=2k+1$ 开始。取平方根得到

$$n=\pm\sqrt{2k+1}.$$

但这个表达式并没有直接给出使 $n=2\ell+1$ 的整数 $\ell$。改证 contrapositive 就能避开平方根，从更容易处理的条件出发：

$$n\text{ is not odd}\quad\Longrightarrow\quad n^2\text{ is not odd}.$$

由于 $n$ 和 $n^2$ 都是整数，这等价于

$$n\text{ is even}\quad\Longrightarrow\quad n^2\text{ is even}.$$

任取 $n\in\mathbb Z$，并假设它是 even。那么存在整数 $k$，使 $n=2k$，于是

$$n^2=(2k)^2=4k^2=2(2k^2).$$

选择 $\ell=2k^2$。它是整数，并且 $n^2=2\ell$，所以 $n^2$ 是 even。这就证明了 contrapositive，也证明了原 claim：一个整数的平方若是 odd，这个整数本身就是 odd。

整数这一假设不可缺少。正是它让我们能够把“不是 odd”换成“是 even”。

Combining both directions

我们已经证明了下面 biconditional 所需要的两个方向：

$$n\text{ is odd}\quad\Longleftrightarrow\quad n^2\text{ is odd} \qquad(n\in\mathbb Z).$$

正向通过展开 odd integer 的平方来证明；反向通过证明 even integer 的平方仍为 even 来完成。

对 biconditional 的两边同时取 negation，仍然得到等价 statement：

$$(p\Leftrightarrow q)\equiv(\neg p\Leftrightarrow\neg q).$$

结合整数的 parity 划分，可以得到下面的 corollary，也就是刚才结论的一个推论：

$$n\text{ is even}\quad\Longleftrightarrow\quad n^2\text{ is even} \qquad(n\in\mathbb Z).$$

所以，一个整数与它的平方有相同 parity。两个方向都有证明支撑，而不只是检查了几个例子。