1 (**************************************************************************)
4 (* ||A|| A project by Andrea Asperti *)
6 (* ||I|| Developers: *)
7 (* ||T|| A.Asperti, C.Sacerdoti Coen, *)
8 (* ||A|| E.Tassi, S.Zacchiroli *)
10 (* \ / This file is distributed under the terms of the *)
11 (* v GNU Lesser General Public License Version 2.1 *)
13 (**************************************************************************)
15 set "baseuri" "cic:/matita/logic/equality/".
17 include "higher_order_defs/relations.ma".
19 inductive eq (A:Type) (x:A) : A \to Prop \def
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)).
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.
35 (match p1 return \lambda y. \lambda p.P y p with
36 [refl_eq \Rightarrow p]).
39 variant reflexive_eq : \forall A:Type. reflexive A (eq A)
41 (* simplify.intros.apply refl_eq. *)
43 theorem symmetric_eq: \forall A:Type. symmetric A (eq A).
44 unfold symmetric.intros.elim H. apply refl_eq.
47 variant sym_eq : \forall A:Type.\forall x,y:A. x=y \to y=x
50 theorem transitive_eq : \forall A:Type. transitive A (eq A).
51 unfold transitive.intros.elim H1.assumption.
54 variant trans_eq : \forall A:Type.\forall x,y,z:A. x=y \to y=z \to x=z
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.
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.
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.
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.
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.
86 coercion cic:/matita/logic/equality/sym_eq.con.
87 coercion cic:/matita/logic/equality/eq_f.con.
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
102 cic:/matita/logic/equality/eq_OF_eq.con.
105 cic:/matita/logic/equality/eq_f'.con. (* \x.sym (eq_f x) *)
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.
119 eq_ind ? ? (\lambda a.a=y') eq2 ? eq1.
125 comp ? ? ? ? u u = refl_eq ? y.
127 apply (eq_rect' ? ? ? ? ? u).
133 \lambda H: \forall x,y:A. decidable (x=y).
134 \lambda x,y. \lambda p:x=y.
136 [ (or_introl p') \Rightarrow p'
137 | (or_intror K) \Rightarrow False_ind ? (K p) ].
141 \forall H: \forall x,y:A. decidable (x=y).
144 nu ? H ? ? u = nu ? H ? ? v.
147 unfold decidable in H.
148 apply (Or_ind' ? ? ? ? ? (H x y)); simplify.
153 definition nu_inv \def
155 \lambda H: \forall x,y:A. decidable (x=y).
158 comp ? ? ? ? (nu ? H ? ? (refl_eq ? x)) v.
162 \forall H: \forall x,y:A. decidable (x=y).
165 nu_inv ? H ? ? (nu ? H ? ? u) = u.
167 apply (eq_rect' ? ? ? ? ? u).
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.
177 rewrite < (nu_left_inv ? H ? ? p).
178 rewrite < (nu_left_inv ? H ? ? q).
179 elim (nu_constant ? H ? ? q).
183 (*CSC: alternative proof that does not pollute the environment with
184 technical lemmata. Unfortunately, it is a pain to do without proper
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.
192 (\lambda x,y. \lambda p:x=y.
194 [ (or_introl p') \Rightarrow p'
195 | (or_intror K) \Rightarrow False_ind ? (K p) ]).
198 eq_ind ? ? (\lambda z. z=y) (nu ? ? q) ? (nu ? ? (refl_eq ? x))
203 apply (eq_rect' ? ? ? ? ? q);
204 fold simplify (nu ? ? (refl_eq ? x)).
205 generalize in match (nu ? ? (refl_eq ? x)); intro.
208 (\lambda y. \lambda u.
209 eq_ind A x (\lambda a.a=y) u y u = refl_eq ? y)
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]
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]
224 [(or_introl p') \Rightarrow p'
225 |(or_intror K) \Rightarrow False_ind (x=x) (K (refl_eq A x))]))
227 intro; simplify; reflexivity.
228 intro q; elim (q (refl_eq ? x)).
233 theorem a:\forall x.x=x\land True.
238 exact (refl_eq Prop x);