为什么这个简单的实数证明没有被自动（甚至大锤）证明

Question

我做错了什么/忘记了 isabelle 无法自动证明这一点：

lemma "sqrt 5 = (1 + sqrt 5) / 2 - (1 - sqrt 5) / 2"
  apply auto
  sorry

这才是我真正想证明的：

fun fib :: "nat ⇒ nat" where
  "fib (Suc 0) = Suc 0" 
| "fib (Suc (Suc 0)) = Suc 0"
| "fib (Suc n)  = (fib (n - 1)) + (fib (n - 2))"

lemma "(n::nat) > 0 ⟹ fib n = (1 / sqrt 5) * (
      (((1 + sqrt 5) / 2)^n) - 
      (((1 - sqrt 5) / 2)^n)
      )"
proof(induction n)
  case 0
  then show ?case 
    by auto
next
  case (Suc n)
  then show ?case 
  proof(induction n)
    case 0
    then show ?case 
      apply(auto)
      sorry          
  next
    case (Suc n)
    then show ?case 
      apply auto
      sorry
  qed
qed

Answer 1

Sledgehammer 通常不擅长进行繁重的算术重写，而这是这里需要的。使用简化器的证明方法，如 auto 和 simp，擅长于此。但是你必须给他们正确的规则。

为此有许多定理集：

algebra_simps，标准化术语 w.r.t。结合性、交换性和分配性（本质上是按升序对所有内容进行排序并相乘）
field_simps，另外交叉乘分数。但要注意：分母必须可证明是非零的。如果简化器不能证明这一点，它就不会交叉相乘。如果分母是几个因数的乘积，可能先把乘积相乘，然后分母就丑到不能显示非零了。
divide_simps 与 field_simps 类似，只是它不使用分配性，并且总是交叉通过为分母为零的情况引入大小写区分来乘以。（在 Isabelle/HOL 中，x / 0 = 0 根据定义成立。）

您在这里需要的另一个规则是 power2_eq_square 将平方重写为乘法。然后你得到：

lemma "sqrt 5 = (1 + sqrt 5) / 2 - ((1 - sqrt 5) / 2)^2"
apply (auto simp: field_simps power2_eq_square)

proof (prove)
goal (1 subgoal):
 1. False

所以这里有些地方不太对劲。正如 NieDzejkob 在评论中指出的那样，左侧应该是 sqrt 5 - 1。这样，证明就通过了。

顺便说一下，如果你不知道，斐波那契数列在 Isabelle/HOL 标准库中：https://isabelle.in.tum.de/library/HOL/HOL-Number_Theory/Fib.html

为什么这个简单的实数证明没有被自动（甚至大锤）证明

Why is this simple proof with real numbers not proven by auto (or even sledgehammer)

isabelle

theorem-proving