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 .
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 .
|Date of creation||2013-03-22 18:52:08|
|Last modified on||2013-03-22 18:52:08|
|Last modified by||Ziosilvio (18733)|
|Defines||maximality property of syntactic congruence|