1 (**************************************************************************)
4 (* ||A|| A project by Andrea Asperti *)
6 (* ||I|| Developers: *)
7 (* ||T|| The HELM team. *)
8 (* ||A|| http://helm.cs.unibo.it *)
10 (* \ / This file is distributed under the terms of the *)
11 (* v GNU General Public License Version 2 *)
13 (**************************************************************************)
15 include "ground/notation/relations/doteq_4.ma".
16 include "ground/lib/relations.ma".
18 (* EXTENSIONAL EQUIVALENCE FOR FUNCTIONS ************************************)
20 definition exteq (A,B:Type[0]): relation (A → B) ≝
21 λf1,f2. ∀a. f1 a = f2 a.
24 "extensional equivalence"
25 'DotEq A B f1 f2 = (exteq A B f1 f2).
27 (* Basic constructions ******************************************************)
29 lemma exteq_refl (A) (B):
30 reflexive … (exteq A B).
33 lemma exteq_repl (A) (B):
34 replace_2 … (exteq A B) (exteq A B) (exteq A B).
37 lemma exteq_sym (A) (B):
38 symmetric … (exteq A B).
39 /2 width=1 by exteq_repl/ qed-.
41 lemma exteq_trans (A) (B):
42 Transitive … (exteq A B).
43 /2 width=1 by exteq_repl/ qed-.
45 lemma exteq_canc_sn (A) (B):
46 left_cancellable … (exteq A B).
47 /2 width=1 by exteq_repl/ qed-.
49 lemma exteq_canc_dx (A) (B):
50 right_cancellable … (exteq A B).
51 /2 width=1 by exteq_repl/ qed-.
53 (* Constructions with compose ***********************************************)
55 lemma compose_repl_fwd_dx (A) (B) (C) (g) (f1) (f2):
56 f1 ≐{A,B} f2 → g ∘ f1 ≐{A,C} g ∘ f2.
57 #A #B #C #g #f1 #f2 #Hf12 #a
61 lemma compose_repl_bak_dx (A) (B) (C) (g) (f1) (f2):
62 f1 ≐{A,B} f2 → g ∘ f2 ≐{A,C} g ∘ f1.
63 /3 width=1 by compose_repl_fwd_dx, exteq_sym/
66 lemma compose_repl_fwd_sn (A) (B) (C) (g1) (g2) (f):
67 g1 ≐{B,C} g2 → g1 ∘ f ≐{A,C} g2 ∘ f.
68 #A #B #C #g1 #g2 #f #Hg12 #a
72 lemma compose_repl_bak_sn (A) (B) (C) (g1) (g2) (f):
73 g1 ≐{B,C} g2 → g2 ∘ f ≐{A,C} g1 ∘ f.
74 /3 width=1 by compose_repl_fwd_sn, exteq_sym/
77 lemma compose_assoc (A1) (A2) (A3) (A4) (f3:A3→A4) (f2:A2→A3) (f1:A1→A2):
78 f3 ∘ (f2 ∘ f1) ≐ f3 ∘ f2 ∘ f1.