Maximal clones on uncountable sets that include all permutations (Q2577755)

From MaRDI portal
scientific article
Language Label Description Also known as
English
Maximal clones on uncountable sets that include all permutations
scientific article

    Statements

    Maximal clones on uncountable sets that include all permutations (English)
    0 references
    0 references
    6 January 2006
    0 references
    Let \(X\) be a set of size \(| X| =\kappa\). For each natural number \(n\geq 1\), the set of functions on \(X\) of arity \(n\) is denoted by \({\mathcal O}^{(n)}\). Thus, \({\mathcal O}=\bigcup_{n=1}^\infty{\mathcal O}^{(n)}\) is the set of all finitary operations on \(X\). A \textit{clone} is a subset of \({\mathcal O}\) which contains the projection maps and which is closed under composition. Arbitrary intersections of clones are obviously again clones and therefore the set of clones on \(X\) forms a complete algebraic lattice \(Cl(X)\) which is a subset of the power set of \({\mathcal O}\). It is well-known that the clone lattice is countably infinite if \(X\) has exactly two elements, it has the size of the continuum if \(X\) is finite and has at least three elements, and \(| Cl(X)| =2^{2^\kappa}\) if \(X\) is infinite. The dual atoms of the clone lattice are called maximal clones. On a finite \(X\) there exist finitely many maximal clones, and an explicit list of those clones has been provided by \textit{I. Rosenberg} [Über die funktionale Vollständigkeit in den mehrwertigen Logiken. Rozpr. Česk. Akad. Věd, Rada Mat. Přír. Věd. 80, No.~4 (1970; Zbl 0199.30201)]. Moreover, the clone lattice is dually atomic in that case, that is, every nontrivial clone is contained in a maximal one. For \(X\) infinite the number of maximal clones equals the size of the whole clone lattice [\textit{I. G. Rosenberg}, Arch. Math. 27, 561--568 (1976; Zbl 0345.02010)], so that it seems impossible to know all of them. It has also been shown by \textit{M. Goldstern} and \textit{S. Shelah} [Trans. Am. Math. Soc. 357, 3525--3551 (2005; Zbl 1081.08006)] that if the continuum hypothesis holds, then not every nontrivial clone on a countably infinite set is contained in a maximal one. In the paper under review, the maximal clones on a set \(X\) of infinite regular cardinality \(\kappa\) which contain all permutation but not all unary functions is determined; this extends a result of \textit{L. Heindorf}'s [Algebra Univers. 48, 209--222 (2002; Zbl 1061.08003)] for countably infinite \(X\). If \(\kappa\) is countably infinite or weakly compact, this yields a list of all maximal clones containing all permutations, since in that case the maximal clones above unary functions are known. Moreover, a result of \textit{G. P. Gavrilov}'s [Probl. Kibern. 15, 5--64 (1965; Zbl 0305.02028)] to obtain on all infinite \(X\) a list of all maximal submonoids of the monoid of unary functions which contain the permutations is generalized.
    0 references
    clone lattice
    0 references
    permutation
    0 references
    unary function
    0 references
    maximal clone
    0 references
    maximal monoid
    0 references

    Identifiers