THE PERMUTATIONS WITH n NON-FIXED POINTS AND THE SEQUENCES WITH LENGTH n OF A SET

• Published in: The Journal of symbolic logic 2024-09, Vol.89 (3), p.1067-1076
• Main Authors: NUNTASRI, JUKKRID, VEJJAJIVA, PIMPEN
• Format: Article
• Language: English
• Subjects: Codes; Theorems
• ISSN: 0022-4812; 1943-5886
• DOI: 10.1017/jsl.2022.57

We write $\mathcal {S}_n(A)$ for the set of permutations of a set A with n non-fixed points and $\mathrm {{seq}}^{1-1}_n(A)$ for the set of one-to-one sequences of elements of A with length n where n is a natural number greater than $1$ . With the Axiom of Choice, $|\mathcal {S}_n(A)|$ and $|\mathrm {{seq}}^{1-1}_n(A)|$ are equal for all infinite sets A. Among our results, we show, in ZF, that $|\mathcal {S}_n(A)|\leq |\mathrm {{seq}}^{1-1}_n(A)|$ for any infinite set A if ${\mathrm {AC}}_{\leq n}$ is assumed and this assumption cannot be removed. In the other direction, we show that $|\mathrm {{seq}}^{1-1}_n(A)|\leq |\mathcal {S}_{n+1}(A)|$ for any infinite set A and the subscript $n+1$ cannot be reduced to n. Moreover, we also show that “ $|\mathcal {S}_n(A)|\leq |\mathcal {S}_{n+1}(A)|$ for any infinite set A” is not provable in ZF.