判斷句子前先說明定義域
輸入尚未指定的式子 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。