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 #
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
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
Membership in S respects the syntactic congruence of S, since a supremum of congruences is
their supremum as equivalence relations.
The syntactic congruence of S is the greatest congruence of which S is a union of
classes.
The kernel of f lies below the syntactic congruence of S exactly when S is the preimage
of a set under f.
In a monoid, the syntactic congruence of S identifies u and v when no two-sided context
distinguishes them as members of 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.