Generating countable sets of surjective functions

James D. Mitchell; Yann Peresse

doi:10.4064 / fm213-1-4

Generating countable sets of surjective functions

James D. Mitchell, Yann Peresse

Research output: Contribution to journal › Article › peer-review

10 Citations (Scopus)

Abstract

We prove that any countable set of surjective functions on an infinite set of cardinality ℵn with n∈N can be generated by at most n2/2+9n/2+7 surjective functions of the same set; and there exist n2/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.

Original language	English
Pages (from-to)	67-93
Number of pages	27
Journal	Fundamenta Mathematicae
Volume	213
Issue number	1
DOIs	https://doi.org/10.4064 / fm213-1-4
Publication status	Published - 2011

Keywords

TRANSFORMATIONS
SEMIGROUPS
Infinite Combinatorics

Access to Document

10.4064 / fm213-1-4

http://www-circa.mcs.st-and.ac.uk/~jamesm/articles/sierpinski10.pdf

Cite this

@article{97df149e14bf4ac3a483909d66cc6ce3,

title = "Generating countable sets of surjective functions",

abstract = "We prove that any countable set of surjective functions on an infinite set of cardinality ℵn with n∈N can be generated by at most n2/2+9n/2+7 surjective functions of the same set; and there exist n2/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{\"u}tzenberger monoids.",

keywords = "TRANSFORMATIONS, SEMIGROUPS, Infinite Combinatorics",

author = "Mitchell, {James D.} and Yann Peresse",

note = "JD Mitchell, Y. Peresse, 'Generating countable sets of surjective functions', Fundamenta Mathematicae, Vol. 213(1): 67-93, 2011, the version of record is available at doi: 10.4064 / fm213-1-4. {\textcopyright} 2011 Institute of Mathematics, Polish Academy of Sciences (IMPAN).",

year = "2011",

doi = "10.4064 / fm213-1-4",

language = "English",

volume = "213",

pages = "67--93",

journal = "Fundamenta Mathematicae",

issn = "0016-2736",

publisher = "Instytut Matematyczny",

number = "1",

}

TY - JOUR

T1 - Generating countable sets of surjective functions

AU - Mitchell, James D.

AU - Peresse, Yann

N1 - JD Mitchell, Y. Peresse, 'Generating countable sets of surjective functions', Fundamenta Mathematicae, Vol. 213(1): 67-93, 2011, the version of record is available at doi: 10.4064 / fm213-1-4. © 2011 Institute of Mathematics, Polish Academy of Sciences (IMPAN).

PY - 2011

Y1 - 2011

N2 - We prove that any countable set of surjective functions on an infinite set of cardinality ℵn with n∈N can be generated by at most n2/2+9n/2+7 surjective functions of the same set; and there exist n2/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.

AB - We prove that any countable set of surjective functions on an infinite set of cardinality ℵn with n∈N can be generated by at most n2/2+9n/2+7 surjective functions of the same set; and there exist n2/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.

KW - TRANSFORMATIONS

KW - SEMIGROUPS

KW - Infinite Combinatorics

U2 - 10.4064 / fm213-1-4

DO - 10.4064 / fm213-1-4

M3 - Article

SN - 0016-2736

VL - 213

SP - 67

EP - 93

JO - Fundamenta Mathematicae

JF - Fundamenta Mathematicae

IS - 1

ER -

Generating countable sets of surjective functions

Abstract

Keywords

Access to Document

Fingerprint

Cite this