逐步主鏈
S01 · definition
操作前
d:X\times X\to\mathbb{R}操作後
d\ge 0;\ d(x,y)=0\Leftrightarrow x=y;\ d(x,y)=d(y,x);\ d(x,z)\le d(x,y)+d(y,z)
條件:無
規則:metric_def · 依賴:mko_metric_def
葉節點依據:metric_def + mko_metric_def
依 MKO,度量要滿足四項,且每一項都對所有點(或點對、三元組)成立:非負;分離(距離為零當且僅當兩點相同);對稱;三角不等式。分離包含兩個方向:對角線為零,以及非對角線不為零。
S02 · implies
操作前
d(i,j),\ i,j\in X
操作後
d(i,j)\in\{0,1,2\},\ d(i,j)\ge 0條件:無
規則:finite_exhaustion · 依賴:G1
葉節點依據:finite_exhaustion + order_basics
逐格查 16 個值:每個都是 0、1 或 2,因此都非負。同時記下兩個之後要用的界:所有值都 ≤2。
S03 · implies
操作前
d(i,i),\ i\in X
操作後
x=y\Rightarrow d(x,y)=0
條件:無
規則:finite_exhaustion · 依賴:G1
葉節點依據:finite_exhaustion
對角線 d(0,0)、d(1,1)、d(2,2)、d(3,3) 都是 0,所以相同的點距離為零。這是分離的一個方向。
S04 · implies
操作前
d(i,j),\ i\neq j
操作後
d(x,y)=0\Rightarrow x=y
條件:無
規則:contrapositive · 依賴:G1, S02
葉節點依據:finite_exhaustion + contrapositive
非對角線的 12 格都是 1 或 2,所以 x≠y 時 d(x,y)≥1,特別是 d(x,y)≠0。依逆否推理,這等價於「d(x,y)=0 推出 x=y」。
S05 · implies
操作前
x=y\Rightarrow d(x,y)=0,\ d(x,y)=0\Rightarrow x=y
操作後
d(x,y)=0\Leftrightarrow x=y
條件:無
規則:iff_intro · 依賴:S03, S04
葉節點依據:iff_intro
S03 與 S04 兩個方向合起來,就是分離性。MKO 第一段正是說:對角線須為零、非對角線不得為零,二者共同構成分離性。
S06 · implies
操作前
d(i,j)\ \text{vs}\ d(j,i)操作後
\forall i,j\in X:\ d(i,j)=d(j,i)
條件:無
規則:finite_exhaustion · 依賴:G1
葉節點依據:finite_exhaustion
比對 6 組對稱位置:d(0,1)=d(1,0)=1,d(0,2)=d(2,0)=2,d(0,3)=d(3,0)=1,d(1,2)=d(2,1)=1,d(1,3)=d(3,1)=2,d(2,3)=d(3,2)=1;對角線自然對稱。表等於它的轉置。
S07 · case_split
操作前
(i,j,k)\in X^3
操作後
i=k\ \lor\ (i\neq k\land(j=i\lor j=k))\ \lor\ i,j,k\ \text{pairwise distinct}條件:無
規則:case_analysis · 依賴:S02, S03, S04
葉節點依據:case_analysis
三角不等式 d(i,k)≤d(i,j)+d(j,k) 要對全部 64 個有序三元組成立。把三元組分成三種情形:A:i=k;B:i≠k 且 j 等於 i 或 k;C:i、j、k 兩兩相異。子步 S07.1 到 S07.3 逐一處理,S07.4 確認三種情形恰好涵蓋全部 64 個三元組。
S08 · implies
操作前
\text{cases A, B, C}操作後
\forall i,j,k\in X:\ d(i,k)\le d(i,j)+d(j,k)
條件:無
規則:case_analysis · 依賴:S07, S07.1, S07.2, S07.3, S07.4
葉節點依據:case_analysis + finite_exhaustion
三種情形都已證明不等式成立,且涵蓋全部 64 個三元組,依分情形證明,三角不等式對 X 的每個有序三元組成立。N1 另以公式 d(i,j)=min(|i−j|, 4−|i−j|) 窮舉 64 個三元組作交叉核對。
S09 · implies
操作前
\text{nonnegativity, separation, symmetry, triangle inequality}操作後
(X,d)\ \text{is a metric space}條件:無
規則:mko_metric_def · 依賴:S02, S05, S06, S08
葉節點依據:mko_metric_def + and_intro_elim
四項條件分別由 S02、S05、S06、S08 給出,所以 (X,d) 是度量空間。結論只屬於這個指定的有限模型。
S10 · implies
操作前
e\ \text{on } Y=\{0,1,2\}操作後
e\ge 0,\ e(x,y)=0\Leftrightarrow x=y,\ e(x,y)=e(y,x)
條件:無
規則:finite_exhaustion · 依賴:G2
葉節點依據:finite_exhaustion
逐格查候選乙:9 個值都非負;對角線三格為 0;非對角線六格是 1、3、1、1、3、1,都不為 0;e(0,1)=e(1,0)=1,e(0,2)=e(2,0)=3,e(1,2)=e(2,1)=1,表對稱。前三項全部通過。
S11 · implies
操作前
e(0,2)\ \text{vs}\ e(0,1)+e(1,2)操作後
3>1+1=2
條件:無
規則:order_basics · 依賴:G2
葉節點依據:order_basics + numeric_evaluation
取三元組 (0,1,2):e(0,2)=3,而 e(0,1)+e(1,2)=1+1=2。3>2,所以三角不等式在這個三元組失敗:經過點 1 的路比直接距離更短。
S12 · implies
操作前
\exists(i,j,k):\ e(i,k)>e(i,j)+e(j,k)
操作後
(Y,e)\ \text{is not a metric space}條件:無
規則:quantifier_negation · 依賴:S10, S11
葉節點依據:quantifier_negation + mko_metric_def
三角不等式是全稱命題;S11 給出反例,依量詞否定它為假,所以 (Y,e) 不是度量空間,儘管 S10 的非負、分離、對稱全部通過。
S13 · implies
操作前
f(0,1)=0,\ 0\neq 1
操作後
(Z,f)\ \text{is not a metric space}條件:無
規則:mko_metric_def · 依賴:G3
葉節點依據:mko_metric_def + metric_def + quantifier_negation
候選丙的 9 個值都非負、表對稱、對角線為零;但 f(0,1)=0 而 0≠1,違反「d(x,y)=0 推出 x=y」,分離失敗,所以不是度量(這種表在文獻中稱為偽度量)。只看非負、對稱與對角線會漏掉它。
局部子步與引理
S07.1 · implies
操作前
i=k
操作後
d(i,k)=0\le d(i,j)+d(j,i)
條件:i=k
規則:order_basics · 依賴:S07, S02, S03
葉節點依據:order_basics + add_zero
情形 A:i=k,左邊 d(i,i)=0(S03);右邊是兩個非負數之和(S02),所以 ≥0。0≤右邊,不等式成立。
S07.2 · implies
操作前
i\neq k,\ j\in\{i,k\}操作後
d(i,j)+d(j,k)=d(i,k)
條件:i\neq k
規則:eq_replace · 依賴:S07, S03
葉節點依據:eq_replace + add_zero + order_basics
情形 B:若 j=i,右邊為 d(i,i)+d(i,k)=0+d(i,k)=d(i,k);若 j=k,右邊為 d(i,k)+d(k,k)=d(i,k)+0=d(i,k)。兩種子情形中右邊都恰好等於左邊,所以 d(i,k)≤右邊以等號成立。
S07.3 · implies
操作前
i,j,k\ \text{pairwise distinct}操作後
d(i,k)\le 2\le d(i,j)+d(j,k)
條件:i\neq j,\ j\neq k,\ i\neq k
規則:order_basics · 依賴:S07, S02, S04
葉節點依據:order_basics + numeric_evaluation
情形 C:i≠j 與 j≠k,由 S04,d(i,j)≥1 且 d(j,k)≥1,所以右邊 ≥1+1=2;由 S02,每個距離 ≤2,所以 d(i,k)≤2。依序的傳遞,d(i,k)≤右邊。
S07.4 · implies
操作前
|A|+|B|+|C|
操作後
16+24+24=64=4^3
條件:無
規則:finite_counting_basics · 依賴:S07
葉節點依據:finite_counting_basics + numeric_evaluation
三種情形互斥且窮盡:若 i=k 屬 A;否則 i≠k,此時 j 等於 i 或 k 屬 B,與兩者都不同屬 C。計數:A 有 4·4=16 個(選 i 與 j);B 有 2·(4·3)=24 個(選相異的 i、k,再讓 j 等於其中之一);C 有 4·3·2=24 個。合計 64=4³,正是全部有序三元組。