在 Isabelle 中重新索引总和

Question

我正在尝试翻译我在 this answer into Isabelle and I managed 中给出的论点以几乎完全证明它。不过，我还需要证明：

"(∑k | k ∈ {1..n} ∧ d dvd k. f (k/n)) =
        (∑q | q ∈ {1..n/d}. f (q/(n/d)))" for d :: nat

我的想法是使用这个定理：

sum.reindex_bij_witness

但是，我无法实例化与定理的集合 S、T 相关的变换 i、j。原则上应该设置为：

S = {k. k ∈ {1..n} ∧ d dvd k}
T = {q. q ∈ {1..n/d}}
i k = k/d
j q = q d

我认为有打字错误。也许我应该使用 div?

Answer 1

首先请注意，您应该写coprime a b而不是gcd a b = 1。那是等价的（至少对于所有有 GCD 的类型），但使用起来更方便。

其次，我不会写⋀n. F n = …这样的假设。将其写为 defines 更有意义，即

lemma
  fixes F :: "nat ⇒ complex"
  defines "F ≡ (λn. …)"

第三，{q. q ∈ {1..n/d}}和{1..n/d}完全一样，建议你这样写

回答你的实际问题：如果你在问题中写的是你在 Isabelle 中的写法并且 n 和 d 是 nat 类型，你应该是意识到 {q. q ∈ {1..n/d}} 实际上意味着 {1..real n / real d}。如果 n / d > 1，这实际上是一组无限实数，可能不是您想要的。

您真正想要的可能是集合 {1..n div d}，其中 div 表示自然数的 division。这是有限组自然数字。

那么你可以很容易地证明以下内容：

lemma
  fixes f :: "real ⇒ complex" and n d :: nat
  assumes "d > 0" "d dvd n"
  shows "(∑k | k ∈ {1..n} ∧ d dvd k. f (k/n)) =
           (∑q∈{1..n div d}. f (q/(n/d)))"
  by (rule sum.reindex_bij_witness[of _ "λk. k * d" "λk. k div d"])
     (use assms in ‹force simp: div_le_mono›)+

关于 div

的注释

div和/表示相同的函数，即Rings.divide.divide。然而，/ 出于历史原因（也许是出于对 Pascal 的美好记忆），/ 额外施加了类型 class 限制 inverse，即它仅适用于具有inverse 函数。

在大多数实际情况下，这意味着 div 是一种通用的 div 环上的 ision 操作，而 / 仅适用于字段（或 div异能环，或像正式幂级数这样“几乎”场的事物。

如果您为自然数 a 和 b 写 a / b，因此这是一个类型错误。 Isabelle 的强制系统然后推断您可能打算写 real a / real b，这就是您得到的。

在这种情况下查看输出以确保推断的强制转换符合您的预期是个好主意。

调试不匹配规则

如果您应用了一些规则（例如使用 apply (rule …)）但它失败了并且您不明白为什么，可以通过一个小技巧来找出答案。如果您在 apply 之前添加 using [[unify_trace_failure]]，您会收到一条错误消息，指示统一失败的确切位置。在这种情况下，消息是

The following types do not unify:
(nat ⇒ complex) ⇒ nat set ⇒ complex
(real ⇒ complex) ⇒ real set ⇒ complex

这表明某处存在一组实数的求和，该求和应该是一组自然数的求和。

在 Isabelle 中重新索引总和

Reindexing sums in Isabelle

isabelle

关于 div

调试不匹配规则