A Number-Theoretic Conjecture and its
Implication for Set Theory
L. Halbeisen
Abstract. For any set S let |seq
1-1(S)| denote the cardinality of the set of all finite one-to-one
sequences that can be formed from S, and for positive integers a let |aS| denote the
cardinality of all functions from S to a. Using a result from combinatorial
number theory, Halbeisen and Shelah have shown that even in the absence
of the axiom of choice, for infinite sets S one always has |seq 1-1 (S)|
¹
|2S|
(but nothing more can be proved without the aid of the axiom of choice).
Combining stronger number-theoretic results with the combinatorial proof for
a = 2, it will be shown that for most positive integers a one can prove the
inequality |seq
1-1
(S)|
¹
|aS| without using any form of the axiom of choice.
Moreover, it is shown that a very probable number-theoretic conjecture implies that
this inequality holds for every positive integer a in any model of set theory.