module plfa.part1.Equality where

我们在论证的过程中经常会使用相等性。给定两个都为 A 类型的项 MN, 我们用 M ≡ N 来表示 MN 可以相互替换。在此之前, 我们将相等性作为一个基础运算,而现在我们来说明如何将其定义为一个归纳的数据类型。

导入

本章节没有导入的内容。本书的每一章节,以及 Agda 标准库的每个模块都导入了相等性。 我们在此定义相等性,导入其他内容将会产生冲突。

相等性

我们如下定义相等性:
data _≡_ {A : Set} (x : A) : A  Set where
  refl : x  x

用其他的话来说,对于任意类型 A 和任意 A 类型的 x,构造子 refl 提供了 x ≡ x 的证明。所以,每个值等同于它本身,我们并没有其他办法来证明值的相等性。 这个定义里有不对称的地方,_≡_ 的第一个参数(Argument)由 x : A 给出, 而第二个参数(Argument)则是由 A → Set 的索引给出。 这和我们尽可能多的使用参数(Parameter)的理念相符。_≡_ 的第一个参数(Argument) 可以作为一个参数(Parameter),因为它不会变,而第二个参数(Argument)则必须是一个索引, 这样它才可以等于第一个。

我们如下定义相等性的优先级:

infix 4 _≡_

我们将 _≡_ 的优先级设置为 4,与 _≤_ 相同,所以其它算术运算符的结合都比它紧密。 由于它既不是左结合,也不是右结合的,因此 x ≡ y ≡ z 是不合法的。

相等性是一个等价关系(Equivalence Relation)

一个等价关系是自反、对称和传递的。其中自反性可以通过构造子 refl 直接从相等性的定义中得来。 我们可以直接地证明其对称性:

sym :  {A : Set} {x y : A}
   x  y
    -----
   y  x
sym refl = refl

这个证明是怎么运作的呢?sym 参数的类型是 x ≡ y,但是等式的左手边被 refl 模式实例化了, 这要求 xy 相等。因此,等式的右手边需要一个类型为 x ≡ x 的项,用 refl 即可。

交互式地证明 sym 很有教育意义。首先,我们在左手边使用一个变量来表示参数,在右手边使用一个洞:

sym : ∀ {A : Set} {x y : A}
  → x ≡ y
    -----
  → y ≡ x
sym e = {! !}

如果我们进入这个洞,使用 C-c C-,,Agda 会告诉我们:

Goal: .y ≡ .x
————————————————————————————————————————————————————————————
e  : .x ≡ .y
.y : .A
.x : .A
.A : Set

在这个洞里,我们使用 C-c C-c e,Agda 会将 e 逐一展开为所有可能的构造子。 此处只有一个构造子:

sym : ∀ {A : Set} {x y : A}
  → x ≡ y
    -----
  → y ≡ x
sym refl = {! !}

如果我们再次进入这个洞,重新使用 C-c C-,,然后 Agda 现在会告诉我们:

 Goal: .x ≡ .x
 ————————————————————————————————————————————————————————————
 .x : .A
 .A : Set

这是一个重要的步骤—— Agda 发现了 xy 必须相等,才能与模式 refl 相匹配。

最后,我们回到洞里,使用 C-c C-r,Agda 将会把洞变成一个可以满足给定类型的构造子实例。

sym : ∀ {A : Set} {x y : A}
  → x ≡ y
    -----
  → y ≡ x
sym refl = refl

我们至此完成了与之前给出证明相同的证明。

传递性亦是很直接:

trans :  {A : Set} {x y z : A}
   x  y
   y  z
    -----
   x  z
trans refl refl  =  refl

同样,交互式地证明这个特性是一个很好的练习,尤其是观察 Agda 的已知内容根据参数的实例而变化的过程。

合同性和替换性

相等性满足合同性(Congruence)。如果两个项相等,那么对它们使用相同的函数, 其结果仍然相等:

cong :  {A B : Set} (f : A  B) {x y : A}
   x  y
    ---------
   f x  f y
cong f refl  =  refl

两个参数的函数也满足合同性:

cong₂ :  {A B C : Set} (f : A  B  C) {u x : A} {v y : B}
   u  x
   v  y
    -------------
   f u v  f x y
