Namespaces
Variants
Actions

Difference between revisions of "Polygon (over a monoid)"

From Encyclopedia of Mathematics
Jump to: navigation, search
m (better)
(Tex done)
 
Line 22: Line 22:
 
for any $f_i \in \Omega$, $a \in A$. If $\Omega$ is the set of input signals for an automaton having set of states $A$, then $A$ is similarly transformed into an $F$-polygon (cf. [[Automata, algebraic theory of]]).
 
for any $f_i \in \Omega$, $a \in A$. If $\Omega$ is the set of input signals for an automaton having set of states $A$, then $A$ is similarly transformed into an $F$-polygon (cf. [[Automata, algebraic theory of]]).
  
A mapping <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073590/p07359032.png" /> of an <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073590/p07359033.png" />-polygon <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073590/p07359034.png" /> into an <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073590/p07359035.png" />-polygon <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073590/p07359036.png" /> is called a homomorphism if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073590/p07359037.png" /> for any <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073590/p07359038.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073590/p07359039.png" />. For <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073590/p07359040.png" /> one arrives at the definition of an endomorphism. All endomorphisms of a polygon <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073590/p07359041.png" /> form a monoid, and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073590/p07359042.png" /> can be considered as a polygon over it.
+
A mapping $\phi$ of an $R$-polygon $A$ into an $R$-polygon $B$ is called a homomorphism if $\phi(\lambda a) = \lambda \phi(a)$ for any $\lambda \in R$ and $a \in A$. For $A=B$ one arrives at the definition of an endomorphism. All endomorphisms of a polygon $A$ form a monoid, and $A$ can be considered as a polygon over it.
  
An equivalence <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073590/p07359043.png" /> on an <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073590/p07359044.png" />-polygon <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073590/p07359045.png" /> is called a congruence if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073590/p07359046.png" /> implies <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073590/p07359047.png" /> for any <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073590/p07359048.png" />. The set of congruence classes of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073590/p07359049.png" /> is naturally transformed into an <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073590/p07359050.png" />-polygon, called a quotient polygon of the polygon <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073590/p07359051.png" /> and denoted by <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073590/p07359052.png" />. If <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073590/p07359053.png" /> is a polygon over <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073590/p07359054.png" />, then in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073590/p07359055.png" /> one can define a relation <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073590/p07359056.png" /> by putting <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073590/p07359057.png" /> if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073590/p07359058.png" /> for all <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073590/p07359059.png" />. The relation <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073590/p07359060.png" /> is a congruence on the monoid <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073590/p07359061.png" />, and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073590/p07359062.png" /> is transformed in a natural fashion into a polygon over the quotient monoid <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073590/p07359063.png" />. If the polygon <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073590/p07359064.png" /> arose from a certain automaton, then this transition is equivalent to identifying identically acting sequences of input signals. In universal algebra one considers the usual constructions of direct and subdirect product, but in addition in polygon theory one may consider a [[Wreath product|wreath product]] construction important in the algebraic theory of automata. The free product (or co-product) of polygons coincides with their disjoint union.
+
An [[equivalence relation]] $\theta$ on an $R$-polygon $A$ is called a congruence if $(a,b) \in \theta$ implies $\lambda a,\lambda b) \in \theta$ for any $\lambda \in R$. The set of congruence classes of $\theta$ is naturally transformed into an $R$-polygon, called a quotient polygon of the polygon $A$ and denoted by $A/\theta$. If $A$ is a polygon over $R$, then in $R$ one can define a relation $\mathop{Ann} A$ by putting $(\lambda,\mu) \in \mathop{Ann} A$  if $\lambda a = \mu a$ for all $a \in A$. The relation $\mathop{Ann} A$ is a congruence on the monoid $R$, and $A$ is transformed in a natural fashion into a polygon over the quotient monoid $R/\mathop{Ann} A$. If the polygon $A$ arose from a certain automaton, then this transition is equivalent to identifying identically acting sequences of input signals. In universal algebra one considers the usual constructions of direct and subdirect product, but in addition in polygon theory one may consider a [[wreath product]] construction important in the algebraic theory of automata. The free product (or co-product) of polygons coincides with their disjoint union.
  
