Normal submonoids

module group-theory.normal-submonoids where
Imports
open import foundation.binary-relations
open import foundation.dependent-pair-types
open import foundation.equivalence-relations
open import foundation.equivalences
open import foundation.functions
open import foundation.identity-types
open import foundation.logical-equivalences
open import foundation.propositions
open import foundation.retractions
open import foundation.sets
open import foundation.subtype-identity-principle
open import foundation.subtypes
open import foundation.universe-levels

open import group-theory.congruence-relations-monoids
open import group-theory.monoids
open import group-theory.saturated-congruence-relations-monoids
open import group-theory.semigroups
open import group-theory.submonoids
open import group-theory.subsets-monoids

Idea

A normal submonoid N of M is a monoid for which there exists a congruence relation ~ on M such that the elements of N are precisely the elements x ~ 1. Such a congruence relation is rarely unique. However, one can show that the normal submonoids form a retract of the type of congruence relations on M, and that the normal submonoids correspond uniquely to saturated congruence relations.

A submonoid N of M is normal if and only if for all x y : M and u : N we have

  xuy ∈ N ⇔ xy ∈ N.

Definitions

Normal submonoids

module _
  {l1 l2 : Level} (M : Monoid l1) (N : Submonoid l2 M)
  where

  is-normal-submonoid-Prop : Prop (l1  l2)
  is-normal-submonoid-Prop =
    Π-Prop
      ( type-Monoid M)
      ( λ x 
        Π-Prop
          ( type-Monoid M)
          ( λ y 
            Π-Prop
              ( type-Monoid M)
              ( λ u 
                function-Prop
                  ( is-in-Submonoid M N u)
                  ( iff-Prop
                    ( subset-Submonoid M N (mul-Monoid M (mul-Monoid M x u) y))
                    ( subset-Submonoid M N (mul-Monoid M x y))))))

  is-normal-Submonoid : UU (l1  l2)
  is-normal-Submonoid = type-Prop is-normal-submonoid-Prop

  is-prop-is-normal-Submonoid : is-prop is-normal-Submonoid
  is-prop-is-normal-Submonoid = is-prop-type-Prop is-normal-submonoid-Prop

Normal-Submonoid :
  {l1 : Level} (l2 : Level)  Monoid l1  UU (l1  lsuc l2)
Normal-Submonoid l2 M = Σ (Submonoid l2 M) (is-normal-Submonoid M)

