Documentation

Linglib.Core.GroupTheory.Congruence.Syntactic

The syntactic congruence of a subset #

The syntactic congruence of a subset S of a magma is the greatest congruence of which S is a union of classes, so the kernel of a homomorphism lies below it exactly when S is the preimage of a set. In a monoid it identifies u and v when no two-sided context tells them apart, that is when $xuy \in S \iff xvy \in S$ for all x and y. It commutes with inverse images along a homomorphism whose range and 1 cover the target, as a surjection's does and as the embedding of a semigroup in the monoid with an identity adjoined does. Over a free monoid or a free semigroup it is the syntactic congruence of a language.

Implementation notes #

The congruence is defined by its universal property, so one definition serves magmas, semigroups and monoids, and the description by contexts is a theorem where contexts exist.

References #

def Con.syntactic {M : Type u_1} [Mul M] (S : Set M) :
Con M

The syntactic congruence of S is the greatest congruence of which S is a union of classes.

Equations
  • Con.syntactic S = sSup {c : Con M | ∀ ⦃u v : M⦄, c u v → (u ∈ S ↔ v ∈ S)}
Instances For
    def AddCon.syntactic {M : Type u_1} [Add M] (S : Set M) :
    AddCon M

    The syntactic congruence of S is the greatest additive congruence of which S is a union of classes.

    Equations
    • AddCon.syntactic S = sSup {c : AddCon M | ∀ ⦃u v : M⦄, c u v → (u ∈ S ↔ v ∈ S)}
    Instances For
      theorem Con.mem_iff_of_syntactic {M : Type u_1} [Mul M] {S : Set M} {u v : M} (h : (syntactic S) u v) :
      u ∈ S ↔ v ∈ S

      Membership in S respects the syntactic congruence of S, since a supremum of congruences is their supremum as equivalence relations.

      theorem AddCon.mem_iff_of_syntactic {M : Type u_1} [Add M] {S : Set M} {u v : M} (h : (syntactic S) u v) :
      u ∈ S ↔ v ∈ S
      theorem Con.le_syntactic_iff {M : Type u_1} [Mul M] {S : Set M} {c : Con M} :
      c ≤ syntactic S ↔ ∀ ⦃u v : M⦄, c u v → (u ∈ S ↔ v ∈ S)

      The syntactic congruence of S is the greatest congruence of which S is a union of classes.

      theorem AddCon.le_syntactic_iff {M : Type u_1} [Add M] {S : Set M} {c : AddCon M} :
      c ≤ syntactic S ↔ ∀ ⦃u v : M⦄, c u v → (u ∈ S ↔ v ∈ S)
      theorem Con.ker_le_syntactic_iff {M : Type u_1} {N : Type u_2} {F : Type u_3} [Mul M] [Mul N] [FunLike F M N] [MulHomClass F M N] {S : Set M} {f : F} :
      ker f ≤ syntactic S ↔ ∃ (P : Set N), S = ⇑f ⁻¹' P

      The kernel of f lies below the syntactic congruence of S exactly when S is the preimage of a set under f.

      theorem AddCon.ker_le_syntactic_iff {M : Type u_1} {N : Type u_2} {F : Type u_3} [Add M] [Add N] [FunLike F M N] [AddHomClass F M N] {S : Set M} {f : F} :
      ker f ≤ syntactic S ↔ ∃ (P : Set N), S = ⇑f ⁻¹' P
      @[simp]
      theorem Con.syntactic_compl {M : Type u_1} [Mul M] {S : Set M} :
      @[simp]
      theorem AddCon.syntactic_compl {M : Type u_1} [Add M] {S : Set M} :
      theorem Con.inf_le_syntactic_inter {M : Type u_1} [Mul M] {S T : Set M} :
      syntactic S ⊓ syntactic T ≤ syntactic (S ∩ T)
      theorem AddCon.inf_le_syntactic_inter {M : Type u_1} [Add M] {S T : Set M} :
      syntactic S ⊓ syntactic T ≤ syntactic (S ∩ T)
      theorem Con.inf_le_syntactic_union {M : Type u_1} [Mul M] {S T : Set M} :
      syntactic S ⊓ syntactic T ≤ syntactic (S ∪ T)
      theorem AddCon.inf_le_syntactic_union {M : Type u_1} [Add M] {S T : Set M} :
      syntactic S ⊓ syntactic T ≤ syntactic (S ∪ T)
      theorem Con.syntactic_le_syntactic_preimage_mul_left {M : Type u_1} [Mul M] {S : Set M} (a : M) :
      syntactic S ≤ syntactic ((fun (x : M) => a * x) ⁻¹' S)
      theorem AddCon.syntactic_le_syntactic_preimage_add_left {M : Type u_1} [Add M] {S : Set M} (a : M) :
      syntactic S ≤ syntactic ((fun (x : M) => a + x) ⁻¹' S)
      theorem Con.syntactic_le_syntactic_preimage_mul_right {M : Type u_1} [Mul M] {S : Set M} (a : M) :
      syntactic S ≤ syntactic ((fun (x : M) => x * a) ⁻¹' S)
      theorem AddCon.syntactic_le_syntactic_preimage_add_right {M : Type u_1} [Add M] {S : Set M} (a : M) :
      syntactic S ≤ syntactic ((fun (x : M) => x + a) ⁻¹' S)
      theorem Con.syntactic_iff {M : Type u_1} [Monoid M] {S : Set M} {u v : M} :
      (syntactic S) u v ↔ ∀ (x y : M), x * u * y ∈ S ↔ x * v * y ∈ S

      In a monoid, the syntactic congruence of S identifies u and v when no two-sided context distinguishes them as members of S.

      theorem AddCon.syntactic_iff {M : Type u_1} [AddMonoid M] {S : Set M} {u v : M} :
      (syntactic S) u v ↔ ∀ (x y : M), x + u + y ∈ S ↔ x + v + y ∈ S
      theorem Con.comap_syntactic {M : Type u_1} {N : Type u_2} {F : Type u_3} [Mul M] [Monoid N] [FunLike F M N] [MulHomClass F M N] {f : F} (hf : ∀ (y : N), y = 1 ∨ y ∈ Set.range ⇑f) (S : Set N) :
      comap ⇑f ⋯ (syntactic S) = syntactic (⇑f ⁻¹' S)

      The syntactic congruence of an inverse image is the inverse image of the syntactic congruence, along a homomorphism whose range and 1 cover its target.

      theorem AddCon.comap_syntactic {M : Type u_1} {N : Type u_2} {F : Type u_3} [Add M] [AddMonoid N] [FunLike F M N] [AddHomClass F M N] {f : F} (hf : ∀ (y : N), y = 0 ∨ y ∈ Set.range ⇑f) (S : Set N) :
      comap ⇑f ⋯ (syntactic S) = syntactic (⇑f ⁻¹' S)