A polygon may be regarded as a non-additive analogue of a module over a ring, which serves as a rich source of problems in the theory of polygons. In particular, a relationship has been established between polygons and radicals in semi-groups (cf. [[Radical in a class of semi-groups|Radical in a class of semi-groups]]), and studies have been made on the relation between the properties of a monoid and those of polygons over them. For example, all left <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073590/p07359065.png" />-polygons are projective if and only if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073590/p07359066.png" /> is a one-element group, while the injectivity of all polygons over a commutative monoid <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073590/p07359067.png" /> is equivalent to the presence in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073590/p07359068.png" /> of a zero and the generation of all its ideals by idempotents (see [[Homological classification of rings|Homological classification of rings]]).
+
A polygon may be regarded as a non-additive analogue of a module over a ring, which serves as a rich source of problems in the theory of polygons. In particular, a relationship has been established between polygons and radicals in semi-groups (cf. [[Radical in a class of semi-groups]]), and studies have been made on the relation between the properties of a monoid and those of polygons over them. For example, all left $R$-polygons are projective if and only if $R$ is a one-element group, while the injectivity of all polygons over a commutative monoid $R$ is equivalent to the presence in $R$ of a [[zero element]] and the generation of all its ideals by [[idempotent]]s (see [[Homological classification of rings]]).
  
If <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073590/p07359069.png" /> is a monoid with zero 0, one can speak of an <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073590/p07359070.png" />-polygon <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073590/p07359071.png" /> with a zero as an <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073590/p07359072.png" />-polygon with a distinguished point <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073590/p07359073.png" /> satisfying <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073590/p07359074.png" /> for all <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073590/p07359075.png" />. The theory of polygons containing zeros has some special features.
+
If $R$ is a monoid with zero 0, one can define an $R$-polygon with zero as a [[pointed set]] $A$ which is an $R$-polygon where the distinguished point $u \in A$ satisfies $0a=u$ for all $a\in A$. The theory of polygons with zero has some special features.
  
Every polygon can be considered as a [[Functor|functor]] from a one-object category into the category of sets.
+
Every polygon can be considered as a [[functor]] from a one-object category into the category of sets.
  
 
====References====
 
====References====
Line 39: Line 39:
 
<TR><TD valign="top">[4]</TD> <TD valign="top">  L.A. Skornyakov,  A.V. Mikhalev,  "Modules"  ''Itogi Nauk. i Tekhn. Alg. Topol. Geom.'' , '''14'''  (1976)  pp. 57–190  (In Russian)</TD></TR>
 
<TR><TD valign="top">[4]</TD> <TD valign="top">  L.A. Skornyakov,  A.V. Mikhalev,  "Modules"  ''Itogi Nauk. i Tekhn. Alg. Topol. Geom.'' , '''14'''  (1976)  pp. 57–190  (In Russian)</TD></TR>
 
</table>
 
</table>
 
 
  
 
====Comments====
 
====Comments====
Line 62: Line 60:
 
<TR><TD valign="top">[b1]</TD> <TD valign="top">  Mati Kilp, Ulrich Knauer, Alexander V. Mikhalev, ''Monoids, Acts and Categories: With Applications to Wreath Products and Graphs'', Walter de Gruyter (2000) ISBN 3110812908</TD></TR>
 
<TR><TD valign="top">[b1]</TD> <TD valign="top">  Mati Kilp, Ulrich Knauer, Alexander V. Mikhalev, ''Monoids, Acts and Categories: With Applications to Wreath Products and Graphs'', Walter de Gruyter (2000) ISBN 3110812908</TD></TR>
 
</table>
 
</table>
 +
 +
{{TEX|done}}

Latest revision as of 11:05, 25 September 2016

$R$-polygon, operand

A non-empty set with a monoid of operators. More precisely, a non-empty set $A$ is called a left polygon over a monoid $R$ if for any $\lambda \in R$ and $a \in A$ the product $\lambda a \in A$ is defined, such that $$ \lambda (\mu a) = (\lambda\mu) a $$ and $$ 1a = a $$ for any $\lambda, \mu \in R$, $a \in A$. A right polygon is defined similarly. Specifying an $R$-polygon $A$ is equivalent to specifying a homomorphism $\phi$ from the monoid $R$ into the monoid of mappings of the set $A$ into itself that transforms 1 to the identity mapping. Here $\lambda a = b$ if and only if $$ \phi(\lambda)a = b \ . $$ In particular, each non-empty set may be considered as a polygon over the monoid of its mappings into itself. Therefore, polygons are closely related to the representation of semi-groups by transformations: cf. Transformation semi-group.

