为什么在使用 `rewriting` 时需要在这种情况下使用 `sym`？

Question

给定自然数的 Peano 定义：

data ℕ : Set where
  zero : ℕ
  suc  : ℕ → ℕ

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

我们可以通过不同的方法证明属性 ∀ (m : ℕ) → zero + m ≡ m + zero.

例如：

comm-+₀ : ∀ (m : ℕ) → zero + m ≡ m + zero
comm-+₀ zero = refl
comm-+₀ (suc n) =
  begin
    zero + suc n
  ≡⟨⟩
    zero + suc (zero + n)
  ≡⟨⟩
    suc (zero + n)
  ≡⟨ cong suc (comm-+₀ n) ⟩
    suc (n + zero)
  ≡⟨⟩
    suc n + zero
  ∎

更紧凑：

comm-+₀ : ∀ (m : ℕ) → zero + m ≡ m + zero
comm-+₀ zero = refl
comm-+₀ (suc n) = cong suc (comm-+₀ n)

如果需要，我们甚至可以使用 rewrite 而放弃 cong:

comm-+₀ : ∀ (m : ℕ) → zero + m ≡ m + zero
comm-+₀ zero = refl
comm-+₀ (suc n) rewrite comm-+₀ n = refl

但是等等！那是行不通的。 Agda 会告诉我们表达式是错误的，因为它无法证明以下内容：

suc (n + 0) ≡ suc (n + 0 + 0)

如果我们向 Agda 提供属性、sym (comm-+₀ n) 的对称重写，它将进行类型检查而没有错误。

所以，我的问题是：为什么在这种情况下我们需要 sym？没有其他策略，证明工作得很好。重写是否同时在两侧而不是左侧工作？

Answer 1

在每种情况下，当 m 的形式为 suc n 时，目标是：

suc n ≡ suc (n + 0)

如您所见，要通过提供正确键入的术语来解决此目标，正确的方法是：

cong suc (comm-+₀ n)

但是，当使用 rewrite 和等式 a ≡ b 时，您可以通过将 a 的 all occurences 替换为 b 在您的例子中，在类型为 n ≡ n + 0 的数量 comm-+₀ n 上使用 rewrite 会导致 n 的每次出现都被 n + 0 替换，因此将目标从

suc n ≡ suc (n + 0)

到

suc (n + 0) ≡ suc (n + 0 + 0)

这不是你想做的。由于重写将左侧的所有出现都替换为右侧，因此使用 sym 反转等式将用 n 代替 n + 0 的唯一出现，从而将目标从

suc n ≡ suc (n + 0)

到

suc n ≡ suc n

这是您的预期行为，让您直接使用 refl 得出结论。这解释了为什么你需要使用 sym.

总结一下：

rewrite 直接与目标类型交互。
rewrite 从左到右重写。
rewrite 重写它在目标类型中找到的所有事件。

可在此处找到有关 rewrite 的更多信息：

https://agda.readthedocs.io/en/v2.6.0.1/language/with-abstraction.html#with-rewrite

为什么在使用 `rewriting` 时需要在这种情况下使用 `sym`？

Why does `sym` need to be used in this case when using `rewriting`?

agda