(* This program is free software; you can redistribute it and/or      *)
(* modify it under the terms of the GNU Lesser General Public License *)
(* as published by the Free Software Foundation; either version 2.1   *)
(* of the License, or (at your option) any later version.             *)
(*                                                                    *)
(* This program is distributed in the hope that it will be useful,    *)
(* but WITHOUT ANY WARRANTY; without even the implied warranty of     *)
(* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the      *)
(* GNU General Public License for more details.                       *)
(*                                                                    *)
(* You should have received a copy of the GNU Lesser General Public   *)
(* License along with this program; if not, write to the Free         *)
(* Software Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA *)
(* 02110-1301 USA                                                     *)


(*****************************************************************************)
(*          Projet Formel - Calculus of Inductive Constructions V5.10        *)
(*****************************************************************************)
(*									     *)
(*            Example of Universal Arrow : Universal Arrow from the          *)
(*		Set A to the Forgetful Functor MON -> SET                    *)
(*****************************************************************************)
(*									     *)
(*                     A. SAIBI	  May 95                  		     *)
(*									     *)
(*****************************************************************************)



Require Export FunForget.
Require Export FreeMonoid.
Require Export UniversalArrow.

Set Implicit Arguments.
Unset Strict Implicit.

Section ua_fm.

Variable A : Setoid.

Definition UA_FM_fun (a : A) : FunForget A := Concat1 a (Empty A).

Lemma UA_FM_map_law : Map_law UA_FM_fun.
Proof.
(* Goal: @Map_law A (@FOb MON SET FunForget (FreeMonoid A)) UA_FM_fun *)
unfold Map_law in |- *; simpl in |- *; intros a b H; split; trivial. 
Qed.

Canonical Structure UA_FM_mor := Build_Map UA_FM_map_law.

 Section ua_fm_diese_def.

 Variables (B : Monoid) (f : Map A (FunForget B)). 

 Fixpoint UA_FM_diese_fun (l : FreeMonoid A) : B :=
   match l with
   | Empty => Munit B
   | Concat1 a m => f a +_M UA_FM_diese_fun m
   end.

 Lemma UA_FM_diese_map_law : Map_law UA_FM_diese_fun.
 Proof.
(* Goal: @Map_law (Mcarrier (FreeMonoid A)) (Mcarrier B) UA_FM_diese_fun *)
 unfold Map_law in |- *; simpl in |- *.
(* Goal: forall (x y : Tlist A) (_ : @Equal_Tlist A x y), @Equal (Mcarrier B) (UA_FM_diese_fun x) (UA_FM_diese_fun y) *)
 intros l1; elim l1.
(* Goal: forall (y : Tlist A) (_ : @Equal_Tlist A (Empty A) y), @Equal (Mcarrier B) (UA_FM_diese_fun (Empty A)) (UA_FM_diese_fun y) *)
(* Goal: forall (c : Carrier A) (t : Tlist A) (_ : forall (y : Tlist A) (_ : @Equal_Tlist A t y), @Equal (Mcarrier B) (UA_FM_diese_fun t) (UA_FM_diese_fun y)) (y : Tlist A) (_ : @Equal_Tlist A (@Concat1 A c t) y), @Equal (Mcarrier B) (UA_FM_diese_fun (@Concat1 A c t)) (UA_FM_diese_fun y) *)
 intro l2; elim l2.
(* Goal: forall _ : @Equal_Tlist A (Empty A) (Empty A), @Equal (Mcarrier B) (UA_FM_diese_fun (Empty A)) (UA_FM_diese_fun (Empty A)) *)
(* Goal: forall (c : Carrier A) (t : Tlist A) (_ : forall _ : @Equal_Tlist A (Empty A) t, @Equal (Mcarrier B) (UA_FM_diese_fun (Empty A)) (UA_FM_diese_fun t)) (_ : @Equal_Tlist A (Empty A) (@Concat1 A c t)), @Equal (Mcarrier B) (UA_FM_diese_fun (Empty A)) (UA_FM_diese_fun (@Concat1 A c t)) *)
(* Goal: forall (c : Carrier A) (t : Tlist A) (_ : forall (y : Tlist A) (_ : @Equal_Tlist A t y), @Equal (Mcarrier B) (UA_FM_diese_fun t) (UA_FM_diese_fun y)) (y : Tlist A) (_ : @Equal_Tlist A (@Concat1 A c t) y), @Equal (Mcarrier B) (UA_FM_diese_fun (@Concat1 A c t)) (UA_FM_diese_fun y) *)
 simpl in |- *; intro; apply Refl.
