P. Wadler 的命题类型中的 "roundabout proof" 是什么？

Question

In 1935, at the age of 25, Gentzen15 introduced not one but two new formulations of logic—natural deduction and sequent calculus—that became established as the two major systems for formulating a logic and remain so to this day. He showed how to normalize proofs to ensure they were not "roundabout," yielding a new proof of the consistency of Hilbert's system. And, to top it off, to match the use of the symbol ∃ for the existential quantification introduced by Peano, Gentzen introduced the symbol ∀ to denote universal quantification. He wrote implication as A ⊃ B (if A holds, then B holds), conjunction as A & B (both A and B hold), and disjunction as A ∨ B (at least one of A or B holds).

什么是回旋证明？你能举个简单的例子吗？为什么会出现问题？

Answer 1

我们以连词为例：A ∧ B.

如果我们知道 A 和 B，我们可以推导出 A ∧ B:

 A   B
------- I
 A ∧ B

这称为引入规则。

对偶地，如果我们知道 A ∧ B 我们可以推导出 A，或者 B:

 A ∧ B          A ∧ B
------- E1     ------- E2
   A              B

这些是淘汰规则。

然后，如果我们知道 A 我们可以证明 A 作为首先使用引入规则推导 A ∧ A，然后将其分解为A（和另一个 A）使用消除规则：

 A   A
------- I
 A ∧ A
-------- E1
   A

而且这种回旋在较大的样张中也会出现

没有理由进行此往返：我们在起点结束！

相继演算"forbids"消元规则后引入规则。 Gentzen 的结果表明，此属性的逻辑与允许引入规则后消除规则的逻辑一样强大。如今这很重要，因为 space 的证明要小得多：首先我们消除（尽可能/需要地制作小公式），然后我们引入（建立目标）。这实际上很有用，例如，对于自动证明搜索或程序合成。

编辑这个答案的第一个版本证明了 A ∧ B:

 A ∧ B         A ∧ B
------- E1    ------- E2
   A             B
  ----------------- I
         A ∧ B

然而除了直接证明：

A ∧ B

-------- ID A∧B

它似乎是唯一的另一个 "simple proof"。在 Haskell 语法中，可以这样写：

proof :: (a, b) -> (a, b)
proof (x, y) = (x, y)
-- or
proof x = x
proof = id

哪些是相同的，并且是唯一合理的定义（除了严格性属性，逻辑不感兴趣）。例如：

proof :: (a, b) -> (a, b)
proof x = fst (x, x)

也有效，不再聪明了。

P. Wadler 的命题类型中的 "roundabout proof" 是什么？

What is a "roundabout proof" in Propositions as Types by P. Wadler?

logic

types

proof

curry-howard