Header

上一篇 LdBeth:NuPRL 中的证明 (二) – 我从来不写递归的

这篇的主要內容是 Virtual Evidence: A Constructive Semantics for Classical LogicsConstructive Reading of Classical Logic 的导读。 也算是第一次展示了下 NuRPL 中的证明,順帯引入 squash type 的概念。

MLTT Agda 中要获得 LEM 得 posutulate (防止你们说 CubicalTT)。众所周知这样 p 出来的 LEM 虽然和 MLTT 相容,但还是沒有 computational meaning 的,这样的 classical logic 是沒有灵魂的。

那 NuPRL 是怎么解決这个的呢?

Recall, refinment type OR subtyping in NuPRL

$\{x:A\ |\ P(x) \}$

it is easy to get non dependent form

$\{S\ |\ T\}$

Unit type 只有一个 element $*$ ,因而当 proposition P 成立时 $\{Unit\ |\ P\}$ 也只有一个 element,而 P 为 False (which is an alias to Void) 时这个类型等于 Void。

在 ITT 中,P 的证明是一个具體的 p : P,而用 refinement type $\{Unit\ |\ P\}\; abbrev \;\{P\}$ 表示 classical logic 的命题就可以把 P 的证明给 squash to trivial。这样显然地,我们有把 constructive proof to classical proof 的 computation procedure $\lambda x.*\in P \implies \{P\}$ ,而反之则不一定成立,从而規避了任意用 classical proof 进行 constructive proof。

然后就要有 double negation rule $\lambda x.* \in \neg\neg P \implies \{P\}$ : $\neg\neg P$ 表明 P 不为 False,而由于 refinement type 的定义当 P 不为 False 时,因为 $\{ P\}$ 只可能有一个 element,所以很容易就得到它的 computational meaning,也就是 const trivial 这样一个函数。

这样就可以证明 $\forall P : \mathbb{P}\ . \{P\}\implies \neg\neg P$ ,也就是从 classical proposition 到 intutionistic double negation 的 formation。在 NuPRL 中的证明如下。

以及 lem 的 classical proposition 的证明。其实用 Auto tactic 可以直接证出,不过为了方便理解还是贴上有完整思路的版本。