如何在 lambda 演算中创建多态对，例如“( a : type A, b : type B ) ”

Question

我正在从事 Lambda 演算的项目，我正在尝试使用 coqide 编写多态性代码但是在编写尊重类型 pprod

的构造函数时遇到问题

Definition pprod : Set -> Set -> Set  := fun A B => forall T : Set , (A -> B -> T) -> T.

我对 pcpl 有疑问

Definition pcpl : Set -> Set -> pprod :=
  fun A B T  : Set => fun (a : A) (b : B) => fun k : A -> B -> T => k a b.

这是我得到的错误：

The term "pprod" has type "Set -> Set -> Set"
which should be Set, Prop or Type.

Answer 1

问题是您在 Set 上进行量化，因此生成的产品类型不能是 Set 类型，而是更大的 Type 类型。所以你的定义应该看起来像

   Definition pprod : Set -> Set -> Type  := fun A B => forall T : Set , (A -> B -> T) -> T.

产品的构造函数应该如下所示

Definition pcpl (A : Set) (B : Set) : A -> B -> pprod A B :=
  fun (a : A) (b : B) => fun T  : Set =>  fun k : A -> B -> T => k a b.

另一种方法是使用 Coq 中的多态类型，即 Prop:

中的类型

 Definition pprod : Prop -> Prop -> Prop  := 
fun A B => forall T : Prop , (A -> B -> T) -> T.
Definition pcpl (A : Prop) (B : Prop) : A -> B -> pprod A B :=
  fun (a : A) (b : B) => fun T  : Prop =>  fun k : A -> B -> T => k a b.

注意 Coq 中的宇宙有点混乱。有关详细信息，请参阅 What is different between Set and Type in Coq?。

我将借此机会宣传新的 Proof Assistants 堆栈交换。

如何在 lambda 演算中创建多态对，例如“( a : type A, b : type B ) ”

how to create a polymorphe couple such as "( a : type A, b : type B ) " in lambda-calculus

coq

lambda-calculus

coqide