在 Agda 中证明当且仅当的错误情况

Question

我试图了解如何在 agda 中创建一个有效的 "if and only if" 语句，但在证明它的错误案例以及在证明中使用归纳法时遇到问题。例如，我想使用 "less than or equal"，我将其定义为：

data ℕ : Set where
  zero : ℕ
  succ : ℕ → ℕ

data _leq_ : ℕ → ℕ → Set where
  0≤n : ∀ {n : ℕ} → zero leq n
  Sn≤Sm : ∀ {n m : ℕ} → (n leq m) → ((succ n) leq (succ m))

要定义 A 当且仅当 B，我们需要一对函数将 A 的证明用于 B 的证明，反之亦然，因此我定义：

record _∧_ (A B : Set) : Set where
  constructor _,_
  field
    fst : A
    snd : B
open _∧_

_iff_ : (A B : Set) → Set
A iff B = (A → B) ∧ (B → A)

现在我的问题是：我想证明 (n <= m+1) <=> (n+1 <= m+2) 的命题，所以公式如下：

prop₂ : ∀ (n m : ℕ) → (n leq (succ m)) iff ((succ n) leq (succ (succ m))) 
prop₂ zero zero = (λ x → Sn≤Sm 0≤n) , λ x → 0≤n
prop₂ zero (succ b) = (λ x → Sn≤Sm 0≤n) , (λ x → 0≤n)
prop₂ (succ a) zero = ?
prop₂ (succ a) (succ b) = ?

我的问题是

证明的第三行我需要给出一个从空集到空集的函数，但是不知道如何表述这个
在最后一行中，我希望使用归纳法，即说 prop2 (succ a) (succ b) = prop2 a b，但是 agda 不接受这样的类型？

Answer 1

如果我坚持你的发展，证明如下：

prop₂ : ∀ (n m : ℕ) → (n leq (succ m)) iff ((succ n) leq (succ (succ m))) 
prop₂ zero zero = (λ x → Sn≤Sm 0≤n) , λ x → 0≤n
prop₂ zero (succ b) = (λ x → Sn≤Sm 0≤n) , (λ x → 0≤n)
prop₂ (succ a) zero = Sn≤Sm , λ {(Sn≤Sm x) → x}
prop₂ (succ a) (succ b) = Sn≤Sm , λ {(Sn≤Sm x) → x}

然而，有更好的方法来证明属性。如您所见，代码中存在冗余，因为您对参数 a 和 b 进行了大小写拆分，而不是对它们的证明元素进行了大小写拆分，其中包含您的所有信息需要。这导致了以下证明，它更加优雅和简洁：

prop-better : ∀ {n m : ℕ} → (n leq (succ m)) iff ((succ n) leq (succ (succ m))) 
prop-better = Sn≤Sm , λ {(Sn≤Sm x) → x}

等价的第一个方向就是定义的 Sn≤Sm 构造函数，另一侧是通过对证明参数进行大小写拆分来完成的，它的形式必然是 Sn≤Sm x 因为这两个自然数的形式为 succ y。这为您提供了证明 x，这正是您所需要的。

Answer 2

我还想补充一点，这是共模匹配的完美候选者。

prop₂ : ∀ (n m : ℕ) → (n leq (succ m)) iff ((succ n) leq (succ (succ m)))
prop₂ n m .fst n≤m+1 = Sn≤Sm n≤m+1
prop₂ n m .snd (Sn≤Sm n≤m+1) = n≤m+1

在 Agda 中证明当且仅当的错误情况

Proving the false case of an if and only if in Agda

agda

theorem-proving