(* Goal: forall (c : Carrier A) (t : Tlist A) (_ : forall _ : @Equal_Tlist A (Empty A) t, @Equal (Mcarrier B) (UA_FM_diese_fun (Empty A)) (UA_FM_diese_fun t)) (_ : @Equal_Tlist A (Empty A) (@Concat1 A c t)), @Equal (Mcarrier B) (UA_FM_diese_fun (Empty A)) (UA_FM_diese_fun (@Concat1 A c t)) *)
(* Goal: forall (c : Carrier A) (t : Tlist A) (_ : forall (y : Tlist A) (_ : @Equal_Tlist A t y), @Equal (Mcarrier B) (UA_FM_diese_fun t) (UA_FM_diese_fun y)) (y : Tlist A) (_ : @Equal_Tlist A (@Concat1 A c t) y), @Equal (Mcarrier B) (UA_FM_diese_fun (@Concat1 A c t)) (UA_FM_diese_fun y) *)
 intros c t H1 H2; elim H2.
(* Goal: forall (c : Carrier A) (t : Tlist A) (_ : forall (y : Tlist A) (_ : @Equal_Tlist A t y), @Equal (Mcarrier B) (UA_FM_diese_fun t) (UA_FM_diese_fun y)) (y : Tlist A) (_ : @Equal_Tlist A (@Concat1 A c t) y), @Equal (Mcarrier B) (UA_FM_diese_fun (@Concat1 A c t)) (UA_FM_diese_fun y) *)
 intros c t H1 l2; elim l2.
(* Goal: forall _ : @Equal_Tlist A (@Concat1 A c t) (Empty A), @Equal (Mcarrier B) (UA_FM_diese_fun (@Concat1 A c t)) (UA_FM_diese_fun (Empty A)) *)
(* Goal: forall (c0 : Carrier A) (t0 : Tlist A) (_ : forall _ : @Equal_Tlist A (@Concat1 A c t) t0, @Equal (Mcarrier B) (UA_FM_diese_fun (@Concat1 A c t)) (UA_FM_diese_fun t0)) (_ : @Equal_Tlist A (@Concat1 A c t) (@Concat1 A c0 t0)), @Equal (Mcarrier B) (UA_FM_diese_fun (@Concat1 A c t)) (UA_FM_diese_fun (@Concat1 A c0 t0)) *)
 intro H2; absurd (Equal_Tlist (Concat1 c t) (Empty A)).
(* Goal: not (@Equal_Tlist A (@Concat1 A c t) (Empty A)) *)
(* Goal: @Equal_Tlist A (@Concat1 A c t) (Empty A) *)
(* Goal: forall (c0 : Carrier A) (t0 : Tlist A) (_ : forall _ : @Equal_Tlist A (@Concat1 A c t) t0, @Equal (Mcarrier B) (UA_FM_diese_fun (@Concat1 A c t)) (UA_FM_diese_fun t0)) (_ : @Equal_Tlist A (@Concat1 A c t) (@Concat1 A c0 t0)), @Equal (Mcarrier B) (UA_FM_diese_fun (@Concat1 A c t)) (UA_FM_diese_fun (@Concat1 A c0 t0)) *)
 apply Diff_Concat1_Empty.
(* Goal: @Equal (Mcarrier B) (@ApMop B (@Ap A (@FOb MON SET FunForget B) f c) (UA_FM_diese_fun t0)) (@ApMop B (@Ap A (Mcarrier B) f c0) (UA_FM_diese_fun t0)) *)
 trivial.