cong₂ f refl refl  =  refl

在函数上的等价性也满足合同性。如果两个函数是相等的,那么它们作用在同一项上的结果是相等的:

cong-app :  {A B : Set} {f g : A  B}
   f  g
    ---------------------
    (x : A)  f x  g x
cong-app refl x = refl

相等性也满足替换性(Substitution)。 如果两个值相等,其中一个满足某谓词,那么另一个也满足此谓词。

subst :  {A : Set} {x y : A} (P : A  Set)
   x  y
    ---------
   P x  P y
subst P refl px = px

谓词是对于某类型为 A 的值之上的命题;因为我们将命题视作类型, 谓词则是对于 A 参数化的一个类型。 例如,参考我们之前在 Relations 章节中的例子, evenodd 是自然数 之上的谓词。 (我们将在 Decidable 章节中比较谓词的两种表示方式:以归纳数据类型 A → Set 或者以布尔值函数 A → Bool。)

等式链

我们在此演示如何使用等式链来论证,正如本书中使用证明形式。我们将声明放在一个叫做 ≡-Reasoning 的模块里,与 Agda 标准库中的格式相对应。

module ≡-Reasoning {A : Set} where

  infix  1 begin_
  infixr 2 step-≡-∣ step-≡-⟩
  infix  3 _∎

  begin_ :  {x y : A}  x  y  x  y
  begin x≡y  =  x≡y

  step-≡-∣ :  (x : A) {y : A}  x  y  x  y
  step-≡-∣ x x≡y  =  x≡y

  step-≡-⟩ :  (x : A) {y z : A}  y  z  x  y  x  z
  step-≡-⟩ x y≡z x≡y  =  trans x≡y y≡z

  syntax step-≡-∣ x x≡y      =  x ≡⟨⟩ x≡y
  syntax step-≡-⟩ x y≡z x≡y  =  x ≡⟨  x≡y  y≡z

  _∎ :  (x : A)  x  x
  x   =  refl

open ≡-Reasoning

这是我们第一次使用嵌套的模块。它包含关键字 module 和后续的模块名、 隐式或显式参数,以及关键字 where;之后模块中的内容(必须缩进)。 模块里可以包含任何形式的声明,也可以包含其他模块。 嵌套的模块和本书每章节所定义的顶层模块相似,只是顶层模块不需要缩进。 打开(open)一个模块会把模块内的所有定义导入进当前的环境中。

这也是我们第一次使用语法声明,它指明了左侧的项可以写成右边的语法形式。 语法 x ≡⟨ x≡y ⟩ y≡z 继承了声明 step-≡-⟩ 时使用的中缀式声明 infixr 2, 这种特殊的语法只要导入了 step-≡-⟩ 标识符就能使用,类似于 step-≡-∣

除了引入带特殊语法的 step-≡ 外,我们也可以直接声明 _≡⟨_⟩′_

_≡⟨_⟩′_ :  {A : Set} (x : A) {y z : A}  x  y  y  z  x  z
x ≡⟨ x≡y ⟩′ y≡z  =  trans x≡y y≡z

间接使用它的原因是 step-≡-⟩ 反转了实参的顺序,这样能让 Agda 更高效地执行类型推导。 在 Lambda 一章中我们会遇到一些长等式链,因此效率是很重要的。

我们来看看如何用等式链证明传递性:

trans′ :  {A : Set} {x y z : A}
   x  y
   y  z
    -----
   x  z
trans′ {A} {x} {y} {z} x≡y y≡z =
  begin
    x
  ≡⟨ x≡y 
    y
  ≡⟨ y≡z 
    z
  

根据其定义,等式右边会被解析成如下:

begin (x ≡⟨ x≡y ⟩ (y ≡⟨ y≡z ⟩ (z ∎)))

