证明在 Agda 中 n 乘以一个偶数得到一个偶数

Question

我正在尝试在 Agda 中将 1..n ∈ ℕ 的和定义为 n * (n + 1) / 2 并且需要证明 n*(n + 1) 是偶数。证明很简单，但似乎有一个概念我不明白，因为我是 Agda 的新手（虽然既不是数学也不是 haskell）并且是从 http://www.cse.chalmers.se/~ulfn/papers/afp08/tutorial.pdf 学到的（非常欢迎指向更高级的教程！）。

open import Data.Nat
open import Relation.Binary.PropositionalEquality
open import Data.Sum

-- A natural number is even, if there is a k ∈ ℕ with k * 2 = n.
data IsEven : ℕ → Set where
  even : (k : ℕ) → IsEven (k * 2)

-- A product is even, if one of the factors is even.
even-product : {n m : ℕ} → IsEven n ⊎ IsEven m → IsEven (m * n)
even-product {n} {m} (inj₁ (even k)) = even (m * k)
even-product {n} {m} (inj₂ (even k)) = even (n * k)

密码returns

m != 2 of type ℕ
when checking that the expression even (k * m) has type
IsEven (k * 2 * m)

我已经尝试使用 with 模式来说服编译器 k * 2 实际上是 n，但无济于事。将 m * k 切换为 k * m 得到

k * m != m of type ℕ
when checking that the expression even (k * m) has type
IsEven (m * (k * 2))

Answer 1

您可以通过输入 {! !} 标记围绕您尝试的解决方案并使用 C-c C-. 快捷方式。

even-product : {n m : ℕ} → IsEven n ⊎ IsEven m → IsEven (m * n)
even-product {n} {m} (inj₁ (even k)) = {!even (m * k)!}
even-product {n} {m} (inj₂ (even k)) = {!even (n * k)!}

重新加载文件，然后在第一个孔中用光标按下 C-c C-. 会得到以下响应：

Goal: IsEven (m * (k * 2))
Have: IsEven (m * k * 2)
————————————————————————————————————————————————————————————
n : ℕ
m : ℕ
k : ℕ

现在问题很清楚了：目标是证明 (m * (k * 2)) 是偶数，但是你有一个证明 (m * k * 2) 是偶数。

要解决此问题，您必须利用 * 是关联的这一事实。我将通过示例在这里假设它，但显然你想稍后再给它一个实际的证明。

postulate
  *-assoc : (k l m : ℕ) → k * (l * m) ≡ (k * l) * m

现在我们可以使用 rewrite 关键字和 *-assoc 来修复第一种情况：

even-product : {n m : ℕ} → IsEven n ⊎ IsEven m → IsEven (m * n)
even-product {n} {m} (inj₁ (even k)) rewrite *-assoc m k 2 = even (m * k)
even-product {n} {m} (inj₂ (even k)) = {!even (n * k)!}

在第二种情况下，C-c C-. 给出以下响应：

Goal: IsEven (k * 2 * n)
Have: IsEven (n * k * 2)
————————————————————————————————————————————————————————————
m : ℕ
n : ℕ
k : ℕ

所以现在你需要使用 * 的交换律和结合律。我将把完整的解决方案留给 reader.

作为练习

Answer 2

证明2 * sum(1..n) = n * (n+1)不是更容易吗？哪个表明 n*(n+1) 是偶数？

证明在 Agda 中 n 乘以一个偶数得到一个偶数

Prove that n times an even number yields an even number in Agda

proof

agda