## Abstract

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 *d* in Ω^{Ω} where *d* is the minimum cardinality of a dominating family for NN. We give examples of preorders, bipartite graphs, and tolerances on Ω where the relative ranks of their endomorphism semigroups in Ω^{Ω} are 0, 1, 2, and *d*.

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^{ℵ0}.

Original language | English |
---|---|

Pages (from-to) | 1471-1485 |

Number of pages | 15 |

Journal | Annals of Pure and Applied Logic |

Volume | 161 |

Issue number | 12 |

DOIs | |

Publication status | Published - Sept 2010 |