判断句子前先说明定义域
输入尚未指定的表达式 R(x,y) 是谓词。当变量被赋值,或在已说明的集合上受到量化,它便成为命题。例如对每个非负实数 x,方程 y2=x 都有实数解;但对每个实数 x 并非如此。即使所写方程不变,改变定义域也会改变命题。
对 f:X→Y,满射表示 ∀y∈Y ∃x∈X:f(x)=y。输入见证可以依赖已选定的输出。单射则是 ∀x,x′∈X:[f(x)=f(x′)⇒x=x′]。一对有不同输出的输入不能否定单射;反例必须令前提为真而结论为假。
蕴含 P⇒Q 恰在 P 真而 Q 假时不成立,所以其否定是 P∧¬Q。逆否命题 ¬Q⇒¬P 与原命题真值相同;逆命题 Q⇒P 则是另一个命题。真值规则不允许我们只因 P 为假就推断 Q。
见证可依赖先前输入,不能依赖后来的输入
∀x∈X ∃y∈Y:R(x,y) 允许每次指定 x 后另选 y。∃y∈Y ∀x∈X:R(x,y) 则要求在考虑任意 x 前,已有一个共同的 y。后者推出前者,但前者未必推出后者。例如在实数上,容许误差可以依赖正在考虑的点,而不必有一个对所有点均有效的共同容许误差。
对 X×Y 上的每个谓词 R,若 ∃y∈Y ∀x∈X:R(x,y),则 ∀x∈X ∃y∈Y:R(x,y)。
设 y0 是共同见证,即对每个 x∈X 都有 R(x,y0)。给定任意 x∈X,元素 y0 就是满足 R(x,y0) 的输出。因此对每个 x 都有 ∃yR(x,y)。若 X 为空,结论无需论证即为真。
反方向的蕴含才会失败,下面一个具体例子说明原因。
反例模式
逐点见证不一定是同一个共同见证
命题:若 ∀x∃yR(x,y),则 ∃y∀xR(x,y)。取 X=Y=Z,令 R(x,y) 表示 x<y。第一个命题为真:对每个 x,输出 y=x+1 都可以。第二个命题为假:对任何提出的共同 y,例如 y=5,输入 x=5 给出 5<5,这不成立。一般而言 x=y 就使 y 失效。补救是保留上一个定理的单向蕴含,或加入真正提供一致见证的假设。
证明全称命题时,要取任意输入、记录它满足的假设,并在不赋予额外有利性质的情况下证明结论。证明存在命题时,要提供所需定义域中的对象,并验证它符合条件;只写出候选对象并不等于验证。若候选式涉及除法或平方根,也须检查它是否有定义。
概念视角算法
把量词看成证明者与反驳者的博弈
把带量词的句子看成博弈中的走法。在 ∀x∃yR(x,y) 中,反驳者先指定 x,证明者再回应一个 y;若证明者总能回应得使 R(x,y) 成立,句子便为真。在 ∃y∀xR(x,y) 中,证明者必须先确定 y,反驳者再逐一尝试每个 x。量词的次序就是走法的先后。否定会交换双方角色,所以量词的次序不变,种类却改变。
对任意无限集合,不应悄悄把“每个输入至少有一个可用输出”换成“存在一个同时选取所有见证的函数”。有效的明确公式可提供这样的选取;一般的选择原理则是另一个课题。对有限集合,可逐一作选择。
按原有次序否定量词的范围
否定全称命题会得到一个存在的反例;否定存在命题则要求每个候选对象都失败。对二元谓词,
¬(∀x∈X ∃y∈Y:R(x,y)) ⟺ ∃x∈X ∀y∈Y:¬R(x,y).
作为反例的输入会使为它提出的每个输出都失败。另一方面,否定 ∃y ∀x:R(x,y) 得到 ∀y ∃x:¬R(x,y);此时反例输入可依赖提出的共同输出。变量次序保留,不是倒转。
对 X×Y 上的每个谓词 R,
¬(∀x∃yR(x,y))⟺∃x∀y¬R(x,y),¬(∃y∀xR(x,y))⟺∀y∃x¬R(x,y).
以 S(x) 表示命题 ∃yR(x,y)。则 ¬∀xS(x) 等价于 ∃x¬S(x),而 ¬S(x),即 ¬∃yR(x,y),等价于 ∀y¬R(x,y)。这给出第一个等价。对第二个,以 U(y) 表示 ∀xR(x,y):则 ¬∃yU(y) 就是 ∀y¬U(y),而 ¬U(y) 就是 ∃x¬R(x,y)。每一步量词的次序都保持不变,只有种类改变。
很容易把 ∀x∃yR(x,y) 的否定写成 ∀x∀y¬R(x,y)。设 R(x,y) 表示 R 上的 y2=x,原命题为假(取 x=−1),但所提出的“否定”也为假(取 x=4、y=2,因为 22=4)。一个命题和它的否定不可能同时为假,所以这个否定是错的。正确的否定是 ∃x∀y:y2=x,以 x=−1 为见证。
同样方法可处理最终成立的叙述。若 an→L 表示对每个 ε>0,存在某个 N 控制所有 n≥N,其否定是
∃ε0>0 ∀N∈N ∃n≥N: ∣an−L∣≥ε0.
一个固定的容许误差在任意靠后的地方仍会失效。一个早期的坏项不足够,而一列越来越小的误差也未必能推翻收敛。对固定的容许误差,非严格不等式才是严格不等式的精确否定。不过,另用容许误差的论证,严格不等式可表达相同的完整不收敛性质:至少为 ε0 的误差大于 ε0/2,而大于 ε0 的误差也至少为 ε0。这是利用存在量词中的容许误差得到的等价,不是逐点否定。
空定义域也使这些等价关系保持一致。空集上的全称命题没有反例,故为真;空集上的存在命题没有见证,故为假。特别是 X 为空时,即使 Y 也为空,∀x∈X∃y∈Y:R(x,y) 仍为真;而当 Y 为空时,∃y∈Y∀x∈X:R(x,y) 为假。讨论两种形式之间的蕴含时,不能暗中加入非空假设。
存在与唯一是两项责任
对集合 Y 上的谓词 R(y),命题 ∃!y∈Y:R(y) 表示以下两点同时成立:(存在性)∃y∈Y:R(y);(唯一性)对所有 y,y′∈Y,若 R(y) 且 R(y′),则 y=y′。
对固定输入,恰有一个解表示解存在,而且任何两个解都相等。有效的存在证明不会自动证明唯一;证明任意两个解相同,也可能仍然允许根本没有解。
命题 ∃!y∈Y:R(y) 为假,当且仅当没有 y∈Y 满足 R,或存在两个不同的 y,y′∈Y 都满足 R。
合取式的否定是析取式:存在性失败,或唯一性失败。存在性失败表示没有 y 满足 R。唯一性失败表示“所有解的配对都相等”并不成立,所以有一对解 y,y′ 满足 y=y′。因此 ∀x∃!yR(x,y) 可因某输入没有输出,或因某输入有多个输出而失败;只检查一种失败方式并不完整。
例如用 y=b/a 解 ay=b,是假设了 a=0。在此假设下,代入证明存在,非零消去证明唯一。若 a=0,则 b=0 时无解,而 b=0 时每个实数 y 都是解。公式本身遗漏了这两种情况。证明审查要找出第一个没有依据的步骤,比只说最后答案看似错误更有帮助。
方程 y2=4 有实数解 y=2,但不只这一个:y=−2 也是解,所以存在性成立而唯一性失败。反过来,y2=−4 的任何两个实数解都相等,因为根本没有解,所以唯一性空泛地成立而存在性失败。两项责任必须各自证明。
例题
固定 a∈R,令 Ra(x,y) 表示 y2−2xy+a=0,其中 x,y∈R。分别求使 ∀x∃y:Ra(x,y)、∃y∀x:Ra(x,y) 及 ∀x∃!y:Ra(x,y) 成立的参数值。
解答。 配方得 (y−x)2=x2−a。若 a≤0,右边对每个实数 x 非负,实数平方根存在定理提供 y=x±x2−a;代入可验证这些候选解。若 a>0,取 x=0 便要求一个平方数为负。因此第一个命题恰在 a≤0 时成立。
若有共同的 y,在 x=0 时得到 y2+a=0,在 x=1 时得到 y2−2y+a=0。相减得 y=0,继而 a=0。反过来,a=0,y=0 对每个 x 均满足方程。第二个命题恰在 a=0 时成立。a<0 时第一个命题为真而第二个为假,说明区别是实质性的。
第三个命题从不成立。若 a>0,在零处没有解;若 a<0,零处有两个不同的根 ±−a。剩下 a=0,但在 x=1 时方程有不同的根零和二。此参数下存在共同见证,每个输入却不一定有唯一见证。共同见证和唯一见证是不同要求。
令 X=Y={1,2,3},以三乘三的零一网格表示 R⊆X×Y。要使 ∀x∃y:R(x,y) 为真而 ∃y∀x:R(x,y) 为假,最少需要多少个一?有多少个达到此最小数目的网格?
解答。 每一行都需要一个一,故至少需要三个。三个已足够:把它们放在对角线上。每一行都有见证,但没有一列对所有行有效。若恰有三个一,每行便恰有一个。这样的网格指定由三行到三列的函数,因此有 33=27 种。恰好在三行所选的列都相同时,才有一列适用于所有行;这样的常函数有三个。所以符合要求、达到这个最少数量的网格恰有 27−3=24 个。
第一个命题的否定是一整行全为零。第二个命题的否定则要求每列至少有一个零,而使各列失败的行可以不同;它不要求有一行全为零。对角线例子中,每列都有反例,但每行仍有一个一。这就是交换量词会改变反例所须做到的事。
有限见证网格
下表以由零和一组成的 3×3 网格记录固定非空三元素集合上的关系,一代表相关的有序对。全零关系不是空定义域。这类有限检验只是说明命题,并不验证遍及所有实数的定理。
下表给出四个主要命题在五个完全指定状态下的真值。“只有第一列”指三个一均在第一列;“只有第一行”指三个一均在第一行。
接受结论前先审查论证
有用的证明审查要检查定义域、见证可依赖的变量、构造式是否存在,以及每个蕴含的方向。也要分清必要条件和充分条件:找出所有解都满足的条件,并不能证明满足该条件的每个对象都是解。把候选对象代回;若声称得到完整分类,还要证明逆方向。前面章节的轨迹与商式例子提供了具体应用。
练习
快速检查
(写出 ∀x∈R ∃y∈R:y2=x 的否定,并判断原命题与其否定哪一个为真。)
由外而内否定量词,再找一个没有平方根的实数 x。
解答 · 答案
否定是 ∃x∈R ∀y∈R:y2=x。它为真:取 x=−1,没有实数 y 满足 y2=−1。所以原命题为假。
快速检查
(在 R 上,判断 ∀x∃y:x+y=0 与 ∃y∀x:x+y=0 的真假。)
比较可依赖 x 的见证与不可依赖 x 的见证。
解答 · 答案
第一个为真:给定 x,取 y=−x。第二个为假:对任何提出的 y,输入 x=1−y 给出 x+y=1=0。
快速检查
(∀x∈R ∃!y∈R:y3=x 是否为真?与 y2=x 比较。)
解答 · 答案
为真。存在性:y=3x 可以。唯一性:若 y3=y′3 则 y=y′,因为立方在 R 上严格递增。对 y2=x 命题则失败:x=−1 没有解,x=4 有两个解 ±2。