Sets of universal sequences for the symmetric group and analogous semigroups

DOI10.1090/PROC/14881zbMATH Open1480.20002arXiv1803.01377OpenAlexW3001703720WikidataQ126298985 ScholiaQ126298985MaRDI QIDQ5221335FDOQ5221335

Authors: J. Hyde, J. Jonušas, J. D. Mitchell, Y. Péresse 

Publication date: 25 March 2020

Published in: Proceedings of the American Mathematical Society (Search for Journal in Brave)

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,ldotsinS$, the equations $w_n=s_n$, $ninmathbbN$, can be solved simultaneously in $S$. For example, Galvin showed that the sequence $(a^{-1}(a^{n}b{a}^{-n})b^{-1}(a^n{b}^{-1}{a}^{-n})ba{)}_{ninmathbbN}$ is universal for the symmetric group Sym$(X)$ when $X$ is infinite, and Sierpi'nski showed that $(a^2{b}^3(aba{b}^3{)}^{n+1}a{b}^{2}a{b}^3{)}_{ninmathbbN}$ 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 Sym$(X)$ is also universal for Sym$(Y)$. If $|X|>2^{alep{h}_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 satisfy this condition, and hence are universal for $X^X$ for every infinite set $X$.

Full work available at URL: https://arxiv.org/abs/1803.01377

Recommendations

• Classes of universal words for the infinite symmetric groups
• On the universality of systems of words in permutation groups
• Universal sequences for the order-automorphisms of the rationals
• scientific article; zbMATH DE number 1008473
• GENERATING INFINITE SYMMETRIC GROUPS

Mathematics Subject Classification ID

Symmetric groups (20B30) Semigroups of transformations, relations, partitions, etc. (20M20) General theory for infinite permutation groups (20B07)

Cites Work

• Turbulence, amalgamation, and generic automorphisms of homogeneous structures
• Title not available (Why is that?)
• Some Remarks on Commutators
• Infinite partition monoids.
• On representing words in the automorphism group of the random graph
• The Bergman property for semigroups
• Generating Countable Sets of Permutations
• GENERATING INFINITE SYMMETRIC GROUPS
• Generation of infinite factorizable inverse monoids.
• The decision problem for equational bases of algebras
• Problem list from: Algebras, lattices and varieties: a conference in honor of Walter Taylor, University of Colorado, 15--18 August, 2004
• On the universality of systems of words in permutation groups
• Representations of infinite permutations by words (II)
• Representations of Infinite Permutations by Words
• Classes of universal words for the infinite symmetric groups
• Are Primitive Words Universal for Infinite Symmetric Groups?
• Some Universal Sets of Terms
• Sur l'approximation des fonctions continues par les superpositions de quatre fonctions
• Generating countable sets of surjective functions.
• Sur les suites infinies de fonctions définies dans les ensembles quelconques
• Infinite dual symmetric inverse monoids
• Sur un théorème de M. Sierpiński
• Universal sequences for the order-automorphisms of the rationals

Cited In (4)

• Title not available (Why is that?)
• Universal sequences for the order-automorphisms of the rationals
• Classes of universal words for the infinite symmetric groups
• On the universality of systems of words in permutation groups

This page was built for publication: Sets of universal sequences for the symmetric group and analogous semigroups

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5221335)