(* Goal: forall (c0 : Carrier A) (t0 : Tlist A) (_ : forall _ : @Equal_Tlist A (@Concat1 A c t) t0, @Equal (Mcarrier B) (UA_FM_diese_fun (@Concat1 A c t)) (UA_FM_diese_fun t0)) (_ : @Equal_Tlist A (@Concat1 A c t) (@Concat1 A c0 t0)), @Equal (Mcarrier B) (UA_FM_diese_fun (@Concat1 A c t)) (UA_FM_diese_fun (@Concat1 A c0 t0)) *)
 intros c0 t0 H2; simpl in |- *; intro H3; elim H3; intros H4 H5.
(* Goal: @Equal (Mcarrier B) (@ApMop B (@Ap A (Mcarrier B) f c) (UA_FM_diese_fun t)) (@ApMop B (@Ap A (Mcarrier B) f c0) (UA_FM_diese_fun t0)) *)
 apply Trans with (f c +_M UA_FM_diese_fun t0).
(* Goal: @Equal (Mcarrier B) (@ApMop B (@Ap A (Mcarrier B) f c) (UA_FM_diese_fun t)) (@ApMop B (@Ap A (@FOb MON SET FunForget B) f c) (UA_FM_diese_fun t0)) *)
(* Goal: @Equal (Mcarrier B) (@ApMop B (@Ap A (@FOb MON SET FunForget B) f c) (UA_FM_diese_fun t0)) (@ApMop B (@Ap A (Mcarrier B) f c0) (UA_FM_diese_fun t0)) *)
 unfold ApMop in |- *; apply Map2_l.
(* Goal: @Equal (Mcarrier B) (@ApMop B (@Ap A (@FOb MON SET FunForget B) f c) (UA_FM_diese_fun t0)) (@ApMop B (@Ap A (Mcarrier B) f c0) (UA_FM_diese_fun t0)) *)
 apply H1; trivial.
(* Goal: @Equal (Mcarrier B) (@ApMop B (@Ap A (@FOb MON SET FunForget B) f c) (UA_FM_diese_fun t0)) (@ApMop B (@Ap A (Mcarrier B) f c0) (UA_FM_diese_fun t0)) *)
 trivial.
(* Goal: @Equal (Mcarrier B) (@ApMop B (@Ap A (@FOb MON SET FunForget B) f c) (UA_FM_diese_fun t0)) (@ApMop B (@Ap A (Mcarrier B) f c0) (UA_FM_diese_fun t0)) *)
 unfold ApMop in |- *; apply Map2_r.
(* Goal: @Equal (Mcarrier B) (@ApMop B (@Ap A (@FOb MON SET FunForget B) f c) (UA_FM_diese_fun t0)) (@ApMop B (@Ap A (Mcarrier B) f c0) (UA_FM_diese_fun t0)) *)
 apply Pres1; trivial.
 Qed.
 
 Canonical Structure UA_FM_diese_map := Build_Map UA_FM_diese_map_law.
 
 Lemma UA_FM_diese_unit_law : MonUnit_law UA_FM_diese_map.
 Proof.
(* Goal: @MonUnit_law (FreeMonoid A) B UA_FM_diese_map *)
 unfold MonUnit_law in |- *; simpl in |- *.
(* Goal: @Equal (Mcarrier B) (UA_FM_diese_fun (@ApMop (FreeMonoid A) (Empty A) l2)) (UA_FM_diese_fun l2) *)
(* Goal: @Equal (Mcarrier B) (UA_FM_diese_fun l2) (@ApMop B (Munit B) (UA_FM_diese_fun l2)) *)
(* Goal: forall (c : Carrier A) (t : Tlist A) (_ : forall b : Tlist A, @Equal (Mcarrier B) (UA_FM_diese_fun (@ApMop (FreeMonoid A) t b)) (@ApMop B (UA_FM_diese_fun t) (UA_FM_diese_fun b))) (b : Tlist A), @Equal (Mcarrier B) (UA_FM_diese_fun (@ApMop (FreeMonoid A) (@Concat1 A c t) b)) (@ApMop B (UA_FM_diese_fun (@Concat1 A c t)) (UA_FM_diese_fun b)) *)
 apply Refl.
 Qed. 

 Lemma UA_FM_diese_op_law : MonOp_law UA_FM_diese_map.
 Proof.
