top
We prove that any countable set of surjective functions on an infinite set of cardinality ℵₙ with n ∈ ℕ can be generated by at most n²/2 + 9n/2 + 7 surjective functions of the same set; and there exist n²/2 + 9n/2 + 7 surjective functions that cannot be generated by any smaller number of surjections. We also present several analogous results for other classical infinite transformation semigroups such as the injective functions, the Baer-Levi semigroups, and the Schützenberger monoids.
J. D. Mitchell, and Y. Péresse. "Generating countable sets of surjective functions." Fundamenta Mathematicae 213.1 (2011): 67-93. <http://eudml.org/doc/283006>.
@article{J2011, abstract = {We prove that any countable set of surjective functions on an infinite set of cardinality ℵₙ with n ∈ ℕ can be generated by at most n²/2 + 9n/2 + 7 surjective functions of the same set; and there exist n²/2 + 9n/2 + 7 surjective functions that cannot be generated by any smaller number of surjections. We also present several analogous results for other classical infinite transformation semigroups such as the injective functions, the Baer-Levi semigroups, and the Schützenberger monoids.}, author = {J. D. Mitchell, Y. Péresse}, journal = {Fundamenta Mathematicae}, keywords = {transformation semigroups; generating sets; surjective functions; injective functions; transformation monoids}, language = {eng}, number = {1}, pages = {67-93}, title = {Generating countable sets of surjective functions}, url = {http://eudml.org/doc/283006}, volume = {213}, year = {2011}, }
TY - JOUR AU - J. D. Mitchell AU - Y. Péresse TI - Generating countable sets of surjective functions JO - Fundamenta Mathematicae PY - 2011 VL - 213 IS - 1 SP - 67 EP - 93 AB - We prove that any countable set of surjective functions on an infinite set of cardinality ℵₙ with n ∈ ℕ can be generated by at most n²/2 + 9n/2 + 7 surjective functions of the same set; and there exist n²/2 + 9n/2 + 7 surjective functions that cannot be generated by any smaller number of surjections. We also present several analogous results for other classical infinite transformation semigroups such as the injective functions, the Baer-Levi semigroups, and the Schützenberger monoids. LA - eng KW - transformation semigroups; generating sets; surjective functions; injective functions; transformation monoids UR - http://eudml.org/doc/283006 ER -