Is a homomorphism between two groups proper? Here are my definitions for groups and homomorphisms:
Definition associative {ty : Type} (f : ty -> ty -> ty) (eq : ty -> ty -> Prop) :=
forall a b c, eq (f (f a b) c) (f a (f b c)).
Definition identity {ty : Type} (f : ty -> ty -> ty) (eq : ty -> ty -> Prop) (e : ty) :=
forall a, eq (f a e) a /\ eq (f e a) a.
Definition op_inverse {ty : Type} (f : ty -> ty -> ty) (eq : ty -> ty -> Prop) (e a a' : ty) :=
eq (f a a') e /\ eq (f a' a) e.
Definition op_invertible {ty : Type} (f : ty -> ty -> ty) (eq : ty -> ty -> Prop) (e : ty) :=
forall a, exists a', op_inverse f eq e a a'.
Record Group : Type := Group'
{ ty :> Type
; op : ty -> ty -> ty
; eqr : ty -> ty -> Prop
; e : ty
; eq_rel :> Equivalence eqr
; prop_op :> Proper (eqr ==> eqr ==> eqr) op
; assoc_op : associative op eqr
; id_op : identity op eqr e
; inv_op : op_invertible op eqr e
}.
Notation "A <.> B" := ((op _) A B) (at level 50).
Notation "A =.= B" := ((eqr _) A B) (at level 50).
Definition homomorphism {G H : Group} (f : G -> H) :=
forall x y, f (x <.> y) =.= (f x <.> f y).
I want to prove:
Lemma homo_is_proper : forall {G H : Group} (f : ty G -> ty H),
homomorphism f -> Proper (eqr G ==> eqr H) f.
Is this necessarily true?
It's not true.
Let H
be a non-trivial group (e.g., Z/2Z
), define G
as the quotient of H
under the total relation eqr := fun _ _ => True
(G
is thus isomorphic to the trivial group), and f : ty G -> ty H
is the identity function. f
satisfies homomorphism
but it's not proper.
In general, to reflect common mathematical practice, when working with setoids, properness is a basic fact that must be proved from first principles, and that the rest of a theory rests upon. Arguably, homo_is_proper
is not a natural question to ask, because all theorems and properties (such as homomorphism
) should really be parameterized only by proper functions in the first place.