在 Agda 中编写证明

Question

我想写出命题"for all x there exist a y such that x < y and y is even "的证明。我这样试过...

-- ll means less function i.e ' < '

_ll_ : ℕ → ℕ → Bool
0 ll 0 = false
0 ll _ = true
a ll 0 = false
(suc a) ll (suc b) = a ll b 

even : ℕ → Bool
even 0 = true
even 1 = false
even (suc (suc n)) = even n

Teven : Bool → Set
Teven true = ⊤
Teven false = ⊥


thm0 : (x : ℕ) →  Σ[ y ∈ ℕ ]  (Teven ( and (x ll y) (even y))) 
thm0 0 = suc (suc zero) , record {}
thm0 (suc a) = ?

最后一行，即 'suc a' agda 无法找到解决方案。我曾经尝试写 2 * suc a , record {}。但这也行不通。任何帮助将不胜感激。

Answer 1

您真正想要的是一次执行两个步骤。

这种定义的问题是所谓的 "boolean blindness" - 通过将您的命题编码为布尔值，您会丢失它们包含的任何有用信息。结果是你必须依赖规范化来（希望）做它的事情，你不能以任何其他方式帮助 Agda（比如通过证明条款上的模式匹配）。

但是，对于您的情况，您可以稍微更改 thm0 的定义以帮助 Agda 进行规范化。 even 在每个递归步骤中执行两个 suc 步 - 您也可以让 thm0 执行两个步骤。

一起来看看：

thm0 : ∀ x → ∃ λ y → Teven ((x ll y) ∧ (even y))
thm0 zero = suc (suc zero) , tt

suc zero（也称为 1）有两个新案例：

thm0 (suc zero) = suc (suc zero) , tt

对于suc (suc x')：

thm0 (suc (suc x') = ?

现在，如果我们知道 y（你存在量化的那个）对于其他 y' 是 suc (suc y')，Agda 可以将 even y 规范化为 even y'（这只是遵循定义）。同样处理 "less-than" 证明 - 一旦你知道 x = suc (suc x') 和 y = suc (suc y') 对于某些 y' （x' 我们已经知道），你可以减少 x ll y 到 x' ll y'.

所以 y 的选择很简单...但是我们如何得到 y'（当然还有证明）？我们可以使用归纳（递归）并将 thm0 应用于 x'！请记住，给定 x'、thm0 returns 一些 y' 以及 even y' 和 x' ll y' 的证明 - 这正是我们所需要的。

thm0 (suc (suc a)) with thm0 a
... | y' , p = ?

然后我们简单地代入y = suc (suc y')和p（如前所述，(x ll y) ∧ even y缩减为(x' ll y') ∧ even y'，即p）。

最终代码：

thm0 : ∀ x → ∃ λ y → Teven ((x ll y) ∧ (even y))
thm0 zero = suc (suc zero) , tt
thm0 (suc zero) = suc (suc zero) , tt
thm0 (suc (suc x')) with thm0 x'
... | y' , p = suc (suc y') , p

然而，话虽如此，我还是反对这样做。不要将您的命题编码为布尔值，然后通过 Teven 在类型级别使用它们。这真的只适用于简单的事情，不能扩展到更复杂的命题。相反，尝试显式证明条件：

data _less-than_ : ℕ → ℕ → Set where
  suc : ∀ {x y} → x less-than y → x less-than suc y
  ref : ∀ {x}                   → x less-than suc x

data Even : ℕ → Set where
  zero    :                  Even 0
  suc-suc : ∀ {x} → Even x → Even (2 + x)

thm0 可以用一个简单的引理写成：

something-even : ∀ n → Even n ⊎ Even (suc n)
something-even zero = inj₁ zero
something-even (suc n) with something-even n
... | inj₁ x = inj₂ (suc-suc x)
... | inj₂ y = inj₁ y

（这表明 n 是偶数或其后继者是偶数）。其实thm0不用递归也可以实现！

thm0 : ∀ x → ∃ λ y → Even y × x less-than y
thm0 n with something-even n
... | inj₁ x = suc (suc n) , suc-suc x , suc ref
... | inj₂ y = suc n , y , ref

有趣的是，当我写这个定义时，我只是在 something-even (suc n) 上进行模式匹配并使用 C-a（自动完成）来填充右侧！当给予足够的提示时，Agda 可以在没有我帮助的情况下编写代码。

在 Agda 中编写证明

Writing Proofs in Agda

functional-programming

agda