动力塔

Question

我想定义一个类型族 PowersetTower : Type -> nat -> Type 这样：

PowersetTower A 0 = A
PowersetTower A (n+1) = Ensemble (PowersetTower A n)（即PowersetTower A n -> Prop）

这可能吗？一个想法是

Inductive PowersetTower : Type -> nat -> Type :=
| base : forall (A : Type), PowersetTower A 0
| step : forall (A : Type) (n : nat), (PowersetTower A n -> Prop) -> PowersetTower A (S n)
.

但是这里 Coq 抱怨构造函数 step 中 PowersetTower 的非严格正数出现。但是，出现在箭头左侧的是 PowersetTower A n，而不是 PowersetTower A (S n)，那么为什么 Coq 禁止这样做呢？这对我来说似乎没问题，因为我正在使用 'smaller' 定义 'larger' 类型。如果接受此定义（可能使用 bypass_check(positivity) 属性）是否会导致问题？

Answer 1

我想你要定义的不是一个索引在n上的归纳族，而是一个依赖于n的类型。你可以通过递归来做到这一点：

Fixpoint PowersetTower (A : Type) (n : nat) : Type :=
  match n with
    | 0 => A
    | S n' => (PowersetTower A n') -> Prop
  end.

这是 n 上的一个完全有效的递归，因为它在递归调用中总是更小——虽然返回的术语恰好是一个类型，但这都是依赖类型的盐。

动力塔

Tower of powersets

coq

powerset