(* 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                                                     *)


Set Implicit Arguments.
Unset Strict Implicit.
Require Export Monoid_util.
Require Export Parts2.
Section Image_hom.
Variable M M' : MONOID.
Variable f : Hom M M'.

Definition image_monoid_hom : submonoid M'.
(* Goal: submonoid M' *)
apply (BUILD_SUB_MONOID (G:=M') (H:=image_map f)).
(* Goal: forall (y : Carrier (sgroup_set (monoid_sgroup M'))) (_ : @in_part (sgroup_set (monoid_sgroup M')) y (@subsgroup_part (monoid_sgroup M') (@submonoid_subsgroup M' image_monoid_hom))), @ex (Carrier (sgroup_set (monoid_sgroup M))) (fun x : Carrier (sgroup_set (monoid_sgroup M)) => @Equal (sgroup_set (monoid_sgroup M')) y (@Ap (sgroup_set (monoid_sgroup M)) (sgroup_set (monoid_sgroup M')) (@sgroup_map (monoid_sgroup M) (monoid_sgroup M') (@monoid_sgroup_hom M M' f)) x)) *)
simpl in |- *.
(* Goal: forall (x y : Carrier (sgroup_set (monoid_sgroup M'))) (_ : @ex (Carrier (sgroup_set (monoid_sgroup M))) (fun x0 : Carrier (sgroup_set (monoid_sgroup M)) => and True (@Equal (sgroup_set (monoid_sgroup M')) x (@Ap (sgroup_set (monoid_sgroup M)) (sgroup_set (monoid_sgroup M')) (@sgroup_map (monoid_sgroup M) (monoid_sgroup M') (@monoid_sgroup_hom M M' f)) x0)))) (_ : @ex (Carrier (sgroup_set (monoid_sgroup M))) (fun x0 : Carrier (sgroup_set (monoid_sgroup M)) => and True (@Equal (sgroup_set (monoid_sgroup M')) y (@Ap (sgroup_set (monoid_sgroup M)) (sgroup_set (monoid_sgroup M')) (@sgroup_map (monoid_sgroup M) (monoid_sgroup M') (@monoid_sgroup_hom M M' f)) x0)))), @ex (Carrier (sgroup_set (monoid_sgroup M))) (fun x0 : Carrier (sgroup_set (monoid_sgroup M)) => and True (@Equal (sgroup_set (monoid_sgroup M')) (sgroup_law (monoid_sgroup M') x y) (@Ap (sgroup_set (monoid_sgroup M)) (sgroup_set (monoid_sgroup M')) (@sgroup_map (monoid_sgroup M) (monoid_sgroup M') (@monoid_sgroup_hom M M' f)) x0))) *)
(* Goal: @in_part (sgroup_set (monoid_sgroup M')) (@monoid_unit (monoid_sgroup M') (monoid_on_def M')) (@image_map (sgroup_set (monoid_sgroup M)) (sgroup_set (monoid_sgroup M')) (@sgroup_map (monoid_sgroup M) (monoid_sgroup M') (@monoid_sgroup_hom M M' f))) *)
intros x y H' H'0; try assumption.
(* Goal: @ex (Carrier (sgroup_set (monoid_sgroup M))) (fun x0 : Carrier (sgroup_set (monoid_sgroup M)) => and True (@Equal (sgroup_set (monoid_sgroup M')) (sgroup_law (monoid_sgroup M') x y) (@Ap (sgroup_set (monoid_sgroup M)) (sgroup_set (monoid_sgroup M')) (@sgroup_map (monoid_sgroup M) (monoid_sgroup M') (@monoid_sgroup_hom M M' f)) x0))) *)
(* Goal: @in_part (sgroup_set (monoid_sgroup M')) (@monoid_unit (monoid_sgroup M') (monoid_on_def M')) (@image_map (sgroup_set (monoid_sgroup M)) (sgroup_set (monoid_sgroup M')) (@sgroup_map (monoid_sgroup M) (monoid_sgroup M') (@monoid_sgroup_hom M M' f))) *)
elim H'0; intros x0 E; elim E; intros H'1 H'2; try exact H'1; clear E H'0.
(* Goal: @ex (Carrier (sgroup_set (monoid_sgroup M))) (fun x0 : Carrier (sgroup_set (monoid_sgroup M)) => and True (@Equal (sgroup_set (monoid_sgroup M')) (sgroup_law (monoid_sgroup M') x y) (@Ap (sgroup_set (monoid_sgroup M)) (sgroup_set (monoid_sgroup M')) (@sgroup_map (monoid_sgroup M) (monoid_sgroup M') (@monoid_sgroup_hom M M' f)) x0))) *)
(* Goal: @in_part (sgroup_set (monoid_sgroup M')) (@monoid_unit (monoid_sgroup M') (monoid_on_def M')) (@image_map (sgroup_set (monoid_sgroup M)) (sgroup_set (monoid_sgroup M')) (@sgroup_map (monoid_sgroup M) (monoid_sgroup M') (@monoid_sgroup_hom M M' f))) *)
elim H'; intros x1 E; elim E; intros H'0 H'3; try exact H'0; clear E H'.
(* Goal: @ex (Carrier (sgroup_set (monoid_sgroup M))) (fun x0 : Carrier (sgroup_set (monoid_sgroup M)) => and True (@Equal (sgroup_set (monoid_sgroup M')) (sgroup_law (monoid_sgroup M') x y) (@Ap (sgroup_set (monoid_sgroup M)) (sgroup_set (monoid_sgroup M')) (@sgroup_map (monoid_sgroup M) (monoid_sgroup M') (@monoid_sgroup_hom M M' f)) x0))) *)
(* Goal: @in_part (sgroup_set (monoid_sgroup M')) (@monoid_unit (monoid_sgroup M') (monoid_on_def M')) (@image_map (sgroup_set (monoid_sgroup M)) (sgroup_set (monoid_sgroup M')) (@sgroup_map (monoid_sgroup M) (monoid_sgroup M') (@monoid_sgroup_hom M M' f))) *)
exists (sgroup_law M x1 x0); split; [ try assumption | idtac ].
apply
 Trans
  with
    (sgroup_law M' (Ap (sgroup_map (monoid_sgroup_hom f)) x1)
       (Ap (sgroup_map (monoid_sgroup_hom f)) x0)); 
(* Goal: @Equal (sgroup_set (monoid_sgroup M')) (@monoid_unit (monoid_sgroup M') (monoid_on_def M')) (@Ap (sgroup_set (monoid_sgroup M)) (sgroup_set (monoid_sgroup M')) (@sgroup_map (monoid_sgroup M) (monoid_sgroup M') (@monoid_sgroup_hom M M' f)) (@monoid_unit (monoid_sgroup M) (monoid_on_def M))) *)
 auto with algebra.
(* Goal: forall (y : Carrier (sgroup_set (monoid_sgroup M'))) (_ : @in_part (sgroup_set (monoid_sgroup M')) y (@subsgroup_part (monoid_sgroup M') (@submonoid_subsgroup M' image_monoid_hom))), @ex (Carrier (sgroup_set (monoid_sgroup M))) (fun x : Carrier (sgroup_set (monoid_sgroup M)) => @Equal (sgroup_set (monoid_sgroup M')) y (@Ap (sgroup_set (monoid_sgroup M)) (sgroup_set (monoid_sgroup M')) (@sgroup_map (monoid_sgroup M) (monoid_sgroup M') (@monoid_sgroup_hom M M' f)) x)) *)
simpl in |- *.
(* Goal: @ex (Carrier (sgroup_set (monoid_sgroup M))) (fun x : Carrier (sgroup_set (monoid_sgroup M)) => and True (@Equal (sgroup_set (monoid_sgroup M')) (@monoid_unit (monoid_sgroup M') (monoid_on_def M')) (@Ap (sgroup_set (monoid_sgroup M)) (sgroup_set (monoid_sgroup M')) (@sgroup_map (monoid_sgroup M) (monoid_sgroup M') (@monoid_sgroup_hom M M' f)) x))) *)
exists (monoid_unit M); split; [ try assumption | idtac ].
(* Goal: @Equal (sgroup_set (monoid_sgroup M')) (@monoid_unit (monoid_sgroup M') (monoid_on_def M')) (@Ap (sgroup_set (monoid_sgroup M)) (sgroup_set (monoid_sgroup M')) (@sgroup_map (monoid_sgroup M) (monoid_sgroup M') (@monoid_sgroup_hom M M' f)) (@monoid_unit (monoid_sgroup M) (monoid_on_def M))) *)
auto with algebra.
(* Goal: @Equal (sgroup_set (monoid_sgroup M')) (@monoid_unit (monoid_sgroup M') (monoid_on_def M')) (@Ap (sgroup_set (monoid_sgroup M)) (sgroup_set (monoid_sgroup M')) (@sgroup_map (monoid_sgroup M) (monoid_sgroup M') (@monoid_sgroup_hom M M' f)) (@monoid_unit (monoid_sgroup M) (monoid_on_def M))) *)
auto with algebra.
Defined.

Lemma image_monoid_prop : forall x : M, in_part (f x) image_monoid_hom.
(* Goal: forall (y : Carrier (sgroup_set (monoid_sgroup M'))) (_ : @in_part (sgroup_set (monoid_sgroup M')) y (@subsgroup_part (monoid_sgroup M') (@submonoid_subsgroup M' image_monoid_hom))), @ex (Carrier (sgroup_set (monoid_sgroup M))) (fun x : Carrier (sgroup_set (monoid_sgroup M)) => @Equal (sgroup_set (monoid_sgroup M')) y (@Ap (sgroup_set (monoid_sgroup M)) (sgroup_set (monoid_sgroup M')) (@sgroup_map (monoid_sgroup M) (monoid_sgroup M') (@monoid_sgroup_hom M M' f)) x)) *)
simpl in |- *.
(* Goal: @Equal (sgroup_set (monoid_sgroup M')) (@monoid_unit (monoid_sgroup M') (monoid_on_def M')) (@Ap (sgroup_set (monoid_sgroup M)) (sgroup_set (monoid_sgroup M')) (@sgroup_map (monoid_sgroup M) (monoid_sgroup M') (@monoid_sgroup_hom M M' f)) (@monoid_unit (monoid_sgroup M) (monoid_on_def M))) *)
intros x; exists x; split; [ try assumption | idtac ]; auto with algebra.
Qed.

Lemma image_monoid_prop_rev :
 forall y : M', in_part y image_monoid_hom -> exists x : M, Equal y (f x).
(* Goal: forall (y : Carrier (sgroup_set (monoid_sgroup M'))) (_ : @in_part (sgroup_set (monoid_sgroup M')) y (@subsgroup_part (monoid_sgroup M') (@submonoid_subsgroup M' image_monoid_hom))), @ex (Carrier (sgroup_set (monoid_sgroup M))) (fun x : Carrier (sgroup_set (monoid_sgroup M)) => @Equal (sgroup_set (monoid_sgroup M')) y (@Ap (sgroup_set (monoid_sgroup M)) (sgroup_set (monoid_sgroup M')) (@sgroup_map (monoid_sgroup M) (monoid_sgroup M') (@monoid_sgroup_hom M M' f)) x)) *)
simpl in |- *.
(* Goal: forall (y : Carrier (sgroup_set (monoid_sgroup M'))) (_ : @ex (Carrier (sgroup_set (monoid_sgroup M))) (fun x : Carrier (sgroup_set (monoid_sgroup M)) => and True (@Equal (sgroup_set (monoid_sgroup M')) y (@Ap (sgroup_set (monoid_sgroup M)) (sgroup_set (monoid_sgroup M')) (@sgroup_map (monoid_sgroup M) (monoid_sgroup M') (@monoid_sgroup_hom M M' f)) x)))), @ex (Carrier (sgroup_set (monoid_sgroup M))) (fun x : Carrier (sgroup_set (monoid_sgroup M)) => @Equal (sgroup_set (monoid_sgroup M')) y (@Ap (sgroup_set (monoid_sgroup M)) (sgroup_set (monoid_sgroup M')) (@sgroup_map (monoid_sgroup M) (monoid_sgroup M') (@monoid_sgroup_hom M M' f)) x)) *)
intros y H'; try assumption.
(* Goal: @ex (Carrier (sgroup_set (monoid_sgroup M))) (fun x : Carrier (sgroup_set (monoid_sgroup M)) => @Equal (sgroup_set (monoid_sgroup M')) y (@Ap (sgroup_set (monoid_sgroup M)) (sgroup_set (monoid_sgroup M')) (@sgroup_map (monoid_sgroup M) (monoid_sgroup M') (@monoid_sgroup_hom M M' f)) x)) *)
elim H'; intros x E; elim E; intros H'0 H'1; try exact H'0; clear E H'.
(* Goal: @ex (Carrier (sgroup_set (monoid_sgroup M))) (fun x : Carrier (sgroup_set (monoid_sgroup M)) => @Equal (sgroup_set (monoid_sgroup M')) y (@Ap (sgroup_set (monoid_sgroup M)) (sgroup_set (monoid_sgroup M')) (@sgroup_map (monoid_sgroup M) (monoid_sgroup M') (@monoid_sgroup_hom M M' f)) x)) *)
exists x; try assumption.
Qed.
End Image_hom.
Hint Resolve image_monoid_prop image_monoid_prop: algebra.