无法评估具有自反传递闭包的表达式

Question

以下表达式几乎相同：

value "(1,5) ∈ trancl {(1::nat,2::nat),(2,5)}"
value "(1,5) ∈ rtrancl {(1::nat,2::nat),(2,5)}"

然而，第一个评估正常，第二个我得到以下错误：

Wellsortedness error:
Type nat not of sort {enum,equal}
No type arity nat :: enum

好像是恒等关系导致的错误：

value "(1::nat,5::nat) ∈ Id"

但是以下代码引理没有帮助：

lemma Id_code [code]: "(a, b) ∈ Id ⟷ a = b" by simp

能否请您建议如何修复它？为什么它不能从头开始工作？是代码引理不完整还是有更根本的原因？

Answer 1

当您查看 rtrancl 和 code_thms rtrancl:

的代码方程时，问题变得很明显

rtrancl r ≡ trancl r ∪ Id

这里，Id是恒等关系，即所有(x, x)的集合。如果你的类型是无限的，Id 和它的补集也将是无限的，并且没有办法用 Isabelle 代码生成器的默认集合表示（它是所有元素的列表）来表示它在集合中或所有不在集合中的元素。

Id 的代码等式也反映了这一点：

Id = (λx. (x, x)) ` set enum_class.enum

这里，enum_class.enum来自enum类型class，是一个类型所有值的列表。当您尝试评估 rtrancl.

时，这就是 enum 约束的来源

我认为不修改代码生成器设置中集合的表示就无法评估 rtrancl（即便如此，以可读形式打印结果也具有挑战性）。然而，让代码生成器评估 (1, 5) ∈ rtrancl … 之类的东西相对容易：您可以简单地注册一个代码展开规则，如下所示：

lemma in_rtrancl_code [code_unfold]: "z ∈ rtrancl A ⟷ fst z = snd z ∨ z ∈ trancl A"
  by (metis prod.exhaust_sel rtrancl_eq_or_trancl)

那么你的 value 命令就可以正常工作了。

Unable to evaluate expressions with a reflexive transitive closure