helm/matita/library/logic/equality.ma

   1 (**************************************************************************)
   2 (*       ___                                                                *)
   3 (*      ||M||                                                             *)
   4 (*      ||A||       A project by Andrea Asperti                           *)
   5 (*      ||T||                                                             *)
   6 (*      ||I||       Developers:                                           *)
   7 (*      ||T||       A.Asperti, C.Sacerdoti Coen,                          *)
   8 (*      ||A||       E.Tassi, S.Zacchiroli                                 *)
   9 (*      \   /                                                             *)
  10 (*       \ /        This file is distributed under the terms of the       *)
  11 (*        v         GNU Lesser General Public License Version 2.1         *)
  12 (*                                                                        *)
  13 (**************************************************************************)
  14
  15 set "baseuri" "cic:/matita/logic/equality/".
  16
  17 include "higher_order_defs/relations.ma".
  18
  19 inductive eq (A:Type) (x:A) : A \to Prop \def
  20     refl_eq : eq A x x.
  21
  22 (*CSC: the URI must disappear: there is a bug now *)
  23 interpretation "leibnitz's equality"
  24    'eq x y = (cic:/matita/logic/equality/eq.ind#xpointer(1/1) _ x y).
  25 (*CSC: the URI must disappear: there is a bug now *)
  26 interpretation "leibnitz's non-equality"
  27   'neq x y = (cic:/matita/logic/connectives/Not.con
  28     (cic:/matita/logic/equality/eq.ind#xpointer(1/1) _ x y)).
  29
  30 theorem eq_ind':
  31  \forall A. \forall x:A. \forall P: \forall y:A. x=y \to Prop.
  32   P ? (refl_eq ? x) \to \forall y:A. \forall p:x=y. P y p.
  33  intros.
  34  exact
  35   ([\lambda y:A. \lambda p:eq A x y.P y p]
  36    match p with
  37     [refl_eq \Rightarrow H]).
  38 qed.
  39
  40 theorem reflexive_eq : \forall A:Type. reflexive A (eq A).
  41 simplify.intros.apply refl_eq.
  42 qed.
  43
  44 theorem symmetric_eq: \forall A:Type. symmetric A (eq A).
  45 simplify.intros.elim H. apply refl_eq.
  46 qed.
  47
  48 theorem sym_eq : \forall A:Type.\forall x,y:A. x=y  \to y=x
  49 \def symmetric_eq.
  50
  51 theorem transitive_eq : \forall A:Type. transitive A (eq A).
  52 simplify.intros.elim H1.assumption.
  53 qed.
  54
  55 theorem trans_eq : \forall A:Type.\forall x,y,z:A. x=y  \to y=z \to x=z
  56 \def transitive_eq.
  57
  58 theorem eq_elim_r:
  59  \forall A:Type.\forall x:A. \forall P: A \to Prop.
  60    P x \to \forall y:A. y=x \to P y.
  61 intros. elim (sym_eq ? ? ? H1).assumption.
  62 qed.
  63
  64 default "equality"
  65  cic:/matita/logic/equality/eq.ind
  66  cic:/matita/logic/equality/sym_eq.con
  67  cic:/matita/logic/equality/trans_eq.con
  68  cic:/matita/logic/equality/eq_ind.con
  69  cic:/matita/logic/equality/eq_elim_r.con.
  70
  71 theorem eq_f: \forall  A,B:Type.\forall f:A\to B.
  72 \forall x,y:A. x=y \to f x = f y.
  73 intros.elim H.reflexivity.
  74 qed.
  75
  76 theorem eq_f2: \forall  A,B,C:Type.\forall f:A\to B \to C.
  77 \forall x1,x2:A. \forall y1,y2:B.
  78 x1=x2 \to y1=y2 \to f x1 y1 = f x2 y2.
  79 intros.elim H1.elim H.reflexivity.
  80 qed.
  81
  82 definition comp \def
  83  \lambda A.
  84   \lambda x,y,y':A.
  85    \lambda eq1:x=y.
  86     \lambda eq2:x=y'.
  87      eq_ind ? ? (\lambda a.a=y') eq2 ? eq1.
  88
  89 lemma trans_sym_eq:
  90  \forall A.
  91   \forall x,y:A.
  92    \forall u:x=y.
  93     comp ? ? ? ? u u = refl_eq ? y.
  94  intros.
  95  apply (eq_ind' ? ? ? ? ? u).
  96  reflexivity.
  97 qed.
  98
  99 definition nu \def
 100  \lambda A.
 101   \lambda H: \forall x,y:A. decidable (x=y).
 102    \lambda x,y. \lambda p:x=y.
 103      match H x y with
 104       [ (or_introl p') \Rightarrow p'
 105       | (or_intror K) \Rightarrow False_ind ? (K p) ].
 106
 107 theorem nu_constant:
 108  \forall A.
 109   \forall H: \forall x,y:A. decidable (x=y).
 110    \forall x,y:A.
 111     \forall u,v:x=y.
 112      nu ? H ? ? u = nu ? H ? ? v.
 113  intros.
 114  unfold nu.
 115  unfold decidable in H.
 116  apply (Or_ind' ? ? ? ? ? (H x y)); simplify.
 117   intro; reflexivity.
 118   intro; elim (q u).
 119 qed.
 120
 121 definition nu_inv \def
 122  \lambda A.
 123   \lambda H: \forall x,y:A. decidable (x=y).
 124    \lambda x,y:A.
 125     \lambda v:x=y.
 126      comp ? ? ? ? (nu ? H ? ? (refl_eq ? x)) v.
 127
 128 theorem nu_left_inv:
 129  \forall A.
 130   \forall H: \forall x,y:A. decidable (x=y).
 131    \forall x,y:A.
 132     \forall u:x=y.
 133      nu_inv ? H ? ? (nu ? H ? ? u) = u.
 134  intros.
 135  apply (eq_ind' ? ? ? ? ? u).
 136  unfold nu_inv.
 137  apply trans_sym_eq.
 138 qed.
 139
 140 theorem eq_to_eq_to_eq_p_q:
 141  \forall A. \forall x,y:A.
 142   (\forall x,y:A. decidable (x=y)) \to
 143    \forall p,q:x=y. p=q.
 144  intros.
 145  rewrite < (nu_left_inv ? H ? ? p).
 146  rewrite < (nu_left_inv ? H ? ? q).
 147  elim (nu_constant ? H ? ? q).
 148  reflexivity.
 149 qed.
 150
 151 (*CSC: alternative proof that does not pollute the environment with
 152   technical lemmata. Unfortunately, it is a pain to do without proper
 153   support for let-ins.
 154 theorem eq_to_eq_to_eq_p_q:
 155  \forall A. \forall x,y:A.
 156   (\forall x,y:A. decidable (x=y)) \to
 157    \forall p,q:x=y. p=q.
 158 intros.
 159 letin nu \def
 160  (\lambda x,y. \lambda p:x=y.
 161    match H x y with
 162     [ (or_introl p') \Rightarrow p'
 163     | (or_intror K) \Rightarrow False_ind ? (K p) ]).
 164 cut
 165  (\forall q:x=y.
 166    eq_ind ? ? (\lambda z. z=y) (nu ? ? q) ? (nu ? ? (refl_eq ? x))
 167    = q).
 168 focus 8.
 169  clear q; clear p.
 170  intro.
 171  apply (eq_ind' ? ? ? ? ? q);
 172  fold simplify (nu ? ? (refl_eq ? x)).
 173  generalize in match (nu ? ? (refl_eq ? x)); intro.
 174  apply
 175   (eq_ind' A x
 176    (\lambda y. \lambda u.
 177     eq_ind A x (\lambda a.a=y) u y u = refl_eq ? y)
 178    ? x H1).
 179  reflexivity.
 180 unfocus.
 181 rewrite < (Hcut p); fold simplify (nu ? ? p).
 182 rewrite < (Hcut q); fold simplify (nu ? ? q).
 183 apply (Or_ind' (x=x) (x \neq x)
 184  (\lambda p:decidable (x=x). eq_ind A x (\lambda z.z=y) (nu x y p) x
 185    ([\lambda H1.eq A x x]
 186     match p with
 187     [(or_introl p') \Rightarrow p'
 188     |(or_intror K) \Rightarrow False_ind (x=x) (K (refl_eq A x))]) =
 189    eq_ind A x (\lambda z.z=y) (nu x y q) x
 190     ([\lambda H1.eq A x x]
 191      match p with
 192     [(or_introl p') \Rightarrow p'
 193     |(or_intror K) \Rightarrow False_ind (x=x) (K (refl_eq A x))]))
 194  ? ? (H x x)).
 195 intro; simplify; reflexivity.
 196 intro q; elim (q (refl_eq ? x)).
 197 qed.
 198 *)
 199
 200 (*
 201 theorem a:\forall x.x=x\land True.
 202 [
 203 2:intros;
 204   split;
 205   [
 206     exact (refl_eq Prop x);
 207   |
 208     exact I;
 209   ]
 210 1:
 211   skip
 212 ]
 213 qed.
 214 *)
 215