[Agda] ℕ ⊆ P U Q -> ¬ isFinite P or ...

Sergei Meshveliani mechvel at botik.ru
Sat Oct 25 17:18:42 CEST 2014


People,

I have been asked about a constructive proof of this theorem:

  ℕ ⊆ P U Q -> (¬ isFinite P) ⊎ (¬ isFinite Q).


A subset in ℕ is defined as an algorithmic predicate  P : ℕ -> Set.

setℕ (total set),  _⊆_,  P,  _U_ (union)  
are defined in a natural way, via predicates.

Finiteness is defined as 

  _Enumerates_ : List ℕ → NSet → Set _
  xs Enumerates P =
                    {x : ℕ} → P x → x ∈ xs

  isFinite : NSet → Set _
  isFinite P =  ∃ \xs → xs Enumerates P


I have proved this in Agda:

 ⋃isFiniteIfBoth : {P Q : NSet} → isFinite P → isFinite Q → 
                                               isFinite (P ⋃ Q),

 theorem1 : {P Q : NSet} → setℕ ⊆ (P ⋃ Q) → ¬ (isFinite P × isFinite Q).


And I have an impression that the statement 

 question : {P Q : NSet} → setℕ ⊆ (P ⋃ Q) → 
                                       (¬ isFinite P) ⊎ (¬ isFinite Q)

has not a constructive proof.

Has it?

Thanks,

------
Sergei



More information about the Agda mailing list