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 <A boolean OR B> = 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 <A boolean OR B> = 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 -