TY - JOUR
T1 - Countable versus uncountable relative ranks in infinite semigroups of transformations and relations
AU - Higgins, PM
AU - Howie, John Mackintosh
AU - Mitchell, James David
AU - Ruskuc, Nikola
PY - 2003/10
Y1 - 2003/10
N2 - The relative rank rank(S : A) of a subset A of a semigroup S is the minimum cardinality of a set B such that = S. It follows from a result of Sierpinski that, if X is infinite, the relative rank of a subset of the full transformation semigroup T-X is either uncountable or at most 2. A similar result holds for the semigroup B-X of binary relations on X.A subset S of T-N is dominated (by U) if there exists a countable subset U of T-N with the property that for each sigma in S there exists mu in U such that isigma less than or equal to imu for all i in N. It is shown that every dominated subset of T-N is of uncountable relative rank. As a consequence, the monoid of all contractions in T-N (mappings alpha with the property that \ialpha - jalpha\ less than or equal to \i - j\ for all i and j) is of uncountable relative rank.It is shown (among other results) that rank(B-X : T-X) = 1 and that rank(B-X : I-X) = 1 (where I-X is the symmetric inverse semigroup on X). By contrast, if S-X is the symmetric group, rank(B-X : S-X) = 2.
AB - The relative rank rank(S : A) of a subset A of a semigroup S is the minimum cardinality of a set B such that = S. It follows from a result of Sierpinski that, if X is infinite, the relative rank of a subset of the full transformation semigroup T-X is either uncountable or at most 2. A similar result holds for the semigroup B-X of binary relations on X.A subset S of T-N is dominated (by U) if there exists a countable subset U of T-N with the property that for each sigma in S there exists mu in U such that isigma less than or equal to imu for all i in N. It is shown that every dominated subset of T-N is of uncountable relative rank. As a consequence, the monoid of all contractions in T-N (mappings alpha with the property that \ialpha - jalpha\ less than or equal to \i - j\ for all i and j) is of uncountable relative rank.It is shown (among other results) that rank(B-X : T-X) = 1 and that rank(B-X : I-X) = 1 (where I-X is the symmetric inverse semigroup on X). By contrast, if S-X is the symmetric group, rank(B-X : S-X) = 2.
KW - transformation semigroups
KW - rank
KW - countable
KW - binary relations
UR - http://www.scopus.com/inward/record.url?scp=0242351056&partnerID=8YFLogxK
U2 - 10.1017/S0013091502000974
DO - 10.1017/S0013091502000974
M3 - Article
SN - 0013-0915
VL - 46
SP - 531
EP - 544
JO - Proceedings of the Edinburgh Mathematical Society
JF - Proceedings of the Edinburgh Mathematical Society
IS - 3
ER -