世界还不够

Question

我仍然试图将观测类型理论本身和整个事物嵌入到Agda中.

目前我有以下Universe层次结构:

Prop : Type 0 : Type 1 : ...
(? ? -> Type ?) : Type ?? : Type ??

为了定义宇宙多态函数的相等性,我需要添加一个代码Type ??,这迫使我添加Type ??到元理论中.在上一个问题中有更多相关内容.

以下是解释算子将类型提升到元理论的基本目标理论函数?_?.

mutual
  Eq : ? (?? lev ? ? -> ?? lev ? ? -> univ? ? ? univ? ? ? prop) ?
  eq : ? (?? lev ? ? -> ?? lev ? ? -> ? (univ? ?) ? A -> ? (univ? ?) ? B -> A ? B ? prop) ?

mutual
  coerce : ? (?? lev ? ? -> ?? lev ? ? -> ? (univ? ?) ? A -> ? (univ? ?) ? B -> Eq _ _ A B ? A ? B) ?
  postulate
    coherence : ? (?? lev ? ? -> ?? lev ? ? -> ? (univ? ?) ? A -> ? (univ? ?) ? B -> 
                     ? (Eq _ _ A B) ? r -> ? A ? x -> eq _ _ A B x (coerce _ _ A B r x)) ?

它的工作原理这种方式,但我想证明coherence,而不是假设.出现两个问题:

首先

如何证明相同的类型存在于同一个宇宙中？这是真的(在建设性意义上)吗？由于Conor McBride,我们有以下标语

我现在想的a == b意思是

一旦你了解到a并且b具有相同的类型,你就会知道它们具有相同的价值

但类型是价值 - 这并不意味着"只要你了解A并B躺在同一个宇宙中,你会知道它们具有相同的价值"吗？我问,因为我无法证明eq x y -> Eq (eq x z) (eq x y)其他方面(该论文提供了一个更普遍的引理,但这个足以得到sym,trans和其他人).问题是要将类型分配给cong (\z' -> eq z' z) pwhere p : eq x y,cong必须接受Universe多态函数,因为x并且y具有可观察的相等但定义上不同的类型.而且,由于功能的平等是逐点的,因此cong需要一种宇宙平等的证明,其中包括类型x和y谎言.在代码中它看起来像这样:

postulate
  refl : ? (?? lev ? ? -> ? (univ? ?) ? A -> ? A ? x -> eq _ _ A A x x) ?
  cong-levOf : ? (?? nat ? ? -> ?? nat ? ? ->
                    ? (univ ?) ? A -> ? (univ ?) ? B -> Eq _ _ A B ? ? ?? ?) ?

hsubstitutive : ? (?? nat ? ? -> ?? nat ? ? -> ?? nat ? ? ->
                     ? (univ ?) ? A -> ? (univ ?) ? B -> ? A ? x -> ? B ? y ->
                       ? (?? nat ? ? -> ? (univ ?) ? C -> C ? univ ?) ? D ->
                         Eq _ _ A B ? eq _ _ A B x y ? Eq _ _ (D _ A x) (D _ B y)) ?
hsubstitutive ? ? ? A B x y D r q =
  refl _ (?? nat ? ? -> ? (univ ?) ? C -> C ? univ ?) D _ _ (cong-levOf _ _ A B r) A B r x y q

cong-?z : ? (?? nat ? ? -> ?? nat ? ? -> ?? nat ? ? ->
               ? (univ ?) ? A -> ? (univ ?) ? B -> ? (univ ?) ? C ->
                 ? A ? x -> ? B ? y -> ? C ? z -> Eq _ _ A B ?
                   eq _ _ A B x y ? Eq _ _ (eq _ _ A C x z) (eq _ _ B C y z)) ?
cong-?z ? ? ? A B C x y z r q = hsubstitutive _ _ _ A B x y (? _ C' z' -> eq _ _ C' C z' z) r q

证明由假定的cong-levOf _ _ A B r地方提供cong-levOf.

第二

类型coherence是

coherence : ? (?? lev ? ? -> ?? lev ? ? -> ? (univ? ?) ? A -> ? (univ? ?) ? B -> 
                 ? (Eq _ _ A B) ? r -> ? A ? x -> eq _ _ A B x (coerce _ _ A B r x)) ?

但是,比方说的类型sym是

sym : ? (?? nat ? ? -> ?? nat ? ? -> ? (univ ?) ? A -> ? (univ ?) ? B ->
           ? A ? x -> ? B ? y -> Eq _ _ A B ? eq _ _ A B x y ? eq _ _ B A y x) ?

??而不是??到处都是.这样做的原因是该类型传递给refl在hsubstitutive是(?? nat ? ? -> ? (univ ?) ? C -> C ? univ ?),它不能是(?? lev ? ? -> ?? (univ? ?) ? C -> C ? univ? ?)需要的,因为该类型是太大了,没有目标理论类型.所以我们不能sym在证明时使用coherence,因为它无法处理足够大的类型.这同样适用于大多数其他组合器,这是coherence不可能的.

我看到的唯一解决方案是增加Type ??元理论和Type ??目标理论的代码.然后类型Eq,eq,refl和cong(我指的是通常的cong f : eq x y -> eq (f x) (f y)-即使是"小"( ??)Eq和eq它必须是Type ??,因为f可大了),将位于Type ??,所以我们可以如说,Type ??(但没有更高)等于本身.并且它们的类型coerce和coherence将会存在Type ??,所以虽然我们可以说它Type ??等于它自己,但是不可能通过这个等式来强制(听起来不是一个大问题).

我想而不是添加Type ??到层次结构中更容易实现它

Prop : Type 0 : Type 1 : ...
(? ? -> Type ?) : Type ?? : Type ?? : Type ?? : Type ?? : ...

但在我疯狂之前,你能说这听起来像是一个好计划吗？我是通过最后一次Type ??宇宙延伸来追逐我的尾巴吗？

我还将重复第一部分的问题:如何证明相同的类型存在于同一个宇宙中？这是真的(在建设性意义上)吗？"Eq A​​B是否意味着只要您了解A并B躺在同一个宇宙中,您就会知道它们具有相同的价值"？