Generating transformation semigroups using endomorphisms of preorders, graphs, and tolerances

详细信息    查看全文

• 作者：J.D. Mitchell ; M. Morayne ; Y. Pé ; resse ; M. Quick
• 关键词：Full transformation semigroup ; Subsemigroups closed in the function topology ; Equivalence relation on subsemigroups ; Relative rank ; Endomorphism of binary relations
• 刊名：Annals of Pure and Applied Logic
• 出版年：2010
• 出版时间：September 2010
• 年：2010
• 卷：161
• 期：12
• 页码：1471-1485
• 全文大小：477 K

文摘

Let Ω^Ω be the semigroup of all mappings of a countably infinite set Ω. If U and V are subsemigroups of Ω^Ω, then we write U≈V if there exists a finite subset F of Ω^Ω such that the subsemigroup generated by U and F equals that generated by V and F. The relative rank of U in Ω^Ω is the least cardinality of a subset A of Ω^Ω such that the union of U and A generates Ω^Ω. In this paper we study the notions of relative rank and the equivalence ≈ for semigroups of endomorphisms of binary relations on Ω.

The semigroups of endomorphisms of preorders, bipartite graphs, and tolerances on Ω are shown to lie in two equivalence classes under ≈. Moreover such semigroups have relative rank 0, 1, 2, or in Ω^Ω where is the minimum cardinality of a dominating family for . We give examples of preorders, bipartite graphs, and tolerances on Ω where the relative ranks of their endomorphism semigroups in Ω^Ω are 0, 1, 2, and .

We show that the endomorphism semigroups of graphs, in general, fall into at least four classes under ≈ and that there exist graphs where the relative rank of the endomorphism semigroup is 2^₀.