syntactic congruence
Let be a semigroup and let .
The relation
(1) |
is called the syntactic congruence of .
The quotient is called the syntactic semigroup of ,
and the natural morphism
is called the syntactic morphism of .
If is a monoid, then is also a monoid,
called the syntactic monoid of .
As an example,
if and
then if ,
and the syntactic monoid is isomorphic to the cyclic group
of order three.
It is straightforward that
is an equivalence relation and is union of classes of .
To prove that it is a congruence
, let
satisfy and .
Let be arbitrary.
Then iff because ,
and iff because .
Then since and are arbitrary.
The syntactic congruence is both left- and right-invariant, i.e., if , then and for any .
The syntactic congruence is maximal in the following sense:
-
•
if is a congruence over and is union of classes of ,
-
•
then implies .
In fact, let : since and is a congruence, . However, is union of classes of , therefore and are either both in or both outside . This is true for all , thus .
Title | syntactic congruence |
---|---|
Canonical name | SyntacticCongruence |
Date of creation | 2013-03-22 18:52:08 |
Last modified on | 2013-03-22 18:52:08 |
Owner | Ziosilvio (18733) |
Last modified by | Ziosilvio (18733) |
Numerical id | 6 |
Author | Ziosilvio (18733) |
Entry type | Definition |
Classification | msc 68Q70 |
Classification | msc 20M35 |
Defines | syntactic semigroup |
Defines | syntactic monoid |
Defines | syntactic morphism |
Defines | maximality property of syntactic congruence |