你如何在证明中对依赖对进行操作？

Question

这是的跟进。多亏了 Kwartz，我现在有了一个命题如果 b 除 a 然后 b 除 a * c 对于任何整数 c，即：

alsoDividesMultiples : (a, b, c : Integer) ->
                       DivisibleBy a b ->
                       DivisibleBy (a * c) b

现在，我们的目标是证明这一说法。我意识到我不明白如何对依赖对进行操作。我尝试了一个更简单的问题，证明每个数字都可以被 1 整除。经过可耻的思考之后，我认为我想出了一个解决方案：

-- All numbers are divisible by 1.
DivisibleBy a 1 = let n = a in
  (n : Integer ** a = 1 * n)

这可以编译，但我怀疑它是否有效。为了验证我是不是错了，它稍微修改为：

-- All numbers are divisible by 1.
DivisibleBy a 1 = let n = a in
  (n : Integer ** a = 2 * n)

这也可以编译，这意味着我的 "English" 解释肯定是不正确的，因为我会把它解释为 "All numbers are divisible by one since every number is two times another integer"。因此，我不完全确定我用该声明展示的是什么。所以，我回去尝试了一种更传统的方式来说明问题：

oneDividesAll : (a : Integer) ->
                (DivisibleBy a 1)
oneDividesAll a = ?sorry

对于oneDividesAll的执行我不是很确定如何"inject"，事实上(n = a)。例如，我会（用英文）将此证明写为：

We wish to show that 1 | a. If so, it follows that a = 1 * n for some n. Let n = a, then a = a * 1, which is true by identity.

我不知道怎么说："Consider when n = a"。根据我的理解，rewrite 策略需要证明 n = a。

我尝试修改我的谬误证明：

oneDividesAll : (a : Integer) ->
                (DivisibleBy a 1)
oneDividesAll a = let n = a in (n : Integer ** a = b * n)

但这给出了：

   |
12 | oneDividesAll a = let n = a in (n : Integer ** a = b * n)
   |                   ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
When checking right hand side of oneDividesAll with expected type
        DivisibleBy a 1

Type mismatch between
        Type (Type of DPair a P)
and
        (n : Integer ** a = prim__mulBigInt 1 n) (Expected type)

任何 help/hints 将不胜感激。

Answer 1

首先，如果你想证明数字的属性，你应该使用Nat（或其他归纳类型）。 Integer 使用参数不能比 prim__mulBigInt : Integer -> Integer -> Integer 进一步论证的原语；你通过两个 Integer 得到一个。编译器不知道 任何东西 结果 Integer 的样子，所以它无法证明它。

所以我会同意 Nat:

DivisibleBy : Nat -> Nat -> Type
DivisibleBy a b = (n : Nat ** a = b * n)

再说一次，这是一个命题，不是证明。 DivisibleBy 6 0 是有效类型，但您找不到 proof : Divisible 6 0。所以你是对的

oneDividesAll : (a : Nat) ->
                (DivisibleBy a 1)
oneDividesAll a = ?sorry

这样，您就可以生成 oneDividesAll a : DivisibleBy a 1 形式的证明。那么，?sorry 这个洞里有什么？ :t sorry 给我们 sorry : (n : Nat ** a = plus n 0) （这只是 DivisibleBy a 1 伊德里斯所能解决的）。你对这对的右边部分感到困惑：x = y 是一种类型，但现在我们需要一个值——这就是你最后一个错误神秘错误消息提示的内容）。 = 只有一个构造函数，Refl : x = x。所以我们需要让等号两边的值相同，所以结果看起来像 (n ** Refl).

如您所想，我们需要将 n 设置为 a:

oneDividesAll a = (a ** ?hole)

对于所需的重写策略，我们查看 :search plus a 0 = a，并查看 plusZeroRightNeutral 具有正确的类型。

oneDividesAll a = (a ** rewrite plusZeroRightNeutral a in ?hole)

现在 :t hole 给我们 hole : a = a 所以我们可以自动完成 Refl:

oneDividesAll a = (a ** rewrite plusZeroRightNeutral a in Refl)

关于定理证明的一个很好的教程（其中也解释了为什么 plus a Z 不归约）在 Idris Doc.

你如何在证明中对依赖对进行操作？

How do you operate on dependent pairs in a proof?

idris