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 include "logic/pts.ma".
17 ninductive peq (A:Type[3]) (x:A) : A \to Prop \def
20 interpretation "leibnitz's equality" 'eq t x y = (peq t x y).
22 ntheorem rewrite_l: ∀A:Type[3].∀x.∀P:A → Prop. P x → ∀y. x = y → P y.
23 #A; #x; #P; #Hx; #y; #Heq;ncases Heq;nassumption.
26 ntheorem sym_peq: ∀A:Type[3].∀x,y:A. x = y → y = x.
27 #A; #x; #y; #Heq; napply (rewrite_l A x (λz.z=x));
28 ##[ @; ##| nassumption; ##]
31 ntheorem rewrite_r: ∀A:Type[3].∀x.∀P:A → Prop. P x → ∀y. y = x → P y.
32 #A; #x; #P; #Hx; #y; #Heq;ncases (sym_peq ? ? ?Heq);nassumption.
35 ntheorem eq_coerc: ∀A,B:Type[2].A→(A=B)→B.
36 #A; #B; #Ha; #Heq;nelim Heq; nassumption.
41 \forall A. \forall x:A. \forall P: \forall y:A. x=y \to Type.
42 P ? (refl_eq ? x) \to \forall y:A. \forall p:x=y. P y p.
45 (match p1 return \lambda y. \lambda p.P y p with
46 [refl_eq \Rightarrow p]).
49 variant reflexive_eq : \forall A:Type. reflexive A (eq A)
52 theorem symmetric_eq: \forall A:Type. symmetric A (eq A).
53 unfold symmetric.intros.elim H. apply refl_eq.
56 variant sym_eq : \forall A:Type.\forall x,y:A. x=y \to y=x
59 theorem transitive_eq : \forall A:Type. transitive A (eq A).
60 unfold transitive.intros.elim H1.assumption.
63 variant trans_eq : \forall A:Type.\forall x,y,z:A. x=y \to y=z \to x=z
66 theorem symmetric_not_eq: \forall A:Type. symmetric A (λx,y.x ≠ y).
67 unfold symmetric.simplify.intros.unfold.intro.apply H.apply sym_eq.assumption.
70 variant sym_neq: ∀A:Type.∀x,y.x ≠ y →y ≠ x
74 \forall A:Type.\forall x:A. \forall P: A \to Prop.
75 P x \to \forall y:A. y=x \to P y.
76 intros. elim (sym_eq ? ? ? H1).assumption.
80 \forall A:Type.\forall x:A. \forall P: A \to Set.
81 P x \to \forall y:A. y=x \to P y.
82 intros. elim (sym_eq ? ? ? H).assumption.
86 \forall A:Type.\forall x:A. \forall P: A \to Type.
87 P x \to \forall y:A. y=x \to P y.
88 intros. elim (sym_eq ? ? ? H).assumption.
91 theorem eq_f: \forall A,B:Type.\forall f:A\to B.
92 \forall x,y:A. x=y \to f x = f y.
93 intros.elim H.apply refl_eq.
96 theorem eq_f': \forall A,B:Type.\forall f:A\to B.
97 \forall x,y:A. x=y \to f y = f x.
98 intros.elim H.apply refl_eq.
108 cic:/matita/logic/equality/eq.ind
109 cic:/matita/logic/equality/sym_eq.con
110 cic:/matita/logic/equality/transitive_eq.con
111 cic:/matita/logic/equality/eq_ind.con
112 cic:/matita/logic/equality/eq_elim_r.con
113 cic:/matita/logic/equality/eq_rec.con
114 cic:/matita/logic/equality/eq_elim_r'.con
115 cic:/matita/logic/equality/eq_rect.con
116 cic:/matita/logic/equality/eq_elim_r''.con
117 cic:/matita/logic/equality/eq_f.con
119 cic:/matita/logic/equality/eq_OF_eq.con.
122 cic:/matita/logic/equality/eq_f'.con. (* \x.sym (eq_f x) *)
125 theorem eq_f2: \forall A,B,C:Type.\forall f:A\to B \to C.
126 \forall x1,x2:A. \forall y1,y2:B.
127 x1=x2 \to y1=y2 \to f x1 y1 = f x2 y2.
128 intros.elim H1.elim H.reflexivity.
136 eq_ind ? ? (\lambda a.a=y') eq2 ? eq1.
142 comp ? ? ? ? u u = refl_eq ? y.
144 apply (eq_rect' ? ? ? ? ? u).
150 \lambda H: \forall x,y:A. decidable (x=y).
151 \lambda x,y. \lambda p:x=y.
153 [ (or_introl p') \Rightarrow p'
154 | (or_intror K) \Rightarrow False_ind ? (K p) ].
158 \forall H: \forall x,y:A. decidable (x=y).
161 nu ? H ? ? u = nu ? H ? ? v.
164 unfold decidable in H.
165 apply (Or_ind' ? ? ? ? ? (H x y)); simplify.
170 definition nu_inv \def
172 \lambda H: \forall x,y:A. decidable (x=y).
175 comp ? ? ? ? (nu ? H ? ? (refl_eq ? x)) v.
179 \forall H: \forall x,y:A. decidable (x=y).
182 nu_inv ? H ? ? (nu ? H ? ? u) = u.
184 apply (eq_rect' ? ? ? ? ? u).
189 theorem eq_to_eq_to_eq_p_q:
190 \forall A. \forall x,y:A.
191 (\forall x,y:A. decidable (x=y)) \to
192 \forall p,q:x=y. p=q.
194 rewrite < (nu_left_inv ? H ? ? p).
195 rewrite < (nu_left_inv ? H ? ? q).
196 elim (nu_constant ? H ? ? q).
200 (*CSC: alternative proof that does not pollute the environment with
201 technical lemmata. Unfortunately, it is a pain to do without proper
203 theorem eq_to_eq_to_eq_p_q:
204 \forall A. \forall x,y:A.
205 (\forall x,y:A. decidable (x=y)) \to
206 \forall p,q:x=y. p=q.
209 (\lambda x,y. \lambda p:x=y.
211 [ (or_introl p') \Rightarrow p'
212 | (or_intror K) \Rightarrow False_ind ? (K p) ]).
215 eq_ind ? ? (\lambda z. z=y) (nu ? ? q) ? (nu ? ? (refl_eq ? x))
220 apply (eq_rect' ? ? ? ? ? q);
221 fold simplify (nu ? ? (refl_eq ? x)).
222 generalize in match (nu ? ? (refl_eq ? x)); intro.
225 (\lambda y. \lambda u.
226 eq_ind A x (\lambda a.a=y) u y u = refl_eq ? y)
230 rewrite < (Hcut p); fold simplify (nu ? ? p).
231 rewrite < (Hcut q); fold simplify (nu ? ? q).
232 apply (Or_ind' (x=x) (x \neq x)
233 (\lambda p:decidable (x=x). eq_ind A x (\lambda z.z=y) (nu x y p) x
234 ([\lambda H1.eq A x x]
236 [(or_introl p') \Rightarrow p'
237 |(or_intror K) \Rightarrow False_ind (x=x) (K (refl_eq A x))]) =
238 eq_ind A x (\lambda z.z=y) (nu x y q) x
239 ([\lambda H1.eq A x x]
241 [(or_introl p') \Rightarrow p'
242 |(or_intror K) \Rightarrow False_ind (x=x) (K (refl_eq A x))]))
244 intro; simplify; reflexivity.
245 intro q; elim (q (refl_eq ? x)).
250 theorem a:\forall x.x=x\land True.
255 exact (refl_eq Prop x);