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 "datatypes/subsets.ma".
  16
  17 record axiom_set : Type ≝ {
  18   A:> Type;
  19   i: A → Type;
  20   C: ∀a:A. i a → Ω \sup A
  21 }.
  22
  23 inductive for_all (A: axiom_set) (U,V: Ω \sup A) (covers: A → CProp) : CProp ≝
  24    iter: (∀a:A.a ∈ V → covers a) → for_all A U V covers.
  25
  26 inductive covers (A: axiom_set) (U: \Omega \sup A) : A → CProp ≝
  27    refl: ∀a:A. a ∈ U → covers A U a
  28  | infinity: ∀a:A. ∀j: i ? a. for_all A U (C ? a j) (covers A U) → covers A U a.
  29
  30 notation "hvbox(a break ◃ b)" non associative with precedence 45
  31 for @{ 'covers $a $b }. (* a \ltri b *)
  32
  33 interpretation "coversl" 'covers A U = (for_all _ U A (covers _ U)).
  34 interpretation "covers" 'covers a U = (covers _ U a).
  35
  36 definition covers_elim ≝
  37  λA:axiom_set.λU: \Omega \sup A.λP:\Omega \sup A.
  38   λH1: U ⊆ P.
  39    λH2:∀a:A.∀j:i ? a. C ? a j ◃ U → C ? a j ⊆ P → a ∈ P.
  40     let rec aux (a:A) (p:a ◃ U) on p : a ∈ P ≝
  41      match p return λaa.λ_:aa ◃ U.aa ∈ P with
  42       [ refl a q ⇒ H1 a q
  43       | infinity a j q ⇒
  44          H2 a j q
  45           match q return λ_:(C ? a j) ◃ U. C ? a j ⊆ P with
  46           [ iter f ⇒ λb.λr. aux b (f b r) ]]
  47     in
  48      aux.
  49
  50 inductive ex_such (A : axiom_set) (U,V : \Omega \sup A) (fish: A → CProp) : CProp ≝
  51  found : ∀a. a ∈ V → fish a → ex_such A U V fish.
  52
  53 coinductive fish (A:axiom_set) (U: \Omega \sup A) : A → CProp ≝
  54  mk_fish: ∀a:A. a ∈ U → (∀j: i ? a. ex_such A U (C ? a j) (fish A U)) → fish A U a.
  55
  56 notation "hvbox(a break ⋉ b)" non associative with precedence 45
  57 for @{ 'fish $a $b }. (* a \ltimes b *)
  58
  59 interpretation "fishl" 'fish A U = (ex_such _ U A (fish _ U)).
  60 interpretation "fish" 'fish a U = (fish _ U a).
  61
  62 let corec fish_rec (A:axiom_set) (U: \Omega \sup A)
  63  (P: Ω \sup A) (H1: P ⊆ U)
  64   (H2: ∀a:A. a ∈ P → ∀j: i ? a. C ? a j ≬ P):
  65    ∀a:A. ∀p: a ∈ P. a ⋉ U ≝
  66  λa,p.
  67   mk_fish A U a
  68    (H1 ? p)
  69    (λj: i ? a.
  70     match H2 a p j with
  71      [ ex_introT2 (y: A) (HyC : y ∈ C ? a j) (HyP : y ∈ P) ⇒
  72          found ???? y HyC (fish_rec A U P H1 H2 y HyP)
  73      ]).
  74
  75 theorem reflexivity: ∀A:axiom_set.∀a:A.∀V. a ∈ V → a ◃ V.
  76  intros;
  77  apply refl;
  78  assumption.
  79 qed.
  80
  81 theorem transitivity: ∀A:axiom_set.∀a:A.∀U,V. a ◃ U → U ◃ V → a ◃ V.
  82  intros;
  83  apply (covers_elim ?? {a | a ◃ V} ??? H); simplify; intros;
  84   [ cases H1 in H2; apply H2;
  85   | apply infinity;
  86      [ assumption
  87      | constructor 1;
  88        assumption]]
  89 qed.
  90
  91 theorem coreflexivity: ∀A:axiom_set.∀a:A.∀V. a ⋉ V → a ∈ V.
  92  intros;
  93  cases H;
  94  assumption.
  95 qed.
  96
  97 theorem cotransitivity:
  98  ∀A:axiom_set.∀a:A.∀U,V. a ⋉ U → (∀b:A. b ⋉ U → b ∈ V) → a ⋉ V.
  99  intros;
 100  apply (fish_rec ?? {a|a ⋉ U} ??? H); simplify; intros;
 101   [ apply H1; apply H2;
 102   | cases H2 in j; clear H2; intro i;
 103     cases (H4 i); clear H4; exists[apply a3] assumption]
 104 qed.
 105
 106 theorem compatibility: ∀A:axiom_set.∀a:A.∀U,V. a ⋉ V → a ◃ U → U ⋉ V.
 107  intros;
 108  generalize in match H; clear H;
 109  apply (covers_elim ?? {a|a ⋉ V → U ⋉ V} ??? H1);
 110  clear H1; simplify; intros;
 111   [ exists [apply a1] assumption
 112   | cases H2 in j H H1; clear H2 a1; intros;
 113     cases (H1 i); clear H1; apply (H3 a1); assumption]
 114 qed.
 115
 116 definition leq ≝ λA:axiom_set.λa,b:A. a ◃ {b}.
 117
 118 interpretation "covered by one" 'leq a b = (leq _ a b).
 119
 120 theorem leq_refl: ∀A:axiom_set.∀a:A. a ≤ a.
 121  intros;
 122  apply refl;
 123  normalize;
 124  reflexivity.
 125 qed.
 126
 127 theorem leq_trans: ∀A:axiom_set.∀a,b,c:A. a ≤ b → b ≤ c → a ≤ c.
 128  intros;
 129  unfold in H H1 ⊢ %;
 130  apply (transitivity ???? H);
 131  constructor 1;
 132  intros;
 133  normalize in H2;
 134  rewrite < H2;
 135  assumption.
 136 qed.
 137
 138 definition uparrow ≝ λA:axiom_set.λa:A.mk_powerset ? (λb:A. a ≤ b).
 139
 140 notation "↑a" with precedence 80 for @{ 'uparrow $a }.
 141
 142 interpretation "uparrow" 'uparrow a = (uparrow _ a).
 143
 144 definition downarrow ≝ λA:axiom_set.λU:Ω \sup A.mk_powerset ? (λa:A. ↑a ≬ U).
 145
 146 notation "↓a" with precedence 80 for @{ 'downarrow $a }.
 147
 148 interpretation "downarrow" 'downarrow a = (downarrow _ a).
 149
 150 definition fintersects ≝ λA:axiom_set.λU,V:Ω \sup A.↓U ∩ ↓V.
 151
 152 interpretation "fintersects" 'fintersects U V = (fintersects _ U V).
 153
 154 record convergent_generated_topology : Type ≝
 155  { AA:> axiom_set;
 156    convergence: ∀a:AA.∀U,V:Ω \sup AA. a ◃ U → a ◃ V → a ◃ U ↓ V
 157  }.
 158