×

A number-theoretic conjecture and its implication for set theory. (English) Zbl 1138.11302

Let \(|\text{seq}^ {1-1}(S)|\) denote the cardinality of the set of all finite one-to-one sequences that can be formed from elements of a given set \(S\), and for positive integers \(a\) let \(|a^S|\) denote the cardinality of all functions from \(S\) to \(a\). The author and S.  Shelah [J. Symbolic Logic 59, 30–30 (1994; Zbl 0795.03064)] proved that for infinite sets \(S\) one always has \(|\text{seq}^ {1-1}(S)|\neq |2^S|\), but nothing more can be proved without the axiom of choice. The aim of the paper is to state and give evidence for a number-theoretical conjecture which implies that for any infinite set \(S\) and for every integer \(a\geq 2\), \(|\text{seq}^ {1-1}(S)|\neq |a^S|\). Before stating the conjecture we need some definitions. For any non-negative integer \(n\), let \(n^*\) be the number of one-to-one sequences we can build with \(n\) distinct objects. Further let \(D(a)=\{n<a\:a|n^*\}\) and \(d(a)=|D(a)|\). A positive integer \(a\) is called \(1\)-regular if \(d(a)\leq 1\). (In the paper various statistical results about the distribution of \(1\)-regular integers, or about the random behavior of \(n^*\) or \(D(a)\) can also be found.) For every integer \(a\geq 2\) let \(P_a=n\:n^*=n^k\;\text{for\;some}\;k\geq 2\) and \(P_a=\cup _{a\geq 2}^\infty P_a\). The author formulates the following three conjectures: (A) The set \(P\) is finite. (B) For each integer \(a\geq 2\), the set \(P_a\) is finite. (C) For each integer \(a\geq 2\), the set \(n\:n^*=a^k\;\text{for\;some}\;k\geq 2\;\text{and}\^^M(n+t)\in P_a\;\text{for\;some}\;1\leq t\leq k\) is finite (in the paper the words “is finite” are missing in the formulation of the last conjecture). Actually it is the weakest of the three conjectures the Conjecture C which is mainly used in the paper. One of the results of the paper says that if Conjecture C is true, then for any infinite set \(S\) and any integer \(a\geq 2\) we always have \(|\text{seq}^ {1-1}(S)|\neq |a^S|\), even in the absence of the axiom of choice.

MSC:

11A25 Arithmetic functions; related numbers; inversion formulas
03E05 Other combinatorial set theory
03E65 Other set-theoretic hypotheses and axioms
11A05 Multiplicative structure; Euclidean algorithm; greatest common divisors
11B83 Special sequences and polynomials

Citations:

Zbl 0795.03064
PDFBibTeX XMLCite
Full Text: EuDML EMIS