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 **************************************************)
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): reflexive … (exteq A B).
32 lemma exteq_repl (A) (B): replace_2 … (exteq A B) (exteq A B) (exteq A B).
35 lemma exteq_sym (A) (B): symmetric … (exteq A B).
36 /2 width=1 by exteq_repl/ qed-.
38 lemma exteq_trans (A) (B): Transitive … (exteq A B).
39 /2 width=1 by exteq_repl/ qed-.
41 lemma exteq_canc_sn (A) (B): left_cancellable … (exteq A B).
42 /2 width=1 by exteq_repl/ qed-.
44 lemma exteq_canc_dx (A) (B): right_cancellable … (exteq A B).
45 /2 width=1 by exteq_repl/ qed-.
47 (* Constructions with function composition **********************************)
49 lemma compose_repl_fwd_dx (A) (B) (C) (g) (f1) (f2):
50 f1 ≐{A,B} f2 → g ∘ f1 ≐{A,C} g ∘ f2.
51 #A #B #C #g #f1 #f2 #Hf12 #a
55 lemma compose_repl_bak_dx (A) (B) (C) (g) (f1) (f2):
56 f1 ≐{A,B} f2 → g ∘ f2 ≐{A,C} g ∘ f1.
57 /3 width=1 by compose_repl_fwd_dx, exteq_sym/
60 lemma compose_repl_fwd_sn (A) (B) (C) (g1) (g2) (f):
61 g1 ≐{B,C} g2 → g1 ∘ f ≐{A,C} g2 ∘ f.
62 #A #B #C #g1 #g2 #f #Hg12 #a
66 lemma compose_repl_bak_sn (A) (B) (C) (g1) (g2) (f):
67 g1 ≐{B,C} g2 → g2 ∘ f ≐{A,C} g1 ∘ f.
68 /3 width=1 by compose_repl_fwd_sn, exteq_sym/
71 lemma compose_assoc (A1) (A2) (A3) (A4) (f3:A3→A4) (f2:A2→A3) (f1:A1→A2):
72 f3 ∘ (f2 ∘ f1) ≐ f3 ∘ f2 ∘ f1.