Sets of universal sequences for the symmetric group and analogous semigroups
HTML articles powered by AMS MathViewer
- by J. Hyde, J. Jonušas, J. D. Mitchell and Y. H. Péresse PDF
- Proc. Amer. Math. Soc. 148 (2020), 1917-1931 Request permission
Abstract:
A universal sequence for a group or semigroup $S$ is a sequence of words $w_1, w_2, \ldots$ such that for any sequence $s_1, s_2, \ldots \in S$, the equations $w_n = s_n$, $n\in \mathbb {N}$, can be solved simultaneously in $S$. For example, Galvin showed that the sequence $(a^{-1}(a^nba^{-n})b^{-1}(a^nb^{-1}a^{-n})ba)_{n\in \mathbb {N}}$ is universal for the symmetric group $\operatorname {Sym}(X)$ when $X$ is infinite, and Sierpiński showed that $(a ^2 b ^3 (abab ^3) ^{n + 1} ab ^2 ab ^3)_{n\in \mathbb {N}}$ is universal for the monoid $X ^X$ of functions from the infinite set $X$ to itself.
In this paper, we show that under some conditions, the set of universal sequences for the symmetric group on an infinite set $X$ is independent of the cardinality of $X$. More precisely, we show that if $Y$ is any set such that $|Y| \geq |X|$, then every universal sequence for $\operatorname {Sym}(X)$ is also universal for $\operatorname {Sym}(Y)$. If $|X| > 2 ^{\aleph _0}$, then the converse also holds. It is shown that an analogue of this theorem holds in the context of inverse semigroups, where the role of the symmetric group is played by the symmetric inverse monoid. In the general context of semigroups, the full transformation monoid $X ^X$ is the natural analogue of the symmetric group and the symmetric inverse monoid. If $X$ and $Y$ are arbitrary infinite sets, then it is an open question as to whether or not every sequence that is universal for $X ^X$ is also universal for $Y ^Y$. However, we obtain a sufficient condition for a sequence to be universal for $X ^X$ which does not depend on the cardinality of $X$. A large class of sequences satisfies this condition, and hence is universal for $X ^X$ for every infinite set $X$.
References
- S. Banach, Sur un theorème de M. Sierpiński, Fund. Math., 25:5–6, 1935.
- George M. Bergman, Generating infinite symmetric groups, Bull. London Math. Soc. 38 (2006), no. 3, 429–440. MR 2239037, DOI 10.1112/S0024609305018308
- G. M. Bergman, Problem list from algebras, lattices and varieties: a conference in honor of Walter Taylor, University of Colorado, 15–18 August, 2004. Algebra Universalis, 55(4):509–526, 2006.
- Randall Dougherty and Jan Mycielski, Representations of infinite permutations by words. II, Proc. Amer. Math. Soc. 127 (1999), no. 8, 2233–2243. MR 1605952, DOI 10.1090/S0002-9939-99-04874-1
- M. Droste and J. K. Truss, On representing words in the automorphism group of the random graph, J. Group Theory 9 (2006), no. 6, 815–836. MR 2272720, DOI 10.1515/JGT.2006.053
- Manfred Droste, Classes of universal words for the infinite symmetric groups, Algebra Universalis 20 (1985), no. 2, 205–216. MR 806615, DOI 10.1007/BF01278598
- Manfred Droste and Saharon Shelah, On the universality of systems of words in permutation groups, Pacific J. Math. 127 (1987), no. 2, 321–328. MR 881762, DOI 10.2140/pjm.1987.127.321
- James East, Generation of infinite factorizable inverse monoids, Semigroup Forum 84 (2012), no. 2, 267–283. MR 2898760, DOI 10.1007/s00233-011-9339-1
- James East, Infinite partition monoids, Internat. J. Algebra Comput. 24 (2014), no. 4, 429–460. MR 3227821, DOI 10.1142/S0218196714500209
- James East, Infinite dual symmetric inverse monoids, Period. Math. Hungar. 75 (2017), no. 2, 273–285. MR 3718521, DOI 10.1007/s10998-017-0194-z
- Fred Galvin, Generating countable sets of permutations, J. London Math. Soc. (2) 51 (1995), no. 2, 230–242. MR 1325568, DOI 10.1112/jlms/51.2.230
- John M. Howie, Fundamentals of semigroup theory, London Mathematical Society Monographs. New Series, vol. 12, The Clarendon Press, Oxford University Press, New York, 1995. Oxford Science Publications. MR 1455373
- J. Hyde, J. Jonušas, J. D. Mitchell, and Y. Péresse, Universal sequences for the order-automorphisms of the rationals, J. Lond. Math. Soc. (2) 94 (2016), no. 1, 21–37. MR 3532162, DOI 10.1112/jlms/jdw015
- Alexander S. Kechris and Christian Rosendal, Turbulence, amalgamation, and generic automorphisms of homogeneous structures, Proc. Lond. Math. Soc. (3) 94 (2007), no. 2, 302–350. MR 2308230, DOI 10.1112/plms/pdl007
- Roger C. Lyndon, Words and infinite permutations, Mots, Lang. Raison. Calc., Hermès, Paris, 1990, pp. 143–152. MR 1252660
- V. Maltcev, J. D. Mitchell, and N. Ruškuc, The Bergman property for semigroups, J. Lond. Math. Soc. (2) 80 (2009), no. 1, 212–232. MR 2520386, DOI 10.1112/jlms/jdp025
- George F. McNulty, The decision problem for equational bases of algebras, Ann. Math. Logic 10 (1976), no. 3-4, 193–259. MR 432440, DOI 10.1016/0003-4843(76)90009-7
- J. D. Mitchell and Y. Péresse, Generating countable sets of surjective functions, Fund. Math. 213 (2011), no. 1, 67–93. MR 2794936, DOI 10.4064/fm213-1-4
- Jan Mycielski, Representations of infinite permutations by words, Proc. Amer. Math. Soc. 100 (1987), no. 2, 237–241. MR 884459, DOI 10.1090/S0002-9939-1987-0884459-5
- Oystein Ore, Some remarks on commutators, Proc. Amer. Math. Soc. 2 (1951), 307–314. MR 40298, DOI 10.1090/S0002-9939-1951-0040298-4
- W. Sierpiński, Sur l’approximation des fonctions continues par les superpositions de quatre fonction, Fund. Math., 23:119–120, 1934.
- W. Sierpiński, Sur les suites infinies de fonctions définies dans les ensembles quelconques, Fund. Math., 24:209–212, 1935.
- D. M. Silberger, Are primitive words universal for infinite symmetric groups?, Trans. Amer. Math. Soc. 276 (1983), no. 2, 841–852. MR 688980, DOI 10.1090/S0002-9947-1983-0688980-5
- Walter Taylor, Some universal sets of terms, Trans. Amer. Math. Soc. 267 (1981), no. 2, 595–607. MR 626492, DOI 10.1090/S0002-9947-1981-0626492-3
- J. K. Truss, private communication, 2009.
Additional Information
- J. Hyde
- Affiliation: Cornell University, Ithaca, New York 14850
- MR Author ID: 905762
- Email: jth263@cornell.edu
- J. Jonušas
- Affiliation: TU Wien, Karlsplatz 13, 1040 Wien, Austria
- Email: julius.jonusas@tuwien.ac.at
- J. D. Mitchell
- Affiliation: University of St Andrews, St Andrews KY16 9AJ, Scotland
- MR Author ID: 691066
- Email: jdm3@st-andrews.ac.uk
- Y. H. Péresse
- Affiliation: University of Hertfordshire, Hatfield AL10 9EU, United Kingdom
- Email: y.peresse@herts.ac.uk
- Received by editor(s): January 17, 2019
- Received by editor(s) in revised form: August 9, 2019, September 12, 2019, and September 13, 2019
- Published electronically: January 28, 2020
- Communicated by: Heike Mildenberger
- © Copyright 2020 American Mathematical Society
- Journal: Proc. Amer. Math. Soc. 148 (2020), 1917-1931
- MSC (2010): Primary 20B07, 20B30, 20M20
- DOI: https://doi.org/10.1090/proc/14881
- MathSciNet review: 4078077