inductive eq (A:Type) (x:A) : A \to Prop \def
refl_eq : eq A x x.
-
+
+(*CSC: the URI must disappear: there is a bug now *)
+interpretation "leibnitz's equality"
+ 'eq x y = (cic:/matita/logic/equality/eq.ind#xpointer(1/1) _ x y).
+(*CSC: the URI must disappear: there is a bug now *)
+interpretation "leibnitz's non-equality"
+ 'neq x y = (cic:/matita/logic/connectives/Not.con
+ (cic:/matita/logic/equality/eq.ind#xpointer(1/1) _ x y)).
+
+theorem eq_ind':
+ \forall A. \forall x:A. \forall P: \forall y:A. x=y \to Prop.
+ P ? (refl_eq ? x) \to \forall y:A. \forall p:x=y. P y p.
+ intros.
+ exact
+ (match p return \lambda y. \lambda p.P y p with
+ [refl_eq \Rightarrow H]).
+qed.
+
theorem reflexive_eq : \forall A:Type. reflexive A (eq A).
simplify.intros.apply refl_eq.
qed.
theorem symmetric_eq: \forall A:Type. symmetric A (eq A).
-simplify.intros.elim H. apply refl_eq.
+unfold symmetric.intros.elim H. apply refl_eq.
qed.
-theorem sym_eq : \forall A:Type.\forall x,y:A. eq A x y \to eq A y x
+theorem sym_eq : \forall A:Type.\forall x,y:A. x=y \to y=x
\def symmetric_eq.
theorem transitive_eq : \forall A:Type. transitive A (eq A).
-simplify.intros.elim H1.assumption.
+unfold transitive.intros.elim H1.assumption.
qed.
-theorem trans_eq : \forall A:Type.\forall x,y,z:A. eq A x y \to eq A y z \to eq A x z
+theorem trans_eq : \forall A:Type.\forall x,y,z:A. x=y \to y=z \to x=z
\def transitive_eq.
theorem eq_elim_r:
\forall A:Type.\forall x:A. \forall P: A \to Prop.
- P x \to \forall y:A. eq A y x \to P y.
-intros. elim sym_eq ? ? ? H1.assumption.
+ P x \to \forall y:A. y=x \to P y.
+intros. elim (sym_eq ? ? ? H1).assumption.
qed.
default "equality"
cic:/matita/logic/equality/eq_elim_r.con.
theorem eq_f: \forall A,B:Type.\forall f:A\to B.
-\forall x,y:A. eq A x y \to eq B (f x) (f y).
+\forall x,y:A. x=y \to f x = f y.
intros.elim H.reflexivity.
qed.
theorem eq_f2: \forall A,B,C:Type.\forall f:A\to B \to C.
\forall x1,x2:A. \forall y1,y2:B.
-eq A x1 x2\to eq B y1 y2\to eq C (f x1 y1) (f x2 y2).
+x1=x2 \to y1=y2 \to f x1 y1 = f x2 y2.
intros.elim H1.elim H.reflexivity.
-qed.
\ No newline at end of file
+qed.
+
+definition comp \def
+ \lambda A.
+ \lambda x,y,y':A.
+ \lambda eq1:x=y.
+ \lambda eq2:x=y'.
+ eq_ind ? ? (\lambda a.a=y') eq2 ? eq1.
+
+lemma trans_sym_eq:
+ \forall A.
+ \forall x,y:A.
+ \forall u:x=y.
+ comp ? ? ? ? u u = refl_eq ? y.
+ intros.
+ apply (eq_ind' ? ? ? ? ? u).
+ reflexivity.
+qed.
+
+definition nu \def
+ \lambda A.
+ \lambda H: \forall x,y:A. decidable (x=y).
+ \lambda x,y. \lambda p:x=y.
+ match H x y with
+ [ (or_introl p') \Rightarrow p'
+ | (or_intror K) \Rightarrow False_ind ? (K p) ].
+
+theorem nu_constant:
+ \forall A.
+ \forall H: \forall x,y:A. decidable (x=y).
+ \forall x,y:A.
+ \forall u,v:x=y.
+ nu ? H ? ? u = nu ? H ? ? v.
+ intros.
+ unfold nu.
+ unfold decidable in H.
+ apply (Or_ind' ? ? ? ? ? (H x y)); simplify.
+ intro; reflexivity.
+ intro; elim (q u).
+qed.
+
+definition nu_inv \def
+ \lambda A.
+ \lambda H: \forall x,y:A. decidable (x=y).
+ \lambda x,y:A.
+ \lambda v:x=y.
+ comp ? ? ? ? (nu ? H ? ? (refl_eq ? x)) v.
+
+theorem nu_left_inv:
+ \forall A.
+ \forall H: \forall x,y:A. decidable (x=y).
+ \forall x,y:A.
+ \forall u:x=y.
+ nu_inv ? H ? ? (nu ? H ? ? u) = u.
+ intros.
+ apply (eq_ind' ? ? ? ? ? u).
+ unfold nu_inv.
+ apply trans_sym_eq.
+qed.
+
+theorem eq_to_eq_to_eq_p_q:
+ \forall A. \forall x,y:A.
+ (\forall x,y:A. decidable (x=y)) \to
+ \forall p,q:x=y. p=q.
+ intros.
+ rewrite < (nu_left_inv ? H ? ? p).
+ rewrite < (nu_left_inv ? H ? ? q).
+ elim (nu_constant ? H ? ? q).
+ reflexivity.
+qed.
+
+(*CSC: alternative proof that does not pollute the environment with
+ technical lemmata. Unfortunately, it is a pain to do without proper
+ support for let-ins.
+theorem eq_to_eq_to_eq_p_q:
+ \forall A. \forall x,y:A.
+ (\forall x,y:A. decidable (x=y)) \to
+ \forall p,q:x=y. p=q.
+intros.
+letin nu \def
+ (\lambda x,y. \lambda p:x=y.
+ match H x y with
+ [ (or_introl p') \Rightarrow p'
+ | (or_intror K) \Rightarrow False_ind ? (K p) ]).
+cut
+ (\forall q:x=y.
+ eq_ind ? ? (\lambda z. z=y) (nu ? ? q) ? (nu ? ? (refl_eq ? x))
+ = q).
+focus 8.
+ clear q; clear p.
+ intro.
+ apply (eq_ind' ? ? ? ? ? q);
+ fold simplify (nu ? ? (refl_eq ? x)).
+ generalize in match (nu ? ? (refl_eq ? x)); intro.
+ apply
+ (eq_ind' A x
+ (\lambda y. \lambda u.
+ eq_ind A x (\lambda a.a=y) u y u = refl_eq ? y)
+ ? x H1).
+ reflexivity.
+unfocus.
+rewrite < (Hcut p); fold simplify (nu ? ? p).
+rewrite < (Hcut q); fold simplify (nu ? ? q).
+apply (Or_ind' (x=x) (x \neq x)
+ (\lambda p:decidable (x=x). eq_ind A x (\lambda z.z=y) (nu x y p) x
+ ([\lambda H1.eq A x x]
+ match p with
+ [(or_introl p') \Rightarrow p'
+ |(or_intror K) \Rightarrow False_ind (x=x) (K (refl_eq A x))]) =
+ eq_ind A x (\lambda z.z=y) (nu x y q) x
+ ([\lambda H1.eq A x x]
+ match p with
+ [(or_introl p') \Rightarrow p'
+ |(or_intror K) \Rightarrow False_ind (x=x) (K (refl_eq A x))]))
+ ? ? (H x x)).
+intro; simplify; reflexivity.
+intro q; elim (q (refl_eq ? x)).
+qed.
+*)
+
+(*
+theorem a:\forall x.x=x\land True.
+[
+2:intros;
+ split;
+ [
+ exact (refl_eq Prop x);
+ |
+ exact I;
+ ]
+1:
+ skip
+]
+qed.
+*)
+