使用 Curry-Howard 对应证明下一个命题逻辑陈述的正确方法是什么？

Question

我正在研究库里-霍华德对应关系。

给定命题逻辑语句：(¬p -> q) -> ((¬p -> ¬q) -> p).

我需要在 OCaml 中定义一个类型（作为命题）和一个函数（作为证明）。

我想到了下一个代码并卡住了：

type empty = | ;; 
let ex58: (('p->empty) -> 'q) -> (('p->empty) -> ('q->empty)) -> 'p = fun f g -> g(f)

错误：

This expression has type ('p -> empty) -> 'q but an expression was expected of type 'p -> empty.

Answer 1

进行此练习时，从为 not:

引入类型构造函数开始可能会更容易

type empty = |
type 'a not = 'a -> empty

然后使用显式通用量化重写练习：

let proof_by_contradiction: type p q. (p not -> q) -> (p not -> q not) -> p =
   ...

应该稍微改进错误消息

Error: This expression has type p not -> q but an expression was expected of type p not = p -> empty

在开始这个练习之前，尝试一下

可能会有用

let proof_by_negation:  type p q. (p -> q) -> (p -> q not) -> p not =
  ...

第一。

Answer 2

我很确定这不是建设性可证明的。

首先，请注意

¬¬p -> (¬p -> a)

对完全任意的 p 和 a 成立（从 ¬¬p 和 ¬p 你首先获得虚假证据，然后通过 ex falso quodlibet 你获得任何 a).

特别是，对于任何 q、

    ¬¬p -> ((¬p -> q) /\ (¬p -> ¬q))             // ("lemma")

成立（将先前的陈述应用于 a = q 和 a = ¬q）。

现在，如果您的原始陈述 ((¬p -> q) /\ (¬p -> ¬q)) -> p 为真，那么您可以预组合 ¬¬p -> ((¬p -> q) /\ (¬p -> ¬q))，从而获得 ¬¬p -> p。但这是双重否定消除，已知无法建设性地证明。

这是 Scala 3 中的完整构造（与 OCaml 有点密切相关；此处使用的语言子集应该很容易翻译成 OCaml）：

type ¬[A] = A => Nothing                               // negation
type /\[A, B] = (A, B)                                 // conjunction / product
type Claim[P, Q] = (¬[P] => Q) => (¬[P] => ¬[Q]) => P  // your claim
type DoubleNegationElimination[P] = ¬[¬[P]] => P

/** Ex falso quodlibet. */
def efq[X]: Nothing => X = f => f

/** Lemma, as explained above. */
def lemma[P, Q](a: ¬[¬[P]]): (¬[P] => Q) /\ (¬[P] => ¬[Q]) =
  val left: ¬[P] => Q = notP => efq(a(notP))
  val right: ¬[P] => ¬[Q] = notP => efq(a(notP))
  (left, right)

/** This shows that if you could prove your claim for any `P`, `Q`,
  * then you would also be able to prove double negation elimination
  * for `P`.
  */
def claimImpliesDoubleNegationElimination[P, Q](
  c: Claim[P, Q]
): DoubleNegationElimination[P] =
  notNotP => {
    val (left, right) = lemma[P, Q](notNotP)
    c(left)(right)
  }

/** This is an (incomplete, because impossible) proof of the double
  * negation elimination for any `P`. It is incomplete, because it
  * relies on the validity of your original claim.
  */
def doubleNegationElimination[P]: DoubleNegationElimination[P] =
  claimImpliesDoubleNegationElimination(claim[P, Unit])

/** There cannot be a constructive proof of this, because otherwise
  * we would obtain a constructive proof of `doubleNegationElimination`.
  */
def claim[P, Q]: Claim[P, Q] = ???

使用 Curry-Howard 对应证明下一个命题逻辑陈述的正确方法是什么？

What is a correct way to prove the next propositional logic statement using Curry–Howard correspondence?

types

functional-programming

ocaml

type-inference

curry-howard