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_rect':
  31  \forall A. \forall x:A. \forall P: \forall y:A. x=y \to Type.
  32   P ? (refl_eq ? x) \to \forall y:A. \forall p:x=y. P y p.
  33  intros.
  34  exact
  35   (match p1 return \lambda y. \lambda p.P y p with
  36     [refl_eq \Rightarrow p]).
  37 qed.
  38
  39 variant reflexive_eq : \forall A:Type. reflexive A (eq A)
  40 \def refl_eq.
  41 (* simplify.intros.apply refl_eq. *)
  42
  43 theorem symmetric_eq: \forall A:Type. symmetric A (eq A).
  44 unfold symmetric.intros.elim H. apply refl_eq.
  45 qed.
  46
  47 variant sym_eq : \forall A:Type.\forall x,y:A. x=y  \to y=x
  48 \def symmetric_eq.
  49
  50 theorem transitive_eq : \forall A:Type. transitive A (eq A).
  51 unfold transitive.intros.elim H1.assumption.
  52 qed.
  53
  54 variant trans_eq : \forall A:Type.\forall x,y,z:A. x=y  \to y=z \to x=z
  55 \def transitive_eq.
  56
  57 theorem eq_elim_r:
  58  \forall A:Type.\forall x:A. \forall P: A \to Prop.
  59    P x \to \forall y:A. y=x \to P y.
  60 intros. elim (sym_eq ? ? ? H1).assumption.
  61 qed.
  62
  63 theorem eq_elim_r':
  64  \forall A:Type.\forall x:A. \forall P: A \to Set.
  65    P x \to \forall y:A. y=x \to P y.
  66 intros. elim (sym_eq ? ? ? H).assumption.
  67 qed.
  68
  69 theorem eq_elim_r'':
  70  \forall A:Type.\forall x:A. \forall P: A \to Type.
  71    P x \to \forall y:A. y=x \to P y.
  72 intros. elim (sym_eq ? ? ? H).assumption.
  73 qed.
  74
  75 theorem eq_f: \forall  A,B:Type.\forall f:A\to B.
  76 \forall x,y:A. x=y \to f x = f y.
  77 intros.elim H.apply refl_eq.
  78 qed.
  79
  80 theorem eq_f': \forall  A,B:Type.\forall f:A\to B.
  81 \forall x,y:A. x=y \to f y = f x.
  82 intros.elim H.apply refl_eq.
  83 qed.
  84
  85 (*  *)
  86 coercion cic:/matita/logic/equality/sym_eq.con.
  87 coercion cic:/matita/logic/equality/eq_f.con.
  88 (* *)
  89
  90 default "equality"
  91  cic:/matita/logic/equality/eq.ind
  92  cic:/matita/logic/equality/sym_eq.con
  93  cic:/matita/logic/equality/transitive_eq.con
  94  cic:/matita/logic/equality/eq_ind.con
  95  cic:/matita/logic/equality/eq_elim_r.con
  96  cic:/matita/logic/equality/eq_rec.con
  97  cic:/matita/logic/equality/eq_elim_r'.con
  98  cic:/matita/logic/equality/eq_rect.con
  99  cic:/matita/logic/equality/eq_elim_r''.con
 100  cic:/matita/logic/equality/eq_f.con
 101 (* *)
 102  cic:/matita/logic/equality/eq_OF_eq.con.
 103 (* *)
 104 (*
 105  cic:/matita/logic/equality/eq_f'.con. (* \x.sym (eq_f x) *)
 106  *)
 107
 108 theorem eq_f2: \forall  A,B,C:Type.\forall f:A\to B \to C.
 109 \forall x1,x2:A. \forall y1,y2:B.
 110 x1=x2 \to y1=y2 \to f x1 y1 = f x2 y2.
 111 intros.elim H1.elim H.reflexivity.
 112 qed.
 113
 114 definition comp \def
 115  \lambda A.
 116   \lambda x,y,y':A.
 117    \lambda eq1:x=y.
 118     \lambda eq2:x=y'.
 119      eq_ind ? ? (\lambda a.a=y') eq2 ? eq1.
 120
 121 lemma trans_sym_eq:
 122  \forall A.
 123   \forall x,y:A.
 124    \forall u:x=y.
 125     comp ? ? ? ? u u = refl_eq ? y.
 126  intros.
 127  apply (eq_rect' ? ? ? ? ? u).
 128  reflexivity.
 129 qed.
 130
 131 definition nu \def
 132  \lambda A.
 133   \lambda H: \forall x,y:A. decidable (x=y).
 134    \lambda x,y. \lambda p:x=y.
 135      match H x y with
 136       [ (or_introl p') \Rightarrow p'
 137       | (or_intror K) \Rightarrow False_ind ? (K p) ].
 138
 139 theorem nu_constant:
 140  \forall A.
 141   \forall H: \forall x,y:A. decidable (x=y).
 142    \forall x,y:A.
 143     \forall u,v:x=y.
 144      nu ? H ? ? u = nu ? H ? ? v.
 145  intros.
 146  unfold nu.
 147  unfold decidable in H.
 148  apply (Or_ind' ? ? ? ? ? (H x y)); simplify.
 149   intro; reflexivity.
 150   intro; elim (q u).
 151 qed.
 152
 153 definition nu_inv \def
 154  \lambda A.
 155   \lambda H: \forall x,y:A. decidable (x=y).
 156    \lambda x,y:A.
 157     \lambda v:x=y.
 158      comp ? ? ? ? (nu ? H ? ? (refl_eq ? x)) v.
 159
 160 theorem nu_left_inv:
 161  \forall A.
 162   \forall H: \forall x,y:A. decidable (x=y).
 163    \forall x,y:A.
 164     \forall u:x=y.
 165      nu_inv ? H ? ? (nu ? H ? ? u) = u.
 166  intros.
 167  apply (eq_rect' ? ? ? ? ? u).
 168  unfold nu_inv.
 169  apply trans_sym_eq.
 170 qed.
 171
 172 theorem eq_to_eq_to_eq_p_q:
 173  \forall A. \forall x,y:A.
 174   (\forall x,y:A. decidable (x=y)) \to
 175    \forall p,q:x=y. p=q.
 176  intros.
 177  rewrite < (nu_left_inv ? H ? ? p).
 178  rewrite < (nu_left_inv ? H ? ? q).
 179  elim (nu_constant ? H ? ? q).
 180  reflexivity.
 181 qed.
 182
 183 (*CSC: alternative proof that does not pollute the environment with
 184   technical lemmata. Unfortunately, it is a pain to do without proper
 185   support for let-ins.
 186 theorem eq_to_eq_to_eq_p_q:
 187  \forall A. \forall x,y:A.
 188   (\forall x,y:A. decidable (x=y)) \to
 189    \forall p,q:x=y. p=q.
 190 intros.
 191 letin nu \def
 192  (\lambda x,y. \lambda p:x=y.
 193    match H x y with
 194     [ (or_introl p') \Rightarrow p'
 195     | (or_intror K) \Rightarrow False_ind ? (K p) ]).
 196 cut
 197  (\forall q:x=y.
 198    eq_ind ? ? (\lambda z. z=y) (nu ? ? q) ? (nu ? ? (refl_eq ? x))
 199    = q).
 200 focus 8.
 201  clear q; clear p.
 202  intro.
 203  apply (eq_rect' ? ? ? ? ? q);
 204  fold simplify (nu ? ? (refl_eq ? x)).
 205  generalize in match (nu ? ? (refl_eq ? x)); intro.
 206  apply
 207   (eq_rect' A x
 208    (\lambda y. \lambda u.
 209     eq_ind A x (\lambda a.a=y) u y u = refl_eq ? y)
 210    ? x H1).
 211  reflexivity.
 212 unfocus.
 213 rewrite < (Hcut p); fold simplify (nu ? ? p).
 214 rewrite < (Hcut q); fold simplify (nu ? ? q).
 215 apply (Or_ind' (x=x) (x \neq x)
 216  (\lambda p:decidable (x=x). eq_ind A x (\lambda z.z=y) (nu x y p) x
 217    ([\lambda H1.eq A x x]
 218     match p with
 219     [(or_introl p') \Rightarrow p'
 220     |(or_intror K) \Rightarrow False_ind (x=x) (K (refl_eq A x))]) =
 221    eq_ind A x (\lambda z.z=y) (nu x y q) x
 222     ([\lambda H1.eq A x x]
 223      match p with
 224     [(or_introl p') \Rightarrow p'
 225     |(or_intror K) \Rightarrow False_ind (x=x) (K (refl_eq A x))]))
 226  ? ? (H x x)).
 227 intro; simplify; reflexivity.
 228 intro q; elim (q (refl_eq ? x)).
 229 qed.
 230 *)
 231
 232 (*
 233 theorem a:\forall x.x=x\land True.
 234 [
 235 2:intros;
 236   split;
 237   [
 238     exact (refl_eq Prop x);
 239   |
 240     exact I;
 241   ]
 242 1:
 243   skip
 244 ]
 245 qed.
 246 *)
 247