diff options
Diffstat (limited to 'theories/Numbers/Natural/Abstract/NIso.v')
| -rw-r--r-- | theories/Numbers/Natural/Abstract/NIso.v | 84 |
1 files changed, 33 insertions, 51 deletions
diff --git a/theories/Numbers/Natural/Abstract/NIso.v b/theories/Numbers/Natural/Abstract/NIso.v index f6ccf3db..47bf38cb 100644 --- a/theories/Numbers/Natural/Abstract/NIso.v +++ b/theories/Numbers/Natural/Abstract/NIso.v @@ -8,51 +8,41 @@ (* Evgeny Makarov, INRIA, 2007 *) (************************************************************************) -(*i $Id: NIso.v 10934 2008-05-15 21:58:20Z letouzey $ i*) +(*i $Id$ i*) Require Import NBase. -Module Homomorphism (NAxiomsMod1 NAxiomsMod2 : NAxiomsSig). +Module Homomorphism (N1 N2 : NAxiomsSig). -Module NBasePropMod2 := NBasePropFunct NAxiomsMod2. +Local Notation "n == m" := (N2.eq n m) (at level 70, no associativity). -Notation Local N1 := NAxiomsMod1.N. -Notation Local N2 := NAxiomsMod2.N. -Notation Local Eq1 := NAxiomsMod1.Neq. -Notation Local Eq2 := NAxiomsMod2.Neq. -Notation Local O1 := NAxiomsMod1.N0. -Notation Local O2 := NAxiomsMod2.N0. -Notation Local S1 := NAxiomsMod1.S. -Notation Local S2 := NAxiomsMod2.S. -Notation Local "n == m" := (Eq2 n m) (at level 70, no associativity). +Definition homomorphism (f : N1.t -> N2.t) : Prop := + f N1.zero == N2.zero /\ forall n, f (N1.succ n) == N2.succ (f n). -Definition homomorphism (f : N1 -> N2) : Prop := - f O1 == O2 /\ forall n : N1, f (S1 n) == S2 (f n). +Definition natural_isomorphism : N1.t -> N2.t := + N1.recursion N2.zero (fun (n : N1.t) (p : N2.t) => N2.succ p). -Definition natural_isomorphism : N1 -> N2 := - NAxiomsMod1.recursion O2 (fun (n : N1) (p : N2) => S2 p). - -Add Morphism natural_isomorphism with signature Eq1 ==> Eq2 as natural_isomorphism_wd. +Instance natural_isomorphism_wd : Proper (N1.eq ==> N2.eq) natural_isomorphism. Proof. unfold natural_isomorphism. intros n m Eqxy. -apply NAxiomsMod1.recursion_wd with (Aeq := Eq2). +apply N1.recursion_wd. reflexivity. -unfold fun2_eq. intros _ _ _ y' y'' H. now apply NBasePropMod2.succ_wd. +intros _ _ _ y' y'' H. now apply N2.succ_wd. assumption. Qed. -Theorem natural_isomorphism_0 : natural_isomorphism O1 == O2. +Theorem natural_isomorphism_0 : natural_isomorphism N1.zero == N2.zero. Proof. -unfold natural_isomorphism; now rewrite NAxiomsMod1.recursion_0. +unfold natural_isomorphism; now rewrite N1.recursion_0. Qed. Theorem natural_isomorphism_succ : - forall n : N1, natural_isomorphism (S1 n) == S2 (natural_isomorphism n). + forall n : N1.t, natural_isomorphism (N1.succ n) == N2.succ (natural_isomorphism n). Proof. unfold natural_isomorphism. -intro n. now rewrite (@NAxiomsMod1.recursion_succ N2 NAxiomsMod2.Neq) ; -[ | | unfold fun2_wd; intros; apply NBasePropMod2.succ_wd]. +intro n. rewrite N1.recursion_succ; auto with *. +repeat red; intros. apply N2.succ_wd; auto. Qed. Theorem hom_nat_iso : homomorphism natural_isomorphism. @@ -63,23 +53,20 @@ Qed. End Homomorphism. -Module Inverse (NAxiomsMod1 NAxiomsMod2 : NAxiomsSig). +Module Inverse (N1 N2 : NAxiomsSig). -Module Import NBasePropMod1 := NBasePropFunct NAxiomsMod1. +Module Import NBasePropMod1 := NBasePropFunct N1. (* This makes the tactic induct available. Since it is taken from (NBasePropFunct NAxiomsMod1), it refers to induction on N1. *) -Module Hom12 := Homomorphism NAxiomsMod1 NAxiomsMod2. -Module Hom21 := Homomorphism NAxiomsMod2 NAxiomsMod1. - -Notation Local N1 := NAxiomsMod1.N. -Notation Local N2 := NAxiomsMod2.N. -Notation Local h12 := Hom12.natural_isomorphism. -Notation Local h21 := Hom21.natural_isomorphism. +Module Hom12 := Homomorphism N1 N2. +Module Hom21 := Homomorphism N2 N1. -Notation Local "n == m" := (NAxiomsMod1.Neq n m) (at level 70, no associativity). +Local Notation h12 := Hom12.natural_isomorphism. +Local Notation h21 := Hom21.natural_isomorphism. +Local Notation "n == m" := (N1.eq n m) (at level 70, no associativity). -Lemma inverse_nat_iso : forall n : N1, h21 (h12 n) == n. +Lemma inverse_nat_iso : forall n : N1.t, h21 (h12 n) == n. Proof. induct n. now rewrite Hom12.natural_isomorphism_0, Hom21.natural_isomorphism_0. @@ -89,25 +76,20 @@ Qed. End Inverse. -Module Isomorphism (NAxiomsMod1 NAxiomsMod2 : NAxiomsSig). - -Module Hom12 := Homomorphism NAxiomsMod1 NAxiomsMod2. -Module Hom21 := Homomorphism NAxiomsMod2 NAxiomsMod1. +Module Isomorphism (N1 N2 : NAxiomsSig). -Module Inverse12 := Inverse NAxiomsMod1 NAxiomsMod2. -Module Inverse21 := Inverse NAxiomsMod2 NAxiomsMod1. +Module Hom12 := Homomorphism N1 N2. +Module Hom21 := Homomorphism N2 N1. +Module Inverse12 := Inverse N1 N2. +Module Inverse21 := Inverse N2 N1. -Notation Local N1 := NAxiomsMod1.N. -Notation Local N2 := NAxiomsMod2.N. -Notation Local Eq1 := NAxiomsMod1.Neq. -Notation Local Eq2 := NAxiomsMod2.Neq. -Notation Local h12 := Hom12.natural_isomorphism. -Notation Local h21 := Hom21.natural_isomorphism. +Local Notation h12 := Hom12.natural_isomorphism. +Local Notation h21 := Hom21.natural_isomorphism. -Definition isomorphism (f1 : N1 -> N2) (f2 : N2 -> N1) : Prop := +Definition isomorphism (f1 : N1.t -> N2.t) (f2 : N2.t -> N1.t) : Prop := Hom12.homomorphism f1 /\ Hom21.homomorphism f2 /\ - forall n : N1, Eq1 (f2 (f1 n)) n /\ - forall n : N2, Eq2 (f1 (f2 n)) n. + forall n, N1.eq (f2 (f1 n)) n /\ + forall n, N2.eq (f1 (f2 n)) n. Theorem iso_nat_iso : isomorphism h12 h21. Proof. |