如何在阿格达(Ada)中证明“定理¬≡⊥”?

通往逻辑,数学和编程的Haskell之路之后,您可以找到第48页定理2.12.1 ¬ ⊤ ≡ ⊥及其反义词{{1} }

这本书使用Haskell并假设

  1. ¬ ⊥ ≡ ⊤
  2. ⊥ = False

这将产生Agda类型⊤ = True,通过theorem : (p q : Bool) → not p ≡ q进行证明很简单。

但是,在不假设1和2的情况下可以证明原始定理吗?

尝试

refl

由于我们无法构造-- from software foundations (https://plfa.github.io/Negation/) postulate excluded-middle : ∀ {A : Set} → A ⊎ ¬ A theorem : ¬ ⊤ ≡ ⊥ theorem x = {!!} ,因此当然不会产生任何解决方案,所以我猜需要矛盾的证明吗?另外,我是否正确地假设这假设了排除中间的定律,因此这是附加的假设?

阿格达说:

  

我不确定构造函数refl是否应该有这种情况,   因为在尝试解决以下统一问题时我被卡住了   问题(推断索引≟预期索引):     ⊥   在检查表达式时?的类型为⊥

谢谢!

vorlor 回答:如何在阿格达(Ada)中证明“定理¬≡⊥”?

这在纯属Agda中可证明,没有任何假设。解决方案是⊤ ≡ ⊥允许我们将的任何证明转换为的证明。

open import Data.Unit
open import Data.Empty
open import Relation.Binary.PropositionalEquality
open import Relation.Nullary

theorem : ¬ (⊤ ≡ ⊥)
theorem eq = subst (λ A → A) eq tt
,

如果¬ ⊤ ≡ ⊥¬ (⊤ ≡ ⊥),则@Andras Kovacs为¬ ⊤ ≡ ⊥¬ ⊥ ≡ ⊤都回答问题。如果¬ ⊤ ≡ ⊥(¬ ⊤) ≡ ⊥,则证明要求类型相等。通常,只要证明¬ ⊤之间存在同构,就可以了。

(¬ ⊤) ≡ ⊥的证明表明¬ ⊤没有人居住。

然后,(¬ ⊥) ≡ ⊤的证明基本上证明了¬ ⊥仅具有一个功能id(因此对于包含单个元素的所有类型都是同构的)。

以下所有这些都可以使用一些标准的Agda函数来构造,但是这里需要证明这些同构的存在的自给自足的定义。注意FalseTrue是类型,而不是布尔值。另外,由于¬ ⊥是一个函数,因此需要扩展性公理才能证明第二个定理。

data False : Set where

data True : Set where
  tt : True

data _==_ {A : Set} (x : A) : A -> Set where
   refl : x == x

false-elim : {A : Set} -> False -> A
false-elim ()

id : {A : Set} -> A -> A
id x = x

const : {A B : Set} -> B -> A -> B
const x _ = x

ap : {A B : Set} -> (A -> B) -> A -> B
ap = id

ap' : {A B : Set} -> A -> (A -> B) -> B
ap' x f = f x

infixl 4 _==_

data Isomorphism {A B : Set} (f : A -> B) (g : B -> A) : Set where
   iso : ((x : B) -> f (g x) == id x) ->
         ((x : A) -> g (f x) == id x) -> Isomorphism f g

Not : Set -> Set
Not A = A -> False

not-True-iso-False : Isomorphism (ap' tt) false-elim
not-True-iso-False = iso (\x -> false-elim {ap' tt (false-elim x) == id x} x)
                         \not-true -> false-elim (not-true tt)

-- extensionality: if functions produce equal results for all inputs,then the functions are equal
postulate ext : {A B : Set} -> (f g : A -> B) -> ((x : A) -> f x == g x) -> f == g

not-False-iso-True : Isomorphism {Not False} {True} (const tt) (const id)
not-False-iso-True = iso is-true is-not-false where
   is-true : (x : True) -> const tt (const {True} (id {Not False})) == id x
   is-true tt = refl
   is-not-false : (x : Not False) -> const id (const {Not False} tt) == id x
   is-not-false x = ext (const id (const {Not False} tt)) x \()

现在,如果我们为任意级别的类型Universe定义_==_,则可以引入有关类型相等的公理:如果两个类型具有同构性,则它们相等。

open import Agda.Primitive
data _==_ {a : Level} {A : Set a} (x : A) : A -> Set a where
   refl : x == x

postulate iso-is-eq : {A B : Set} {f : A -> B} {g : B -> A} ->
                      Isomorphism f g -> A == B

not-True-is-False : (Not True) == False
not-True-is-False = iso-is-eq not-True-iso-False

not-False-is-True : (Not False) == True
not-False-is-True = iso-is-eq not-False-iso-True
本文链接:https://www.f2er.com/3084127.html

大家都在问