证明 `weaken` 不会改变数字的值

Question

假设我们想证明削弱 Data.Fin 的上限不会改变数字的值。直观的表述方式是：

weakenEq : (num : Fin n) -> num = weaken num

现在让我们生成定义...稍等！让我们考虑一下该声明。 num 和 weaken num 有不同的类型。我们可以在这种情况下声明相等性吗？

= 上的文档建议我们可以尝试，但我们可能想改用 ~=~。好吧，无论如何，让我们继续生成定义和大小写拆分，结果是

weakenEq : (num : Fin n) -> num = weaken num
weakenEq FZ = ?weakenEq_rhs_1
weakenEq (FS x) = ?weakenEq_rhs_2

weakenEq_rhs_1洞的目标是FZ = FZ，从价值的角度来看还是有道理的。于是我们乐观地用Refl替换空洞，结果却失败了：

When checking right hand side of weakenEq with expected type
        FZ = weaken FZ

Unifying k and S k would lead to infinite value

一个有点神秘的错误消息，所以我们想知道这是否真的与类型不同有关。

无论如何，让我们再试一次，但现在使用 ~=~ 而不是 =。不幸的是，错误仍然存在。

那么，如何声明和证明weaken x不会改变x的值呢？这样做真的有意义吗？如果这是我可能想要 rewrite 一个 Vect n (Fin k) 和 Vect n (Fin (S k)) 的更大证明的一部分，我应该怎么做，这是通过 mapping weaken 在原始向量？

Answer 1

如果你真的想证明 Fin n 的值在应用弱化函数后没有改变，你需要证明这些值的相等性：

weakenEq: (num: Fin n) -> finToNat num = finToNat $ weaken num
weakenEq FZ     = Refl
weakenEq (FS x) = cong $ weakenEq x

Answer 2

你对 map (Data.Fin.finToNat) v = map (Data.Fin.finToNat . Data.Fin.weaken) v 的第二个 problem/Markus' 评论：

vectorWeakenEq : (v: Vect n (Fin k)) -> 
                 map Fin.finToNat v = map (Fin.finToNat . Fin.weaken) v
vectorWeakenEq [] = Refl
vectorWeakenEq (x :: xs) =
  rewrite sym $ weakenEq x in
  cong {f=(::) (finToNat x)} (vectorWeakenEq xs)

要了解为什么 num = weaken num 不起作用，让我们看一个反例：

getSize : Fin n -> Nat
getSize _ {n} = n

现在 x : Fin n、getSize x = n != (n + 1) = getSize (weaken x)。这不会发生在只依赖构造函数的函数上，比如 finToNat。所以你必须把自己限制在那些人身上，并证明他们的行为是那样的。

证明 `weaken` 不会改变数字的值

Proving `weaken` doesn't change the value of a number

idris