module _
  {l1 l2 : Level} (M : Monoid l1) (N : Normal-Submonoid l2 M)
  where

  submonoid-Normal-Submonoid : Submonoid l2 M
  submonoid-Normal-Submonoid = pr1 N

  is-normal-Normal-Submonoid : is-normal-Submonoid M submonoid-Normal-Submonoid
  is-normal-Normal-Submonoid = pr2 N

  subset-Normal-Submonoid : subtype l2 (type-Monoid M)
  subset-Normal-Submonoid =
    subset-Submonoid M submonoid-Normal-Submonoid

  is-submonoid-Normal-Submonoid : is-submonoid-Monoid M subset-Normal-Submonoid
  is-submonoid-Normal-Submonoid =
    is-submonoid-Submonoid M submonoid-Normal-Submonoid

  is-in-Normal-Submonoid : type-Monoid M  UU l2
  is-in-Normal-Submonoid =
    is-in-Submonoid M submonoid-Normal-Submonoid

  is-prop-is-in-Normal-Submonoid :
    (x : type-Monoid M)  is-prop (is-in-Normal-Submonoid x)
  is-prop-is-in-Normal-Submonoid =
    is-prop-is-in-Submonoid M submonoid-Normal-Submonoid

  is-closed-under-eq-Normal-Submonoid :
    {x y : type-Monoid M}  is-in-Normal-Submonoid x  (x  y) 
    is-in-Normal-Submonoid y
  is-closed-under-eq-Normal-Submonoid =
    is-closed-under-eq-subtype subset-Normal-Submonoid

  is-closed-under-eq-Normal-Submonoid' :
    {x y : type-Monoid M}  is-in-Normal-Submonoid y 
    (x  y)  is-in-Normal-Submonoid x
  is-closed-under-eq-Normal-Submonoid' =
    is-closed-under-eq-subtype' subset-Normal-Submonoid

  type-Normal-Submonoid : UU (l1  l2)
  type-Normal-Submonoid = type-Submonoid M submonoid-Normal-Submonoid

  is-set-type-Normal-Submonoid : is-set type-Normal-Submonoid
  is-set-type-Normal-Submonoid =
    is-set-type-Submonoid M submonoid-Normal-Submonoid

  set-Normal-Submonoid : Set (l1  l2)
  set-Normal-Submonoid = set-Submonoid M submonoid-Normal-Submonoid

  inclusion-Normal-Submonoid : type-Normal-Submonoid  type-Monoid M
  inclusion-Normal-Submonoid = inclusion-Submonoid M submonoid-Normal-Submonoid

  ap-inclusion-Normal-Submonoid :
    (x y : type-Normal-Submonoid)  x  y 
    inclusion-Normal-Submonoid x  inclusion-Normal-Submonoid y
  ap-inclusion-Normal-Submonoid =
    ap-inclusion-Submonoid M submonoid-Normal-Submonoid

  is-in-submonoid-inclusion-Normal-Submonoid :
    (x : type-Normal-Submonoid) 
    is-in-Normal-Submonoid (inclusion-Normal-Submonoid x)
  is-in-submonoid-inclusion-Normal-Submonoid =
    is-in-submonoid-inclusion-Submonoid M submonoid-Normal-Submonoid

  contains-unit-Normal-Submonoid : is-in-Normal-Submonoid (unit-Monoid M)
  contains-unit-Normal-Submonoid =
    contains-unit-Submonoid M submonoid-Normal-Submonoid

  unit-Normal-Submonoid : type-Normal-Submonoid
  unit-Normal-Submonoid = unit-Submonoid M submonoid-Normal-Submonoid

  is-closed-under-mul-Normal-Submonoid :
    {x y : type-Monoid M} 
    is-in-Normal-Submonoid x  is-in-Normal-Submonoid y 
    is-in-Normal-Submonoid (mul-Monoid M x y)
  is-closed-under-mul-Normal-Submonoid =
    is-closed-under-mul-Submonoid M submonoid-Normal-Submonoid

  mul-Normal-Submonoid : (x y : type-Normal-Submonoid)  type-Normal-Submonoid
  mul-Normal-Submonoid = mul-Submonoid M submonoid-Normal-Submonoid

  associative-mul-Normal-Submonoid :
    (x y z : type-Normal-Submonoid) 
    (mul-Normal-Submonoid (mul-Normal-Submonoid x y) z) 
    (mul-Normal-Submonoid x (mul-Normal-Submonoid y z))
  associative-mul-Normal-Submonoid =
    associative-mul-Submonoid M submonoid-Normal-Submonoid

  semigroup-Normal-Submonoid : Semigroup (l1  l2)
  semigroup-Normal-Submonoid =
    semigroup-Submonoid M submonoid-Normal-Submonoid

  left-unit-law-mul-Normal-Submonoid :
    (x : type-Normal-Submonoid) 
    mul-Normal-Submonoid unit-Normal-Submonoid x  x
  left-unit-law-mul-Normal-Submonoid =
    left-unit-law-mul-Submonoid M submonoid-Normal-Submonoid

  right-unit-law-mul-Normal-Submonoid :
    (x : type-Normal-Submonoid) 
    mul-Normal-Submonoid x unit-Normal-Submonoid  x
  right-unit-law-mul-Normal-Submonoid =
    right-unit-law-mul-Submonoid M submonoid-Normal-Submonoid

  monoid-Normal-Submonoid : Monoid (l1  l2)
  monoid-Normal-Submonoid = monoid-Submonoid M submonoid-Normal-Submonoid

Properties

Extensionality of the type of all normal submonoids

