helm/software/matita/library/demo/formal_topology.ma

   1 (**************************************************************************)
   2 (*       ___                                                              *)
   3 (*      ||M||                                                             *)
   4 (*      ||A||       A project by Andrea Asperti                           *)
   5 (*      ||T||                                                             *)
   6 (*      ||I||       Developers:                                           *)
   7 (*      ||T||         The HELM team.                                      *)
   8 (*      ||A||         http://helm.cs.unibo.it                             *)
   9 (*      \   /                                                             *)
  10 (*       \ /        This file is distributed under the terms of the       *)
  11 (*        v         GNU General Public License Version 2                  *)
  12 (*                                                                        *)
  13 (**************************************************************************)
  14
  15 include "logic/equality.ma".
  16
  17 inductive And (A,B:CProp) : CProp ≝
  18  conj: A → B → And A B.
  19
  20 interpretation "constructive and" 'and x y = (And x y).
  21
  22 inductive exT (A:Type) (P:A→CProp) : CProp ≝
  23   ex_introT: ∀w:A. P w → exT A P.
  24
  25 interpretation "CProp exists" 'exists \eta.x = (exT _ x).
  26
  27 record powerset (A: Type) : Type ≝ { char: A → CProp }.
  28
  29 notation "hvbox(2 \sup A)" non associative with precedence 45
  30 for @{ 'powerset $A }.
  31
  32 interpretation "powerset" 'powerset A = (powerset A).
  33
  34 definition mem ≝ λA.λS:2 \sup A.λx:A. match S with [mk_powerset c ⇒ c x].
  35
  36 notation "hvbox(a break ∈ b)" non associative with precedence 45
  37 for @{ 'mem $a $b }.
  38
  39 interpretation "mem" 'mem a S = (mem _ S a).
  40
  41 record axiom_set : Type ≝
  42  { A:> Type;
  43    i: A → Type;
  44    C: ∀a:A. i a → 2 \sup A
  45  }.
  46
  47 inductive covers (A: axiom_set) (U: 2 \sup A) : A → CProp ≝
  48    refl: ∀a:A. a ∈ U → covers A U a
  49  | infinity: ∀a:A. ∀j: i ? a. coversl A U (C ? a j) → covers A U a
  50 with coversl : (2 \sup A) → CProp ≝
  51    iter: ∀V:2 \sup A.(∀a:A.a ∈ V → covers A U a) → coversl A U V.
  52
  53 notation "hvbox(a break ◃ b)" non associative with precedence 45
  54 for @{ 'covers $a $b }.
  55
  56 interpretation "coversl" 'covers A U = (coversl _ U A).
  57 interpretation "covers" 'covers a U = (covers _ U a).
  58
  59 definition covers_elim ≝
  60  λA:axiom_set.λU: 2 \sup A.λP:2 \sup A.
  61   λH1:∀a:A. a ∈ U → a ∈ P.
  62    λH2:∀a:A.∀j:i ? a. C ? a j ◃ U → (∀b. b ∈ C ? a j → b ∈ P) → a ∈ P.
  63     let rec aux (a:A) (p:a ◃ U) on p : a ∈ P ≝
  64      match p return λaa.λ_:aa ◃ U.aa ∈ P with
  65       [ refl a q ⇒ H1 a q
  66       | infinity a j q ⇒ H2 a j q (auxl (C ? a j) q)
  67       ]
  68     and auxl (V: 2 \sup A) (q: V ◃ U) on q : ∀b. b ∈ V → b ∈ P ≝
  69      match q return λVV.λ_:VV ◃ U.∀b. b ∈ VV → b ∈ P with
  70       [ iter VV f ⇒ λb.λr. aux b (f b r) ]
  71     in
  72      aux.
  73
  74 coinductive fish (A:axiom_set) (U: 2 \sup A) : A → CProp ≝
  75  mk_fish: ∀a:A. (a ∈ U ∧ ∀j: i ? a. ∃y: A. y ∈ C ? a j ∧ fish A U y) → fish A U a.
  76 definition fishl ≝ λA:axiom_set.λU:2 \sup A.λV:2 \sup A. ∃a. a ∈ V ∧ fish ? U a.
  77
  78 notation "hvbox(a break ⋉ b)" non associative with precedence 45
  79 for @{ 'fish $a $b }.
  80
  81 interpretation "fishl" 'fish A U = (fishl _ U A).
  82 interpretation "fish" 'fish a U = (fish _ U a).
  83
  84 let corec fish_rec (A:axiom_set) (U: 2 \sup A)
  85  (P: 2 \sup A) (H1: ∀a:A. a ∈ P → a ∈ U)
  86   (H2: ∀a:A. a ∈ P → ∀j: i ? a. ∃y: A. y ∈ C ? a j ∧ y ∈ P) :
  87    ∀a:A. ∀p: a ∈ P. a ⋉ U ≝
  88  λa,p.
  89   mk_fish A U a
  90    (conj ? ? (H1 ? p)
  91    (λj: i ? a.
  92     match H2 a p j with
  93      [ ex_introT (y: A) (Ha: y ∈ C ? a j ∧ y ∈ P) ⇒
  94         match Ha with
  95          [ conj (fHa: y ∈ C ? a j) (sHa: y ∈ P) ⇒
  96             ex_introT A (λy.y ∈ C ? a j ∧ fish A U y) y
  97              (conj ? ? fHa (fish_rec A U P H1 H2 y sHa))
  98          ]
  99      ])).
 100
 101 theorem reflexivity: ∀A:axiom_set.∀a:A.∀V. a ∈ V → a ◃ V.
 102  intros;
 103  apply refl;
 104  assumption.
 105 qed.
 106
 107 theorem transitivity: ∀A:axiom_set.∀a:A.∀U,V. a ◃ U → U ◃ V → a ◃ V.
 108  intros;
 109  apply (covers_elim ?? (mk_powerset A (λa.a ◃ V)) ??? H); simplify; intros;
 110   [ cases H1 in H2;
 111     intro;
 112     apply H2;
 113     assumption
 114   | apply infinity;
 115      [ assumption
 116      | constructor 1;
 117        assumption]]
 118 qed.
 119
 120 theorem coreflexivity: ∀A:axiom_set.∀a:A.∀V. a ⋉ V → a ∈ V.
 121  intros;
 122  cases H;
 123  cases H1;
 124  assumption.
 125 qed.
 126
 127 theorem cotransitivity:
 128  ∀A:axiom_set.∀a:A.∀U,V. a ⋉ U → (∀b:A. b ⋉ U → b ∈ V) → a ⋉ V.
 129  intros;
 130  apply (fish_rec ?? (mk_powerset A (λa.a ⋉ U)) ??? H); simplify; intros;
 131   [ apply H1;
 132     assumption
 133   | cases H2 in j; clear H2; cases H3; clear H3;
 134     assumption]
 135 qed.
 136
 137 theorem compatibility: ∀A:axiom_set.∀a:A.∀U,V. a ⋉ V → a ◃ U → U ⋉ V.
 138  intros;
 139  generalize in match H; clear H; generalize in match V; clear V;
 140  apply (covers_elim ?? (mk_powerset A (λa.∀p:2 \sup A.a ⋉ p → U ⋉ p)) ??? H1);
 141  clear H1; simplify; intros;
 142   [ exists [apply a1]
 143     split;
 144     assumption
 145   | cases H2 in j H H1; clear H2 a1; intros;
 146     cases H; clear H;
 147     cases (H4 i); clear H4; cases H; clear H;
 148     apply (H2 w); clear H2;
 149     assumption]
 150 qed.