判断平等

Question

TL;DR: 在 Agda 中，给定 a : A 和 proof : A == B，我可以得到一个元素 a : B 吗？

在我不断尝试学习 Agda 的过程中，我创建了以下 Prime : nat -> Set 数据类型，它证明了自然数的原始性。

Prime zero = False
Prime (succ zero) = False
Prime (succ (succ n)) = forall {i : nat} -> divides i p -> i <N p -> zero <N i -> i == (succ zero)
  where
    p = succ (succ n)

这里：

False是没有构造函数的数据类型；
divides a b 是一种数据类型，它包含 k 事实证明 a * k = b;
a <N b 是一种数据类型，它包含 k 事实证明 a + k = b;
==是相等类型，只有一个构造函数refl；
自然数用 zero : nat 和 succ : nat -> nat 的明显方式定义。

我已经成功展示了 Prime (succ (succ zero)) 的一个成员，并证明了语句 Prime (succ (succ (succ (succ zero))))) 蕴含 False。

现在我要证明素数大于一：

primesAreGreaterThanOne : (p : Sg nat Prime) -> (succ zero <N value p)

哪里

Sg A pred 是依赖对 (p, pred(p)) 其中 p : A;
value : Sg A pred -> A 提取值并丢弃证明。

我已经证明了顺序的三分法：对于所有 a, b，a <N b 或 a == b 或 b <N a 为真。（我希望这个引理可以帮助我们避免任何被排除的中间问题。）因此，通过对 succ zero 和 value p 之间的顺序关系进行个案处理，我已经简化为我有一个p == zero 的证明和 Prime p 的证明以及 Prime zero 被定义为假的陈述。

现在，当然，这些陈述是矛盾的：因为我有 p == zero 的证明，我可以展示 Prime p == Prime zero 类型的居民，因此我有 Prime p == False.

但是我怎样才能把我的元素proof : Prime p（证明是p : Sg nat Prime的第二个组成部分）和"cast"变成False的一个元素？这些类型在命题上相等，但在判断上不相等。

Answer 1

事实证明这很容易；就去做吧 (tm).

typeCast : {a : _} {A : Set a} {B : Set a} (el : A) (pr : A == B) -> B
typeCast {a} {A} {.A} elt refl = elt

Answer 2

我想指出关于这个特定主题的一些理论背景。

Agda 的核心是 Martin Löf 的逻辑框架 (LF)，它是一个最小的依赖类型 lambda 演算，它为我们提供了依赖函数等。总的来说，Agda 基于内涵 ML 类型理论。

在 LF 中，有一个称为类型转换规则的规则指出

 Γ ⊢ t : A     Γ ⊢ A = B
--------------------------
        Γ ⊢ t : B

这会强制使用类型相等的术语。其中两种类型在定义上是相等的，由计算 (beta) 和外延性 (eta) 确定。

编辑澄清：在内涵式 TT 中，判断相等和命题相等是分开的，命题相等不会给你判断。如果您希望给定两个命题上相等的项的规则在判断上也相等，那么您将处于外延 TT 中，这通常是不可取的，因为它使类型检查无法判定。所以，在内涵 TT 中，它并不总是正确的。

判断平等

Judgemental equality

types

agda