module _
  {l1 l2 : Level} (M : Monoid l1) (N : Normal-Submonoid l2 M)
  where

  has-same-elements-Normal-Submonoid :
    {l3 : Level}  Normal-Submonoid l3 M  UU (l1  l2  l3)
  has-same-elements-Normal-Submonoid K =
    has-same-elements-Submonoid M
      ( submonoid-Normal-Submonoid M N)
      ( submonoid-Normal-Submonoid M K)

  extensionality-Normal-Submonoid :
    (K : Normal-Submonoid l2 M) 
    (N  K)  has-same-elements-Normal-Submonoid K
  extensionality-Normal-Submonoid =
    extensionality-type-subtype
      ( is-normal-submonoid-Prop M)
      ( is-normal-Normal-Submonoid M N)
      ( λ x  (id , id))
      ( extensionality-Submonoid M (submonoid-Normal-Submonoid M N))

  eq-has-same-elements-Normal-Submonoid :
    (K : Normal-Submonoid l2 M) 
    has-same-elements-Normal-Submonoid K  N  K
  eq-has-same-elements-Normal-Submonoid K =
    map-inv-equiv (extensionality-Normal-Submonoid K)

The congruence relation of a normal submonoid

module _
  {l1 l2 : Level} (M : Monoid l1) (N : Normal-Submonoid l2 M)
  where

  rel-congruence-Normal-Submonoid : Rel-Prop (l1  l2) (type-Monoid M)
  rel-congruence-Normal-Submonoid x y =
    Π-Prop
      ( type-Monoid M)
      ( λ u 
        Π-Prop
          ( type-Monoid M)
          ( λ v 
            iff-Prop
              ( subset-Normal-Submonoid M N
                ( mul-Monoid M (mul-Monoid M u x) v))
              ( subset-Normal-Submonoid M N
                ( mul-Monoid M (mul-Monoid M u y) v))))

  sim-congruence-Normal-Submonoid : (x y : type-Monoid M)  UU (l1  l2)
  sim-congruence-Normal-Submonoid x y =
    type-Prop (rel-congruence-Normal-Submonoid x y)

  refl-congruence-Normal-Submonoid :
    is-reflexive-Rel-Prop rel-congruence-Normal-Submonoid
  pr1 (refl-congruence-Normal-Submonoid u v) = id
  pr2 (refl-congruence-Normal-Submonoid u v) = id

  symmetric-congruence-Normal-Submonoid :
    is-symmetric-Rel-Prop rel-congruence-Normal-Submonoid
  pr1 (symmetric-congruence-Normal-Submonoid H u v) = pr2 (H u v)
  pr2 (symmetric-congruence-Normal-Submonoid H u v) = pr1 (H u v)

  transitive-congruence-Normal-Submonoid :
    is-transitive-Rel-Prop rel-congruence-Normal-Submonoid
  transitive-congruence-Normal-Submonoid H K u v = (K u v) ∘iff (H u v)

  eq-rel-congruence-Normal-Submonoid : Eq-Rel (l1  l2) (type-Monoid M)
  pr1 eq-rel-congruence-Normal-Submonoid = rel-congruence-Normal-Submonoid
  pr1 (pr2 eq-rel-congruence-Normal-Submonoid) =
    refl-congruence-Normal-Submonoid
  pr1 (pr2 (pr2 eq-rel-congruence-Normal-Submonoid)) =
    symmetric-congruence-Normal-Submonoid
  pr2 (pr2 (pr2 eq-rel-congruence-Normal-Submonoid)) =
    transitive-congruence-Normal-Submonoid

  is-congruence-congruence-Normal-Submonoid :
    is-congruence-Monoid M eq-rel-congruence-Normal-Submonoid
  pr1 (is-congruence-congruence-Normal-Submonoid {x} {x'} {y} {y'} H K u v) L =
    is-closed-under-eq-Normal-Submonoid M N
      ( forward-implication
        ( H u (mul-Monoid M y' v))
        ( is-closed-under-eq-Normal-Submonoid M N
          ( forward-implication
            ( K (mul-Monoid M u x) v)
            ( is-closed-under-eq-Normal-Submonoid M N L
              ( ap (mul-Monoid' M v) (inv (associative-mul-Monoid M u x y)))))
          ( associative-mul-Monoid M (mul-Monoid M u x) y' v)))
      ( ( inv (associative-mul-Monoid M (mul-Monoid M u x') y' v)) 
        ( ap (mul-Monoid' M v) (associative-mul-Monoid M u x' y')))
  pr2 (is-congruence-congruence-Normal-Submonoid {x} {x'} {y} {y'} H K u v) L =
    is-closed-under-eq-Normal-Submonoid M N
      ( backward-implication
        ( H u (mul-Monoid M y v))
        ( is-closed-under-eq-Normal-Submonoid M N
          ( backward-implication
            ( K (mul-Monoid M u x') v)
            ( is-closed-under-eq-Normal-Submonoid M N L
              ( ap (mul-Monoid' M v) (inv (associative-mul-Monoid M u x' y')))))
          ( associative-mul-Monoid M (mul-Monoid M u x') y v)))
      ( ( inv (associative-mul-Monoid M (mul-Monoid M u x) y v)) 
        ( ap (mul-Monoid' M v) (associative-mul-Monoid M u x y)))

  congruence-Normal-Submonoid : congruence-Monoid (l1  l2) M
  pr1 congruence-Normal-Submonoid = eq-rel-congruence-Normal-Submonoid
  pr2 congruence-Normal-Submonoid = is-congruence-congruence-Normal-Submonoid

The normal submonoid obtained from a congruence relation

module _
  {l1 l2 : Level} (M : Monoid l1) (R : congruence-Monoid l2 M)
  where

  subset-normal-submonoid-congruence-Monoid :
    subtype l2 (type-Monoid M)
  subset-normal-submonoid-congruence-Monoid x =
    prop-congruence-Monoid M R x (unit-Monoid M)

  is-in-normal-submonoid-congruence-Monoid : type-Monoid M  UU l2
  is-in-normal-submonoid-congruence-Monoid =
    is-in-subtype subset-normal-submonoid-congruence-Monoid

  contains-unit-normal-submonoid-congruence-Monoid :
    is-in-normal-submonoid-congruence-Monoid (unit-Monoid M)
  contains-unit-normal-submonoid-congruence-Monoid =
    refl-congruence-Monoid M R

  is-closed-under-multiplication-normal-submonoid-congruence-Monoid :
    is-closed-under-multiplication-subset-Monoid M
      subset-normal-submonoid-congruence-Monoid
  is-closed-under-multiplication-normal-submonoid-congruence-Monoid x y H K =
    concatenate-sim-eq-congruence-Monoid M R
      ( mul-congruence-Monoid M R H K)
      ( left-unit-law-mul-Monoid M (unit-Monoid M))

  submonoid-congruence-Monoid : Submonoid l2 M
  pr1 submonoid-congruence-Monoid = subset-normal-submonoid-congruence-Monoid
  pr1 (pr2 submonoid-congruence-Monoid) =
    contains-unit-normal-submonoid-congruence-Monoid
  pr2 (pr2 submonoid-congruence-Monoid) =
    is-closed-under-multiplication-normal-submonoid-congruence-Monoid

  is-normal-submonoid-congruence-Monoid :
    is-normal-Submonoid M submonoid-congruence-Monoid
  pr1 (is-normal-submonoid-congruence-Monoid x y u H) =
    trans-congruence-Monoid M R
      ( symm-congruence-Monoid M R
        ( mul-congruence-Monoid M R
          ( concatenate-sim-eq-congruence-Monoid M R
            ( mul-congruence-Monoid M R (refl-congruence-Monoid M R) H)
            ( right-unit-law-mul-Monoid M x))
          ( refl-congruence-Monoid M R)))
  pr2 (is-normal-submonoid-congruence-Monoid x y u H) =
    trans-congruence-Monoid M R
      ( mul-congruence-Monoid M R
        ( concatenate-sim-eq-congruence-Monoid M R
          ( mul-congruence-Monoid M R (refl-congruence-Monoid M R) H)
          ( right-unit-law-mul-Monoid M x))
        ( refl-congruence-Monoid M R))

  normal-submonoid-congruence-Monoid : Normal-Submonoid l2 M
  pr1 normal-submonoid-congruence-Monoid = submonoid-congruence-Monoid
  pr2 normal-submonoid-congruence-Monoid = is-normal-submonoid-congruence-Monoid

The normal submonoid obtained from the congruence relation of a normal submonoid has the same elements as the original normal submonoid

module _
  {l1 l2 : Level} (M : Monoid l1) (N : Normal-Submonoid l2 M)
  where

  has-same-elements-normal-submonoid-congruence-Normal-Submonoid :
    has-same-elements-Normal-Submonoid M
      ( normal-submonoid-congruence-Monoid M
        ( congruence-Normal-Submonoid M N))
      ( N)
  pr1 (has-same-elements-normal-submonoid-congruence-Normal-Submonoid x) H =
    is-closed-under-eq-Normal-Submonoid M N
      ( backward-implication
        ( H (unit-Monoid M) (unit-Monoid M))
        ( is-closed-under-eq-Normal-Submonoid' M N
          ( contains-unit-Normal-Submonoid M N)
          ( ( right-unit-law-mul-Monoid M
              ( mul-Monoid M (unit-Monoid M) (unit-Monoid M))) 
            ( left-unit-law-mul-Monoid M (unit-Monoid M)))))
      ( right-unit-law-mul-Monoid M _  left-unit-law-mul-Monoid M _)
  pr1
    ( pr2
      ( has-same-elements-normal-submonoid-congruence-Normal-Submonoid x)
      ( H)
      ( u)
      ( v))
    ( K) =
    is-closed-under-eq-Normal-Submonoid' M N
      ( forward-implication (is-normal-Normal-Submonoid M N u v x H) K)
      ( ap (mul-Monoid' M v) (right-unit-law-mul-Monoid M u))
  pr2
    ( pr2
      ( has-same-elements-normal-submonoid-congruence-Normal-Submonoid x)
      ( H)
      ( u)
      ( v))
    ( K) =
    backward-implication
      ( is-normal-Normal-Submonoid M N u v x H)
      ( is-closed-under-eq-Normal-Submonoid M N K
        ( ap (mul-Monoid' M v) (right-unit-law-mul-Monoid M u)))

The congruence relation of a normal submonoid is saturated

module _
  {l1 l2 : Level} (M : Monoid l1) (N : Normal-Submonoid l2 M)
  where

  is-saturated-congruence-Normal-Submonoid :
    is-saturated-congruence-Monoid M (congruence-Normal-Submonoid M N)
  is-saturated-congruence-Normal-Submonoid x y H u v =
    ( ( has-same-elements-normal-submonoid-congruence-Normal-Submonoid M N
        ( mul-Monoid M (mul-Monoid M u y) v)) ∘iff
      ( H u v)) ∘iff
    ( inv-iff
      ( has-same-elements-normal-submonoid-congruence-Normal-Submonoid M N
        ( mul-Monoid M (mul-Monoid M u x) v)))

  saturated-congruence-Normal-Submonoid :
    saturated-congruence-Monoid (l1  l2) M
  pr1 saturated-congruence-Normal-Submonoid = congruence-Normal-Submonoid M N
  pr2 saturated-congruence-Normal-Submonoid =
    is-saturated-congruence-Normal-Submonoid

The congruence relation of the normal submonoid associated to a congruence relation relates the same elements as the original congruence relation

module _
  {l1 l2 : Level} (M : Monoid l1) (R : saturated-congruence-Monoid l2 M)
  where

  normal-submonoid-saturated-congruence-Monoid :
    Normal-Submonoid l2 M
  normal-submonoid-saturated-congruence-Monoid =
    normal-submonoid-congruence-Monoid M
      ( congruence-saturated-congruence-Monoid M R)

  relate-same-elements-congruence-normal-submonoid-saturated-congruence-Monoid :
    relate-same-elements-saturated-congruence-Monoid M
      ( saturated-congruence-Normal-Submonoid M
        ( normal-submonoid-saturated-congruence-Monoid))
      ( R)
  pr1
    ( relate-same-elements-congruence-normal-submonoid-saturated-congruence-Monoid
      x y)
    H =
    is-saturated-saturated-congruence-Monoid M R x y H
  pr1
    ( pr2
      ( relate-same-elements-congruence-normal-submonoid-saturated-congruence-Monoid
        x y)
      H u v) =
    trans-saturated-congruence-Monoid M R
      ( mul-saturated-congruence-Monoid M R
        ( mul-saturated-congruence-Monoid M R
          ( refl-saturated-congruence-Monoid M R)
          ( symm-saturated-congruence-Monoid M R H))
        ( refl-saturated-congruence-Monoid M R))
  pr2
    ( pr2
      ( relate-same-elements-congruence-normal-submonoid-saturated-congruence-Monoid
        x y)
      H u v) =
    trans-saturated-congruence-Monoid M R
      ( mul-saturated-congruence-Monoid M R
        ( mul-saturated-congruence-Monoid M R
          ( refl-saturated-congruence-Monoid M R)
          ( H))
        ( refl-saturated-congruence-Monoid M R))

The type of normal submonoids of M is a retract of the type of congruence relations of M

issec-congruence-Normal-Submonoid :
  {l1 : Level} (l2 : Level) (M : Monoid l1) (N : Normal-Submonoid (l1  l2) M) 
  ( normal-submonoid-congruence-Monoid M (congruence-Normal-Submonoid M N)) 
  ( N)
issec-congruence-Normal-Submonoid l2 M N =
  eq-has-same-elements-Normal-Submonoid M
    ( normal-submonoid-congruence-Monoid M (congruence-Normal-Submonoid M N))
    ( N)
    ( has-same-elements-normal-submonoid-congruence-Normal-Submonoid M N)

normal-submonoid-retract-of-congruence-Monoid :
  {l1 : Level} (l2 : Level) (M : Monoid l1) 
  (Normal-Submonoid (l1  l2) M) retract-of (congruence-Monoid (l1  l2) M)
pr1 (normal-submonoid-retract-of-congruence-Monoid l2 M) =
  congruence-Normal-Submonoid M
pr1 (pr2 (normal-submonoid-retract-of-congruence-Monoid l2 M)) =
  normal-submonoid-congruence-Monoid M
pr2 (pr2 (normal-submonoid-retract-of-congruence-Monoid l2 M)) =
  issec-congruence-Normal-Submonoid l2 M

The type of normal submonoids of M is equivalent to the type of saturated congruence relations on M

issec-saturated-congruence-Normal-Submonoid :
  {l1 : Level} (l2 : Level) (M : Monoid l1) (N : Normal-Submonoid (l1  l2) M) 
  ( normal-submonoid-saturated-congruence-Monoid M
    ( saturated-congruence-Normal-Submonoid M N)) 
  ( N)
issec-saturated-congruence-Normal-Submonoid l2 M N =
  eq-has-same-elements-Normal-Submonoid M
    ( normal-submonoid-saturated-congruence-Monoid M
      ( saturated-congruence-Normal-Submonoid M N))
    ( N)
    ( has-same-elements-normal-submonoid-congruence-Normal-Submonoid M N)

isretr-saturated-congruence-Normal-Submonoid :
  {l1 : Level} (l2 : Level) (M : Monoid l1)
  (R : saturated-congruence-Monoid (l1  l2) M) 
  ( saturated-congruence-Normal-Submonoid M
    ( normal-submonoid-saturated-congruence-Monoid M R)) 
  ( R)
isretr-saturated-congruence-Normal-Submonoid l2 M R =
  eq-relate-same-elements-saturated-congruence-Monoid M
    ( saturated-congruence-Normal-Submonoid M
      ( normal-submonoid-saturated-congruence-Monoid M R))
    ( R)
    ( relate-same-elements-congruence-normal-submonoid-saturated-congruence-Monoid
      ( M)
      ( R))

is-equiv-normal-submonoid-saturated-congruence-Monoid :
  {l1 : Level} (l2 : Level) (M : Monoid l1) 
  is-equiv (normal-submonoid-saturated-congruence-Monoid {l2 = l1  l2} M)
is-equiv-normal-submonoid-saturated-congruence-Monoid l2 M =
  is-equiv-has-inverse
    ( saturated-congruence-Normal-Submonoid M)
    ( issec-saturated-congruence-Normal-Submonoid l2 M)
    ( isretr-saturated-congruence-Normal-Submonoid l2 M)

equiv-normal-submonoid-saturated-congruence-Monoid :
  {l1 : Level} (l2 : Level) (M : Monoid l1) 
  saturated-congruence-Monoid (l1  l2) M  Normal-Submonoid (l1  l2) M
pr1 (equiv-normal-submonoid-saturated-congruence-Monoid l2 M) =
  normal-submonoid-saturated-congruence-Monoid M
pr2 (equiv-normal-submonoid-saturated-congruence-Monoid l2 M) =
  is-equiv-normal-submonoid-saturated-congruence-Monoid l2 M

References

  • S. Margolis and J.-É. Pin, Inverse semigroups and extensions of groups by semilattices, J. of Algebra 110 (1987), 277-297.