(* Goal: @MonOp_law (FreeMonoid A) B UA_FM_diese_map *)
 unfold MonOp_law in |- *; simpl in |- *.
(* Goal: forall a b : Tlist A, @Equal (Mcarrier B) (UA_FM_diese_fun (@ApMop (FreeMonoid A) a b)) (@ApMop B (UA_FM_diese_fun a) (UA_FM_diese_fun b)) *)
 intro l1; elim l1.
(* Goal: forall b : Tlist A, @Equal (Mcarrier B) (UA_FM_diese_fun (@ApMop (FreeMonoid A) (Empty A) b)) (@ApMop B (UA_FM_diese_fun (Empty A)) (UA_FM_diese_fun b)) *)
(* Goal: forall (c : Carrier A) (t : Tlist A) (_ : forall b : Tlist A, @Equal (Mcarrier B) (UA_FM_diese_fun (@ApMop (FreeMonoid A) t b)) (@ApMop B (UA_FM_diese_fun t) (UA_FM_diese_fun b))) (b : Tlist A), @Equal (Mcarrier B) (UA_FM_diese_fun (@ApMop (FreeMonoid A) (@Concat1 A c t) b)) (@ApMop B (UA_FM_diese_fun (@Concat1 A c t)) (UA_FM_diese_fun b)) *)
 simpl in |- *; intro l2.
(* Goal: @Equal (Mcarrier B) (UA_FM_diese_fun (@ApMop (FreeMonoid A) (Empty A) l2)) (@ApMop B (Munit B) (UA_FM_diese_fun l2)) *)
(* Goal: forall (c : Carrier A) (t : Tlist A) (_ : forall b : Tlist A, @Equal (Mcarrier B) (UA_FM_diese_fun (@ApMop (FreeMonoid A) t b)) (@ApMop B (UA_FM_diese_fun t) (UA_FM_diese_fun b))) (b : Tlist A), @Equal (Mcarrier B) (UA_FM_diese_fun (@ApMop (FreeMonoid A) (@Concat1 A c t) b)) (@ApMop B (UA_FM_diese_fun (@Concat1 A c t)) (UA_FM_diese_fun b)) *)
 apply Trans with (UA_FM_diese_fun l2).
(* Goal: @Equal (Mcarrier B) (UA_FM_diese_fun (@ApMop (FreeMonoid A) (Empty A) l2)) (UA_FM_diese_fun l2) *)
(* Goal: @Equal (Mcarrier B) (UA_FM_diese_fun l2) (@ApMop B (Munit B) (UA_FM_diese_fun l2)) *)
(* Goal: forall (c : Carrier A) (t : Tlist A) (_ : forall b : Tlist A, @Equal (Mcarrier B) (UA_FM_diese_fun (@ApMop (FreeMonoid A) t b)) (@ApMop B (UA_FM_diese_fun t) (UA_FM_diese_fun b))) (b : Tlist A), @Equal (Mcarrier B) (UA_FM_diese_fun (@ApMop (FreeMonoid A) (@Concat1 A c t) b)) (@ApMop B (UA_FM_diese_fun (@Concat1 A c t)) (UA_FM_diese_fun b)) *)
 apply Refl.
