[Agda] not-all -> any-not

Sergei Meshveliani mechvel at botik.ru
Thu Oct 24 19:54:46 CEST 2013


People,
I write

  ¬all→any¬ : {A : Set} {P : A → Set} {P? : Decidable P} {xs : List A} →
                                      (¬ All P xs) → (Any (¬_ ∘ P) xs)

and think:  is this provable without using  Decidable ?

I tried a singleton list for a counter example. But here is the proof: 

 ¬all→P1 : {A : Set} {P : A → Set} {x : A} → (¬ All P (x ∷ [])) → ¬ P x
 ¬all→P1 ¬all-x Px =  ¬all-x (Px ∷a []a)

([]a, _∷a_  imported from  Data.List.All  as renamed [], _∷_).

May be   x ∷ y ∷ []   is a counter example?


And  ¬all→any¬  I implement as

  ¬all→any¬              {xs = []}     ¬all[]     =  ⊥-elim $ ¬all[] []a

  ¬all→any¬ {P = P} {P? = P?} {xs = x ∷ ys} ¬all-x:ys  with P? x
  ...      |
             no ¬Px = here ¬Px
  ...      | yes Px = 
                 there $ ¬all→any¬ {P = P} {P? = P?} {xs = ys} ¬all-ys
                              where
                              ¬all-ys : ¬ All P ys
                              ¬all-ys all-ys = ¬all-x:ys (Px ∷a all-ys)


Thank you in advance for explanation,

------
Sergei



More information about the Agda mailing list