带有实数距离的 isabelle 终止

Question

也许有人可以帮我在 Isabelle 中提供终止证明。我试图从列表 A 构造一个新的子列表 B。为了构造 B，我一遍又一遍地阅读整个 A。取出元素并使用结果搜索下一个元素。我设计了一个简单的例子来说明：

给定的是随机实数列表。如果列表中的某个项目大于 P，我们就说列表中有一个数字 P。

definition pointOnList :: "real list ⇒ real ⇒ bool" where
  "pointOnList L P ≡ ∃ i. i < length L ∧ P < L!i"

我创建了一个函数，它总是取下一个更大的元素。

fun nextPoint :: "real list ⇒ real ⇒ real" where
  "nextPoint (X#Ls) P = (if (X > P)
    then (X)
    else (nextPoint Ls P))"

现在我正在尝试创建一个新的排序零件列表，方法是用 nextPoint 取出下一个比 P 大但小于 Q 的元素并继续此操作。

function listBetween :: "real list ⇒ real ⇒ real ⇒ real list" where
  "pointOnList L P ⟹ pointOnList L Q ⟹ listBetween L P Q = (if(P ≤ Q)
  then(P # (listBetween L (nextPoint L P) Q))
  else([]))"

我已经证明 nextPoint 总是 returns 越来越多：

lemma foo: "pointOnList P A ⟹ A < (nextPoint P A)"

relation "measure (size o fst o snd)“ 的终止证明不适用于实数……现在我不知道如何继续。

Answer 1

终止参数 relation "measure (size o fst o snd)" 不起作用有几个原因：

用你的引理 foo 你刚刚证明了价值增加。但是对于终止，你需要一个递减的措施。所以你可能想使用 difference
```
relation "measure (λ (L,P,Q). Q - P)"
```
即便如此，问题是 measure 期望映射到自然 numbers 而 Q - P 是实数，所以这不起作用。您以前使用过 size，但是您的引理 foo 没有说明 size 和 < 之间的联系。此外，< 不是基于实数的有根据的顺序。
最终，我会尽量避免在这个简单的例子中对实数进行推理，并采取类似
的措施
```
measure (λ (L,P,Q). length [ A . A <- L, P < A])"
```
并相应地调整 foo 的陈述。

Answer 2

要显示 Isabelle 中的终止，您必须证明递归调用遵循有根据的关系。最简单的方法是给出一个返回自然数的终止度量，该自然数随着每次调用而变小。这不适用于实数，因为它们没有充分的根据——你可能有类似 1 → 1/2 → 1/4 → 1/8 → …

在您的案例中使用的终止度量是满足条件的列表元素的数量，即 length (filter (λx. P ≤ x ∧ x ≤ Q)) l。但是，请注意，如果 Q 大于列表中的所有数字，您的定义将无法工作。

你的定义有点费力和复杂。我推荐以下定义：

listBetween L P Q = sort (filter (λx. P ≤ x ∧ x ≤ Q) L)

或者，等价地，

listBetween L P Q = sort [x ← L. x ∈ {P..Q}]

但是请注意，此定义不会丢弃同一数字的多次出现，即 listBetween L 0 10 [2,1,2] = [1,2,2]。如果你想把它们扔掉，你可以使用 remdups.

另请注意，pointOnList L P ≡ ∃ i. i < length L ∧ P < L!i 之类的东西几乎不是您想要的 - 此处无需使用显式列表索引。就做 ∃x∈set L. P < x.

带有实数距离的 isabelle 终止

isabelle termination with distance of real numbers

termination

isabelle