(* Goal: @Equal (Mcarrier B) (UA_FM_diese_fun l2) (@ApMop B (Munit B) (UA_FM_diese_fun l2)) *)
(* Goal: forall (c : Carrier A) (t : Tlist A) (_ : forall b : Tlist A, @Equal (Mcarrier B) (UA_FM_diese_fun (@ApMop (FreeMonoid A) t b)) (@ApMop B (UA_FM_diese_fun t) (UA_FM_diese_fun b))) (b : Tlist A), @Equal (Mcarrier B) (UA_FM_diese_fun (@ApMop (FreeMonoid A) (@Concat1 A c t) b)) (@ApMop B (UA_FM_diese_fun (@Concat1 A c t)) (UA_FM_diese_fun b)) *)
 apply Midl1.
(* Goal: forall (c : Carrier A) (t : Tlist A) (_ : forall b : Tlist A, @Equal (Mcarrier B) (UA_FM_diese_fun (@ApMop (FreeMonoid A) t b)) (@ApMop B (UA_FM_diese_fun t) (UA_FM_diese_fun b))) (b : Tlist A), @Equal (Mcarrier B) (UA_FM_diese_fun (@ApMop (FreeMonoid A) (@Concat1 A c t) b)) (@ApMop B (UA_FM_diese_fun (@Concat1 A c t)) (UA_FM_diese_fun b)) *)
 simpl in |- *; intros c t H l2.
(* Goal: @Equal (Mcarrier B) (@ApMop B (@Ap A (Mcarrier B) f c) (UA_FM_diese_fun (@Concat A t l2))) (@ApMop B (@ApMop B (@Ap A (Mcarrier B) f c) (UA_FM_diese_fun t)) (UA_FM_diese_fun l2)) *)
 apply Trans with (f c +_M (UA_FM_diese_fun t +_M UA_FM_diese_fun l2)).
(* Goal: @Equal (Mcarrier B) (@ApMop B (@Ap A (Mcarrier B) f c) (UA_FM_diese_fun (@Concat A t l2))) (@ApMop B (@Ap A (@FOb MON SET FunForget B) f c) (@ApMop B (UA_FM_diese_fun t) (UA_FM_diese_fun l2))) *)
(* Goal: @Equal (Mcarrier B) (@ApMop B (@Ap A (@FOb MON SET FunForget B) f c) (@ApMop B (UA_FM_diese_fun t) (UA_FM_diese_fun l2))) (@ApMop B (@ApMop B (@Ap A (Mcarrier B) f c) (UA_FM_diese_fun t)) (UA_FM_diese_fun l2)) *)
 unfold ApMop in |- *; apply Map2_l; exact (H l2).
(* Goal: @Equal (Mcarrier B) (@ApMop B (@Ap A (@FOb MON SET FunForget B) f c) (@ApMop B (UA_FM_diese_fun t) (UA_FM_diese_fun l2))) (@ApMop B (@ApMop B (@Ap A (Mcarrier B) f c) (UA_FM_diese_fun t)) (UA_FM_diese_fun l2)) *)
 apply Mass. 
 Qed.

 Canonical Structure UA_FM_diese :=
   Build_MonMor UA_FM_diese_unit_law UA_FM_diese_op_law.

 End ua_fm_diese_def.

Lemma UA_FM_law1 : UA_law1 UA_FM_mor UA_FM_diese.
Proof.
(* Goal: @UA_law1 MON SET A FunForget (FreeMonoid A) UA_FM_mor UA_FM_diese *)
unfold UA_law1, UA_eq in |- *; intros B f.
(* Goal: @Equal (@Hom SET A (@FOb MON SET FunForget B)) (@Comp SET A (@FOb MON SET FunForget (FreeMonoid A)) (@FOb MON SET FunForget B) UA_FM_mor (@FMor MON SET FunForget (FreeMonoid A) B (@UA_FM_diese B f))) f *)
unfold UA_FM_mor in |- *; simpl in |- *.
(* Goal: @Ext A (Mcarrier B) (@Comp SET A (Tlist_setoid A) (Mcarrier B) (@Build_Map A (Tlist_setoid A) UA_FM_fun UA_FM_map_law) (@FMor MON SET FunForget (FreeMonoid A) B (@UA_FM_diese B f))) f *)
unfold Ext in |- *; simpl in |- *.
(* Goal: forall x : Carrier A, @Equal (Mcarrier B) (@ApMop B (@Ap A (Mcarrier B) f x) (Munit B)) (@Ap A (Mcarrier B) f x) *)
intro a; apply Midr1.
Qed.

