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 |a^{S}| 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)|
¹
|2^{S}|
(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)|
¹
|a^{S}| 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.

Keywords:
Non-repetitive sequences, axiom of
choice, combinatorial number theory.