这里 begin 的使用纯粹是装饰性的,因为它直接返回了其参数。其参数包括了 _≡⟨_⟩_ 作用于 xx≡yy ≡⟨ y≡z ⟩ (z ∎)。第一个参数是一个项 x, 而第二、第三个参数分别是等式 x ≡ yy ≡ z 的证明,它们在 _≡⟨_⟩_ 的定义中用 trans 连接起来,形成 x ≡ z 的证明。y ≡ z 的证明包括了 _≡⟨_⟩_ 作用于 yy≡zz ∎。第一个参数是一个项 y,而第二、第三个参数分别是等式 y ≡ zz ≡ z 的证明, 它们在 _≡⟨_⟩_ 的定义中用 trans 连接起来,形成 y ≡ z 的证明。最后,z ≡ z 的证明包括了 _∎ 作用于 z 之上,使用了 refl。经过化简,上述定义等同于:

trans x≡y (trans y≡z refl)

我们可以把任意等式链转化成一系列的 trans 的使用。这样的证明更加精简, 但是更难以阅读。 的小窍门意味着等式链化简成为的一系列 trans 会以 trans e refl 结尾,这里的 e 是等式的证明。

(这个技巧可能看起来效率低下,因为 trans e refle 都证明了相同的相等性。 但这种低效率是我们实现等式链的良好记法的关键。如果它能提高可读性,就不应该担心低效率!)

Exercise trans and ≡-Reasoning (practice)

Sadly, we cannot use the definition of trans' using ≡-Reasoning as the definition for trans. Can you see why? (Hint: look at the definition of _≡⟨_⟩_)

-- Your code goes here

等式链的另外一个例子

我们重新证明加法的交换律来作为等式链的第二个例子。我们首先重复自然数和加法的定义。 我们不能导入它们(正如本章节开头中所解释的那样),因为那样会产生一个冲突:

data  : Set where
  zero : 
  suc  :   

_+_ :     
zero    + n  =  n
(suc m) + n  =  suc (m + n)

为了节约空间,我们假设两条引理(而不是证明它们):

postulate
  +-identity :  (m : )  m + zero  m
  +-suc :  (m n : )  m + suc n  suc (m + n)

这是我们第一次使用假设(Postulate)。假设为一个标识符指定一个签名,但是不提供定义。 我们在这里假设之前证明过的东西,来节约空间。假设在使用时必须加以注意。如果假设的内容为假, 那么我们可以证明出任何东西。

我们接下来重复交换律的证明:

+-comm :  (m n : )  m + n  n + m
+-comm m zero =
  begin
    m + zero
  ≡⟨ +-identity m 
    m
  ≡⟨⟩
    zero + m
  
+-comm m (suc n) =
  begin
    m + suc n
  ≡⟨ +-suc m n 
    suc (m + n)
  ≡⟨ cong suc (+-comm m n) 
    suc (n + m)
  ≡⟨⟩
    suc n + m
  

论证的过程和之前的相似。我们在不需要解释的地方使用 _≡⟨⟩_,我们可以认为 _≡⟨⟩__≡⟨ refl ⟩_ 是等价的。

Agda 总是认为一个项与其化简的项是等价的。我们之所以可以写出

  suc (n + m)
≡⟨⟩
  suc n + m

是因为 Agda 认为它们是一样的。这也意味着我们可以交换两行的顺序,写出

  suc n + m
≡⟨⟩
  suc (n + m)

而 Agda 并不会反对。Agda 只会检查由 ≡⟨⟩ 隔开的项是否化简后相同。 而书写的顺序合不合理则是由我们自行决定。

练习 ≤-Reasoning (延伸)

章节 Relations 中的单调性证明亦可以用相似于 ≡-Reasoning 的,更易于理解的形式给出。 相似地来定义 ≤-Reasoning,并用其重新给出加法对于不等式是单调的证明。重写 +-monoˡ-≤+-monoʳ-≤+-mono-≤ 的定义。

-- 请将代码写在此处

重写

考虑一个自然数的性质,比如说一个数是偶数。我们重复之前给出的定义:

data even :   Set
data odd  :   Set

data even where

  even-zero : even zero

  even-suc :  {n : }
     odd n
      ------------
     even (suc n)

data odd where
  odd-suc :  {n : }
     even n
      -----------
     odd (suc n)

在前面的部分中,我们证明了加法满足交换律。给定 even (m + n) 成立的证据,我们应当可以用它来做 even (n + m) 成立的证据。

