在 Agda 中证明加法的交换性

Question

我试图证明加法在 Agda 中是可交换的，但我无法让它工作。下面是相关代码，最下面是两个麻烦的目标：

cong : ∀{A B : Set} (f : A → B) {x y : A} (eq : x ≡ y) → f x ≡ f y
cong f refl = refl

plus-assoc : ∀ x {y z} → (x + y) + z ≡ x + (y + z)
plus-assoc zero = refl
plus-assoc (suc x) = cong suc (plus-assoc x)

plus-zero : ∀ x → x + zero ≡ x
plus-zero zero = refl
plus-zero (suc x) rewrite plus-zero x = refl

plus-suc : ∀ x {y} → x + suc y ≡ suc (x + y)
plus-suc zero = refl
plus-suc (suc x) = cong suc (plus-suc x)

plus-comm : ∀ x {y} → x + y ≡ y + x
plus-comm zero = { }0
plus-comm (suc x) = { }1

Agda 找到的目标是

Goal: .y ≡ .y + zero

这显然看起来很像加零，但如果我不知道如何用 .y 重写。

第二个进球是

Goal: suc (x + .y) ≡ .y + suc x
——————————————————————————————————————————
.y : Nat
x  : Nat

如果我像这样用 plus-suc 重写：

plus-comm (suc x) rewrite plus-suc x = { }1

我收到这个错误：

Cannot rewrite by equation of type {y : Nat} →
                               x + suc y ≡ suc (x + y)
when checking that the clause
plus-comm (suc x) rewrite plus-suc x = ? has type
(x : Nat) {y : Nat} → x + y ≡ y + x

我真的无法理解这个错误。有什么线索吗？我可以在没有隐式变量的情况下重写整个事情，因为这似乎让事情变得更加困难，但我得到了原样的代码，所以如果可能的话，我想保持原样。

谢谢！

Answer 1

您可以保留带有 y 的证明函数作为隐式参数，但您需要并且可以在定义中使用它。

pcomm : ∀ x {y} → x + y ≡ y + x
pcomm zero {y} = {!!}
pcomm (suc x) {y} = {!!}

您还可以在调用函数时提供隐式参数，例如 pcomm x {y}。该函数缺少一个关键参数以完成重写。

提示：如果一个函数有很多隐式参数，而您只关心提供一个特定的参数，则可以执行以下操作。

-- f {C = X}
f : ∀ {A B C : Set} → Set
f {C = C} = C

在 Agda 中证明加法的交换性

Proving commutativity of addition in Agda

agda