Agda排除中间的法则

Question

我听说阿格达的Martin-Lof类型理论与排除中的理论是一致的.我如何将其添加为假设？另外,在添加LEM之后,它是经典的一阶逻辑吗？我的意思是,我是否也有(对所有)=存在(不)等价？我不知道类型理论,所以如果你在类型理论中引用任何结果,请添加其他解释.

Answer 1

在MLTT中,exists对应于Data.Product在标准库中定义的从属对.它将存在的证据和它具有正确财产的证据打包在一起.

没有必要假设任何东西来证明存在主义陈述的否定意味着否定财产的普遍陈述:

??? : {A : Set} {B : A ? Set} ?
      ¬ (? ? a ? B a) ?
      ? a ? ¬ (B a)
??? ¬? a b = ¬? (a , b)

然而,为了证明相反,你确实需要排除中间的法则让证人出现在凭空.用新的假设扩展Agda真的很容易,你可以简单地写(Dec定义Relation.Nullary):

postulate LEM : (A : Set) ? Dec A

记住如何证明双重否定消除始终是一件好事,LEM并且我们将在以后需要它,所以它是(case_of_在(Function并在其中定义和解释README.Case):

¬¬A?A : {A : Set} ? ¬ (¬ A) ? A
¬¬A?A {A} ¬¬p =
  case LEM A of ?
    { (yes p) ? p
    ; (no ¬p) ? ?-elim $ ¬¬p ¬p
    }

然后你可以证明,对一个普遍陈述的否定暗示了一个存在主义的陈述:

¬??? : {A : Set} {B : A ? Set} ?
      ¬ (? a ? B a) ?
      ? ? a ? ¬ (B a)
¬??? {A} {B} ¬? = 
  case LEM (? ? a ? ¬ B a) of ?
    { (yes p) ? p
    ; (no ¬p) ? ?-elim $ ¬? (¬¬A?A ? ??? ¬p)
    }

所有正确进口的要点