Agda 对这种论证有特殊记法的支持——我们之前提到过的 rewrite 记法。来启用这种记法, 我们只用编译程序指令来告诉 Agda 什么类型对应相等性:

{-# BUILTIN EQUALITY _≡_ #-}

我们然后就可以如下证明求证的性质:

even-comm :  (m n : )
   even (m + n)
    ------------
   even (n + m)
even-comm m n ev  rewrite +-comm n m  =  ev

在这里,ev 包括了所有 even (m + n) 成立的证据,我们证明它亦可作为 even (n + m) 成立的证据。一般来说,关键字 rewrite 之后跟着一个等式的证明,这个等式被用于重写目标和任意作用域内变量的类型。

交互性地证明 even-comm 是很有帮助的。一开始,我们先给左边的参数赋予变量,给右手边放上一个洞:

even-comm : ∀ (m n : ℕ)
  → even (m + n)
    ------------
  → even (n + m)
even-comm m n ev = {! !}

如果我们进入洞里,输入 C-c C-,,Agda 会报告:

Goal: even (n + m)
————————————————————————————————————————————————————————————
ev : even (m + n)
n  : ℕ
m  : ℕ

现在我们加入重写:

even-comm : ∀ (m n : ℕ)
  → even (m + n)
    ------------
  → even (n + m)
even-comm m n ev rewrite +-comm n m = {! !}

如果我们再次进入洞里,并输入 C-c C-,,Agda 现在会报告:

Goal: even (m + n)
————————————————————————————————————————————————————————————
ev : even (m + n)
n  : ℕ
m  : ℕ

目标里的参数被交换了。现在 ev 显然满足目标条件,输入 C-c C-a 会用 ev 来填充这个洞。 命令 C-c C-a 可以进行自动搜索,检查作用域内的变量是否和目标有相同的类型。

多重重写

我们可以多次使用重写,以竖线隔开。举个例子,这里是加法交换律的第二个证明,使用重写而不是等式链:

+-comm′ :  (m n : )  m + n  n + m
+-comm′ zero    n  rewrite +-identity n             =  refl
+-comm′ (suc m) n  rewrite +-suc n m | +-comm′ m n  =  refl

这个证明更加的简短。之前的证明用 cong suc (+-comm m n) 作为使用归纳假设的说明, 而这里我们使用 +-comm m n 来重写就足够了,因为重写可以将合同性考虑在其中。尽管使用重写的证明更加的简短, 使用等式链的证明能容易理解,我们将尽可能的使用后者。

深入重写

rewrite 记法实际上是 with 抽象的一种应用:

even-comm′ :  (m n : )
   even (m + n)
    ------------
   even (n + m)
even-comm′ m n ev with   m + n  | +-comm m n
...                  | .(n + m) | refl       = ev

总的来着,我们可以在 with 后面跟上任何数量的表达式,用竖线分隔开,并且在每个等式中使用相同个数的模式。 我们经常将表达式和模式如上对齐。这个第一列表明了 m + nn + m 是相同的,第二列使用相应等式来证明的前述的断言。 注意在这里使用的点模式(Dot Pattern).(n + m)。点模式由一个点和一个表达式组成, 在其他信息迫使这个值和点模式中的值相等时使用。在这里,m + nn + m 由后续的 +-comm m nrefl 的匹配来识别。我们可能会认为第一种情况是多余的,因为第二种情况中才蕴涵了需要的信息。 但实际上 Agda 在这件事上很挑剔——省略第一条或者更换顺序会让 Agda 报告一个错误。(试一试你就知道!)

在这种情况中,我们也可以使用之前定义的替换函数来避免使用重写:

even-comm″ :  (m n : )
   even (m + n)
    ------------
   even (n + m)
even-comm″ m n  =  subst even (+-comm m n)

尽管如此,重写是 Agda 工具箱中很重要的一部分。我们会偶尔使用它,但是它有的时候是必要的。

莱布尼兹(Leibniz)相等性

我们使用的相等性断言的形式源于 Martin-Löf,于 1975 年发表。一个更早的形式源于莱布尼兹, 于 1686 年发表。莱布尼兹断言的相等性表示不可分辨的实体(Identity of Indiscernibles): 两个对象相等当且仅当它们满足完全相同的性质。这条原理有时被称作莱布尼兹定律(Leibniz’ Law), 与史波克定律紧密相关:「一个不造成区别的区别不是区别」。我们在这里定义莱布尼兹相等性, 并证明两个项满足莱布尼兹相等性当且仅当其满足 Martin-Löf 相等性。

莱布尼兹相等性一般如下来定义:x ≐ y 当每个对于 x 成立的性质 P 对于 y 也成立时成立。 可能这有些出乎意料,但是这个定义亦足够保证其相反的命题:每个对于 y 成立的性质 P 对于 x 也成立。

xy 为类型 A 的对象。我们定义 x ≐ y 成立,当每个对于类型 A 成立的谓词 P, 我们有 P x 蕴涵了 P y

_≐_ :  {A : Set} (x y : A)  Set₁
_≐_ {A} x y =  (P : A  Set)  P x  P y

我们不能在左手边使用 x ≐ y,取而代之我们使用 _≐_ {A} x y 来提供隐式参数 A,这样 A 可以出现在右手边。

这是我们第一次使用等级(Levels)。我们不能将 Set 赋予类型 Set,因为这会导致自相矛盾, 比如罗素悖论(Russell’s Paradox)或者 Girard 悖论。不同的是,我们有一个阶级的类型:其中 Set : Set₁Set₁ : Set₂,以此类推。实际上,Set 本身就是 Set₀ 的缩写。定义 _≐_ 的等式在右手边提到了 Set,因此签名中必须使用 Set₁。我们稍后将进一步介绍等级。

莱布尼兹相等性是自反和传递的。自反性由恒等函数的变种得来,传递性由函数组合的变种得来:

refl-≐ :  {A : Set} {x : A}
   x  x
refl-≐ P Px  =  Px

trans-≐ :  {A : Set} {x y z : A}
   x  y
   y  z
    -----
   x  z
trans-≐ x≐y y≐z P Px  =  y≐z P (x≐y P Px)

对称性就没有那么显然了。我们需要证明如果对于所有谓词 PP x 蕴涵 P y, 那么反方向的蕴涵也成立。

sym-≐ :  {A : Set} {x y : A}
   x  y
    -----
   y  x
sym-≐ {A} {x} {y} x≐y P  =  Qy
  where
    Q : A  Set
    Q z = P z  P x
    Qx : Q x
    Qx = refl-≐ P
    Qy : Q y
    Qy = x≐y Q Qx

给定 x ≐ y 和一个特定的 P,我们需要构造一个 P y 蕴涵 P x 的证明。 我们首先用一个谓词 Q 将相等性实例化,使得 Q zP z 蕴涵 P x 时成立。 Q x 这个性质是显然的,由自反性可以得出,由此通过 x ≐ y 就能推出 Q y 成立。而 Q y 正是我们需要的证明,即 P y 蕴涵 P x

我们现在来证明 Martin-Löf 相等性蕴涵了莱布尼兹相等性,以及其逆命题。在正方向上, 如果我们已知 x ≡ y,我们需要对于任意的 P,将 P x 的证明转换为 P y 的证明。 我们很容易就可以做到这一点,因为 xy 相等意味着任何 P x 的证明即是 P y 的证明。

≡-implies-≐ :  {A : Set} {x y : A}
   x  y
    -----
   x  y
≡-implies-≐ x≡y P  =  subst P x≡y

因为这个方向由替换性可以得来,如之前证明的那样。

在反方向上,我们已知对于任何 P,我们可以将 P x 的证明转换成 P y 的证明, 我们需要证明 x ≡ y

≐-implies-≡ :  {A : Set} {x y : A}
   x  y
    -----
   x  y
≐-implies-≡ {A} {x} {y} x≐y  =  Qy
  where
    Q : A  Set
    Q z = x  z
    Qx : Q x
    Qx = refl
    Qy : Q y
    Qy = x≐y Q Qx

此证明与莱布尼兹相等性的对称性证明相似。我们取谓词 Q,使得 Q zx ≡ z 成立时成立。 那么 Q x 是显然的,由 Martin Löf 相等性的自反性得来。从而 Q yx ≐ y 可得, 而 Q y 即是我们所需要的 x ≡ y 的证明。

(本部分的内容由此处改编得来: ≐≃≡: Leibniz Equality is Isomorphic to Martin-Löf Identity, Parametrically 作者:Andreas Abel、Jesper Cockx、Dominique Devries、Andreas Nuyts 与 Philip Wadler, 草稿,2017)

全体多态

正如我们之前看到的那样,不是每个类型都属于 Set,但是每个类型都属于类型阶级的某处, Set₀Set₁Set₂等等。其中 SetSet₀ 的缩写,此外 Set₀ : Set₁Set₁ : Set₂,以此类推。 当我们需要比较两个属于 Set 的类型的值时,我们之前给出的定义是足够的, 但如果我们需要比较对于任何等级 ,两个属于 Set ℓ 的类型的值该怎么办呢?

答案是全体多态(Universe Polymorphism),一个定义可以根据任何等级 来做出。 为了使用等级,我们首先导入下列内容:

open import Level using (Level; _⊔_) renaming (zero to lzero; suc to lsuc)

我们将构造子 zerosuc 重命名至 lzerolsuc,为了防止自然数和等级之间的混淆。

等级与自然数是同构的,有相似的构造子:

lzero : Level
lsuc  : Level → Level

Set₀Set₁Set₂ 等名称,是下列的简写:

Set lzero
Set (lsuc lzero)
Set (lsuc (lsuc lzero))

以此类推。我们还有一个运算符:

_⊔_ : Level → Level → Level

给定两个等级,返回两者中较大的那个。

下面是相等性的定义,推广到任意等级:

data _≡′_ { : Level} {A : Set } (x : A) : A  Set  where
  refl′ : x ≡′ x

相似的,下面是对称性的推广定义:

sym′ :  { : Level} {A : Set } {x y : A}
   x ≡′ y
    ------
   y ≡′ x
sym′ refl′ = refl′

为了简洁,我们在本书中给出的定义将避免使用全体多态,但是大多数标准库中的定义, 包括相等性的定义,都推广到了任意等级,如上所示。

下面是莱布尼兹相等性的推广定义:

_≐′_ :  { : Level} {A : Set } (x y : A)  Set (lsuc )
_≐′_ {} {A} x y =  (P : A  Set )  P x  P y

之前,签名中使用了 Set₁ 来作为一个值包括了 Set 的类型;而此处,我们使用 Set (lsuc ℓ) 来作为一个值包括了 Set ℓ 的类型。

标准库中的大部分函数都泛化到了任意层级。例如,以下是复合的定义。

_∘_ :  {ℓ₁ ℓ₂ ℓ₃ : Level} {A : Set ℓ₁} {B : Set ℓ₂} {C : Set ℓ₃}
   (B  C)  (A  B)  A  C
(g  f) x  =  g (f x)

更多关于层级的信息可以从Agda 文档中查询。

标准库

标准库中可以找到与本章节中相似的定义。Agda 标准库将 _≡⟨_⟩_ 定义为 step-≡它反转了参数的顺序。标准库还定义了一个语法宏,它可以在你导入 step-≡ 时被自动导入,它能够恢复原始的参数顺序:

-- import Relation.Binary.PropositionalEquality as Eq
-- open Eq using (_≡_; refl; trans; sym; cong; cong-app; subst)
-- open Eq.≡-Reasoning using (begin_; _≡⟨⟩_; step-≡; _∎)

这里的导入以注释的形式给出,以防止冲突,如引言中解释的那样。

Unicode

本章节使用下列 Unicode:

≡  U+2261  等同于 (\==, \equiv)
⟨  U+27E8  数学左尖括号 (\<)
⟩  U+27E9  数学右尖括号 (\>)
∎  U+220E  证毕 (\qed)
≐  U+2250  趋近于极限 (\.=)
ℓ  U+2113  手写小写 L (\ell)
⊔  U+2294  正方形向上开口 (\lub)
₀  U+2080  下标 0 (\_0)
₁  U+2081  下标 1 (\_1)
₂  U+2082  下标 2 (\_2)