helm/software/matita/library/Q/fraction/finv.ma

   1 (**************************************************************************)
   2 (*       ___                                                                *)
   3 (*      ||M||                                                             *)
   4 (*      ||A||       A project by Andrea Asperti                           *)
   5 (*      ||T||                                                             *)
   6 (*      ||I||       Developers:                                           *)
   7 (*      ||T||       A.Asperti, C.Sacerdoti Coen,                          *)
   8 (*      ||A||       E.Tassi, S.Zacchiroli                                 *)
   9 (*      \   /                                                             *)
  10 (*       \ /        This file is distributed under the terms of the       *)
  11 (*        v         GNU Lesser General Public License Version 2.1         *)
  12 (*                                                                        *)
  13 (**************************************************************************)
  14
  15 include "Z/plus.ma".
  16 include "Q/fraction/fraction.ma".
  17
  18 let rec finv f \def
  19   match f with
  20   [ (pp n) \Rightarrow (nn n)
  21   | (nn n) \Rightarrow (pp n)
  22   | (cons x g) \Rightarrow (cons (Zopp x) (finv g))].
  23
  24 theorem finv_finv: ∀f. finv (finv f) = f.
  25  intro;
  26  elim f;
  27   [1,2: reflexivity
  28   | simplify;
  29     rewrite > H;
  30     rewrite > Zopp_Zopp;
  31     reflexivity
  32   ]
  33 qed.
  34
  35 theorem or_numerator_nfa_one_nfa_proper:
  36 ∀f.
  37  (numerator f = nfa_one ∧ ∃g.numerator (finv f) = nfa_proper g) ∨
  38  ∃g.numerator f = nfa_proper g.
  39 intro.elim f
  40   [simplify.right.
  41    apply (ex_intro ? ? (nf_last n)).reflexivity
  42   |simplify.left.split
  43     [reflexivity
  44     |apply (ex_intro ? ? (nf_last n)).reflexivity
  45     ]
  46   |elim H;clear H
  47     [elim H1.clear H1.
  48      elim H2.clear H2.
  49      elim z
  50       [simplify.
  51        rewrite > H.rewrite > H1.simplify.
  52        left.split
  53         [reflexivity
  54         |apply (ex_intro ? ? (nf_cons O a)).reflexivity
  55         ]
  56       |simplify.
  57        rewrite > H.rewrite > H1.simplify.
  58        right.apply (ex_intro ? ? (nf_last n)).reflexivity
  59       |simplify.
  60        rewrite > H.rewrite > H1.simplify.
  61        left.split
  62         [reflexivity
  63         |apply (ex_intro ? ? (nf_cons (S n) a)).reflexivity
  64         ]
  65       ]
  66     |elim H1.clear H1.
  67       elim z
  68       [simplify.
  69        rewrite > H.simplify.
  70        right.
  71        apply (ex_intro ? ? (nf_cons O a)).reflexivity
  72       |simplify.
  73        rewrite > H.simplify.
  74        right.apply (ex_intro ? ? (nf_cons (S n) a)).reflexivity
  75       |simplify.
  76        rewrite > H.simplify.
  77        right.
  78        apply (ex_intro ? ? (nf_cons O a)).reflexivity
  79       ]
  80     ]
  81   ]
  82 qed.
  83
  84 theorem eq_nfa_one_to_eq_finv_nfa_proper:
  85 ∀f.numerator f = nfa_one → ∃h.numerator (finv f) = nfa_proper h.
  86   intros;
  87   elim (or_numerator_nfa_one_nfa_proper f); cases H1;
  88    [ assumption
  89    | rewrite > H in H2;
  90      destruct
  91    ]
  92 qed.