If $A$ is a universal algebra whose signature $\Omega$ contains only unary operations, then $A$ can be converted into a polygon over the free monoid $F$ generated by $\Omega$ by putting $$ f_1 \cdots f_n a = f_1(\cdots(f_n(a)\cdots) $$

for any $f_i \in \Omega$, $a \in A$. If $\Omega$ is the set of input signals for an automaton having set of states $A$, then $A$ is similarly transformed into an $F$-polygon (cf. Automata, algebraic theory of).

A mapping $\phi$ of an $R$-polygon $A$ into an $R$-polygon $B$ is called a homomorphism if $\phi(\lambda a) = \lambda \phi(a)$ for any $\lambda \in R$ and $a \in A$. For $A=B$ one arrives at the definition of an endomorphism. All endomorphisms of a polygon $A$ form a monoid, and $A$ can be considered as a polygon over it.

An equivalence relation $\theta$ on an $R$-polygon $A$ is called a congruence if $(a,b) \in \theta$ implies $\lambda a,\lambda b) \in \theta$ for any $\lambda \in R$. The set of congruence classes of $\theta$ is naturally transformed into an $R$-polygon, called a quotient polygon of the polygon $A$ and denoted by $A/\theta$. If $A$ is a polygon over $R$, then in $R$ one can define a relation $\mathop{Ann} A$ by putting $(\lambda,\mu) \in \mathop{Ann} A$ if $\lambda a = \mu a$ for all $a \in A$. The relation $\mathop{Ann} A$ is a congruence on the monoid $R$, and $A$ is transformed in a natural fashion into a polygon over the quotient monoid $R/\mathop{Ann} A$. If the polygon $A$ arose from a certain automaton, then this transition is equivalent to identifying identically acting sequences of input signals. In universal algebra one considers the usual constructions of direct and subdirect product, but in addition in polygon theory one may consider a wreath product construction important in the algebraic theory of automata. The free product (or co-product) of polygons coincides with their disjoint union.

A polygon may be regarded as a non-additive analogue of a module over a ring, which serves as a rich source of problems in the theory of polygons. In particular, a relationship has been established between polygons and radicals in semi-groups (cf. Radical in a class of semi-groups), and studies have been made on the relation between the properties of a monoid and those of polygons over them. For example, all left $R$-polygons are projective if and only if $R$ is a one-element group, while the injectivity of all polygons over a commutative monoid $R$ is equivalent to the presence in $R$ of a zero element and the generation of all its ideals by idempotents (see Homological classification of rings).

If $R$ is a monoid with zero 0, one can define an $R$-polygon with zero as a pointed set $A$ which is an $R$-polygon where the distinguished point $u \in A$ satisfies $0a=u$ for all $a\in A$. The theory of polygons with zero has some special features.

Every polygon can be considered as a functor from a one-object category into the category of sets.

References

[1] M.A. Arbib (ed.) , Algebraic theory of machines, languages and semigroups , Acad. Press (1968)
[2] A.H. Clifford, G.B. Preston, "Algebraic theory of semi-groups" , 2 , Amer. Math. Soc. (1967)
[3] L.A. Skornyakov, "Generalizations of modules" , Modules , 3 , Novosibirsk (1973) pp. 22–27 (In Russian)
[4] L.A. Skornyakov, A.V. Mikhalev, "Modules" Itogi Nauk. i Tekhn. Alg. Topol. Geom. , 14 (1976) pp. 57–190 (In Russian)

Comments

In the West, left polygons over a monoid $M$ are usually called $M$-sets; the term "operand" is also in use. The category of all $M$-sets ($M$ fixed) forms a topos; but for this it is essential not to exclude (as above) the empty $M$-set.

Without assuming commutativity as above, the monoids all of whose non-empty left polygons (or, all of whose pointed left polygons) are injective have a few characterizations, which are reviewed in [a3]. As noted above, there are no non-trivial monoids all of whose left polygons are projective, but the perfect monoids, defined (like perfect rings, cf. Perfect ring) by every left polygon having a projective covering, are non-trivial; see [a1], [a2].

References

[a1] J. Fountain, "Perfect semigroups" Proc. Edinburgh Math. Soc. , 20 (1976) pp. 87–93
[a2] J. Isbell, "Perfect monoids" Semigroup Forum , 2 (1971) pp. 95–118
[a3] R.W. Yoh, "Congruence relations on left canonic semigroups" Semigroup Forum (1977) pp. 175–183
[a4] S. Eilenberg, "Automata, languages and machines" , Acad. Press (1974)

Comments

The terms monoid action or monoid act, or action of a monoid on a set are also common, as is act for the set acted on; see [b1].

References

[b1] Mati Kilp, Ulrich Knauer, Alexander V. Mikhalev, Monoids, Acts and Categories: With Applications to Wreath Products and Graphs, Walter de Gruyter (2000) ISBN 3110812908
How to Cite This Entry:
Polygon (over a monoid). Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Polygon_(over_a_monoid)&oldid=37003
This article was adapted from an original article by L.A. Skornyakov (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article