Lemma UA_FM_law2 : UA_law2 UA_FM_mor UA_FM_diese.
Proof.
(* Goal: @UA_law2 MON SET A FunForget (FreeMonoid A) UA_FM_mor UA_FM_diese *)
unfold UA_law2 in |- *; simpl in |- *.
(* Goal: forall (a' : Monoid) (f : Map A (Mcarrier a')) (g : MonMor (FreeMonoid A) a') (_ : @UA_eq MON SET A FunForget (FreeMonoid A) UA_FM_mor a' f g), @Equal_MonMor (FreeMonoid A) a' g (@UA_FM_diese a' f) *)
unfold UA_eq, Equal_MonMor in |- *; simpl in |- *.
(* Goal: forall (a' : Monoid) (f : Map A (Mcarrier a')) (g : MonMor (FreeMonoid A) a') (_ : @Ext A (Mcarrier a') (@Comp SET A (Tlist_setoid A) (Mcarrier a') UA_FM_mor (@FMor MON SET FunForget (FreeMonoid A) a' g)) f), @Ext (Tlist_setoid A) (Mcarrier a') (@MonMap (FreeMonoid A) a' g) (@UA_FM_diese_map a' f) *)
unfold UA_FM_diese_map, Ext in |- *; simpl in |- *.
(* Goal: forall (a' : Monoid) (f : Map A (Mcarrier a')) (g : MonMor (FreeMonoid A) a') (_ : forall x : Carrier A, @Equal (Mcarrier a') (@Comp_fun A (Tlist_setoid A) (Mcarrier a') UA_FM_mor (@FMor MON SET FunForget (FreeMonoid A) a' g) x) (@Ap A (Mcarrier a') f x)) (x : Tlist A), @Equal (Mcarrier a') (@Ap (Tlist_setoid A) (Mcarrier a') (@MonMap (FreeMonoid A) a' g) x) (@UA_FM_diese_fun a' f x) *)
unfold Comp_fun, UA_FM_fun, FMor at 1 in |- *; simpl in |- *.
(* Goal: forall (a' : Monoid) (f : Map A (Mcarrier a')) (g : MonMor (FreeMonoid A) a') (_ : forall x : Carrier A, @Equal (Mcarrier a') (@Ap (Tlist_setoid A) (Mcarrier a') (@MonMap (FreeMonoid A) a' g) (UA_FM_fun x)) (@Ap A (Mcarrier a') f x)) (x : Tlist A), @Equal (Mcarrier a') (@Ap (Tlist_setoid A) (Mcarrier a') (@MonMap (FreeMonoid A) a' g) x) (@UA_FM_diese_fun a' f x) *)
intros B f h H l; elim l; simpl in |- *.
(* Goal: @Equal (Mcarrier B) (@Ap (Tlist_setoid A) (Mcarrier B) (@MonMap (FreeMonoid A) B h) (Empty A)) (Munit B) *)
(* Goal: forall (c : Carrier A) (t : Tlist A) (_ : @Equal (Mcarrier B) (@Ap (Tlist_setoid A) (Mcarrier B) (@MonMap (FreeMonoid A) B h) t) (@UA_FM_diese_fun B f t)), @Equal (Mcarrier B) (@Ap (Tlist_setoid A) (Mcarrier B) (@MonMap (FreeMonoid A) B h) (@Concat1 A c t)) (@ApMop B (@Ap A (Mcarrier B) f c) (@UA_FM_diese_fun B f t)) *)
apply (MMon_unit h).
(* Goal: forall (c : Carrier A) (t : Tlist A) (_ : @Equal (Mcarrier B) (@Ap (Tlist_setoid A) (Mcarrier B) (@MonMap (FreeMonoid A) B h) t) (@UA_FM_diese_fun B f t)), @Equal (Mcarrier B) (@Ap (Tlist_setoid A) (Mcarrier B) (@MonMap (FreeMonoid A) B h) (@Concat1 A c t)) (@ApMop B (@Ap A (Mcarrier B) f c) (@UA_FM_diese_fun B f t)) *)
intros c t H1. 
(* Goal: @Equal (Mcarrier B) (@Ap (Tlist_setoid A) (Mcarrier B) (@MonMap (FreeMonoid A) B h) (@Concat1 A c t)) (@ApMop B (@Ap A (Mcarrier B) f c) (@UA_FM_diese_fun B f t)) *)
apply Trans with (h (Concat1 c (Empty A)) +_M h t).
(* Goal: @Equal (Mcarrier B) (@Ap (Tlist_setoid A) (Mcarrier B) (@MonMap (FreeMonoid A) B h) (@Concat1 A c t)) (@ApMop B (@Ap (Mcarrier (FreeMonoid A)) (Mcarrier B) (@MonMap (FreeMonoid A) B h) (@Concat1 A c (Empty A))) (@Ap (Mcarrier (FreeMonoid A)) (Mcarrier B) (@MonMap (FreeMonoid A) B h) t)) *)
(* Goal: @Equal (Mcarrier B) (@ApMop B (@Ap (Mcarrier (FreeMonoid A)) (Mcarrier B) (@MonMap (FreeMonoid A) B h) (@Concat1 A c (Empty A))) (@Ap (Mcarrier (FreeMonoid A)) (Mcarrier B) (@MonMap (FreeMonoid A) B h) t)) (@ApMop B (@Ap A (Mcarrier B) f c) (@UA_FM_diese_fun B f t)) *)
apply (MMon_op h (Concat1 c (Empty A)) t).
(* Goal: @Equal (Mcarrier B) (@ApMop B (@Ap (Mcarrier (FreeMonoid A)) (Mcarrier B) (@MonMap (FreeMonoid A) B h) (@Concat1 A c (Empty A))) (@Ap (Mcarrier (FreeMonoid A)) (Mcarrier B) (@MonMap (FreeMonoid A) B h) t)) (@ApMop B (@Ap A (Mcarrier B) f c) (@UA_FM_diese_fun B f t)) *)
apply Trans with (f c +_M h t).
(* Goal: @Equal (Mcarrier B) (@ApMop B (@Ap (Mcarrier (FreeMonoid A)) (Mcarrier B) (@MonMap (FreeMonoid A) B h) (@Concat1 A c (Empty A))) (@Ap (Mcarrier (FreeMonoid A)) (Mcarrier B) (@MonMap (FreeMonoid A) B h) t)) (@ApMop B (@Ap A (Mcarrier B) f c) (@Ap (Mcarrier (FreeMonoid A)) (Mcarrier B) (@MonMap (FreeMonoid A) B h) t)) *)
(* Goal: @Equal (Mcarrier B) (@ApMop B (@Ap A (Mcarrier B) f c) (@Ap (Mcarrier (FreeMonoid A)) (Mcarrier B) (@MonMap (FreeMonoid A) B h) t)) (@ApMop B (@Ap A (Mcarrier B) f c) (@UA_FM_diese_fun B f t)) *)
unfold ApMop in |- *; apply Map2_r; exact (H c). 
(* Goal: @Equal (Mcarrier B) (@ApMop B (@Ap A (@FOb MON SET FunForget B) f c) (UA_FM_diese_fun t0)) (@ApMop B (@Ap A (Mcarrier B) f c0) (UA_FM_diese_fun t0)) *)
unfold ApMop in |- *; apply Map2_l; trivial.
Qed.
  
Lemma IsUA_FM : IsUA UA_FM_mor.
Proof.
(* Goal: @IsUA MON SET A FunForget (FreeMonoid A) UA_FM_mor *)
exact (Build_IsUA UA_FM_law1 UA_FM_law2).
Defined.

Definition UA_FM : UA A FunForget := IsUA_FM.

End ua_fm.

