Notation. For a set A and a natural number n, let:

1. (1) $[A]^n=\{X\subseteq A\mid |X|=n\}$ ,

2. (2) $[A]^{\leq n}=\{X\subseteq A\mid |X|\leq n\}$ ,

3. (3) $\mathrm {{fin}} (A)= \bigcup \limits _{k\in \omega }[A]^k$ ,

4. (4) $\mathrm {{seq}}_n(A)=\{f\mid f\colon n\rightarrow A\}$ ,

5. (5) $\mathrm {{seq}}(A)=\bigcup \limits _{k\in \omega }\mathrm {{seq}}_k(A)$ ,

6. (6) $\mathrm {{seq}}^{1-1}_n(A)=\{f\in \mathrm {{seq}}_n(A)\mid f\text { is injective}\}$ ,

7. (7) $\mathrm {{seq}}^{1-1}(A)=\bigcup \limits _{k\in \omega }\mathrm {{seq}}^{1-1}_k(A)$ ,

8. (8) $\mathcal {S}(A)=\{f\colon A\rightarrow A\mid f\text { is bijective}\}$ ,

9. (9) $\mathcal {S}_n(A)=\{f\in \mathcal {S}(A)\mid |\{a\in A\mid f(a)\neq a\}|=n\}$ ,

10. (10) $\mathcal {S}_{\mathrm {{fin}}}(A)=\bigcup \limits _{k\in \omega }\mathcal {S}_k(A)$ ,

and for $\pi \in \mathcal {S}(A)$ , let $\mathrm {{m}}(\pi )=\{a\in A\mid \pi (a)\neq a\}$ ; in other words, $\mathrm {{m}}(\pi )$ collects all elements in A that $\pi $ permutes.

We write $(a_0; a_1;\ldots; a_n)$ for the cyclic permutation such that

$a_0\mapsto a_1\mapsto \cdots \mapsto a_n\mapsto a_0$ .

Proof Let A be an infinite set. By ${\mathrm {AC}}_{\leq n}$ , we can define a linear order $<_B$ on each $B\in [A]^n$ by using a choice function for $[A]^{\leq n}.$

For each $\pi \in \mathcal {S}_n(A)$ where $\mathrm {{m}}(\pi )=\{b_1,\dots ,b_{n}\}$ and $b_1<_{\mathrm {{m}}(\pi )}\dots <_{\mathrm {{m}}(\pi )}b_{n}$ , we define $f\colon \mathcal {S}_n(A)\rightarrow \mathrm {{seq}}^{1-1}_n(A)$ by

$$\begin{align*}f(\pi)=(\pi(b_1),\dots,\pi(b_{n})).\end{align*}$$

We can see that f is an injection.

Proof Cf. [Reference Aksornthong and Vejjajiva1, Corollary 2.2].

Proof Let A be an infinite set. Similarly to the proof of Theorem 2.1, under ${\mathrm {AC}}_{<\aleph _0}$ , each finite subset of A can be linearly ordered. Thus, we can define an injection $g\colon \mathcal {S}_{\mathrm {{fin}}}(A)\to \mathrm {{seq}}^{1-1}(A)$ as f in Theorem 2.1. Hence $|\mathcal {S}_{\mathrm {{fin}}}(A)|\leq |\mathrm {{seq}}^{1-1}(A)|$ . From the definition of g, we can see that for any $(b_1,\dots ,b_{n})\in \mathrm {{seq}}^{1-1}(A)$ such that $b_1$ is the least element of $\{b_1,\dots ,b_{n}\}$ , $(b_1,\dots ,b_{n})$ is not in the range of g. Thus g is not a surjection and so $\mathrm {{ran}}(g)$ is a proper subset of $\mathrm {{seq}}^{1-1}(A)$ where $|\mathcal {S}_{\mathrm {{fin}}}(A)|=|\mathrm {{ran}}(g)|$ . Suppose A is Dedekind finite. From [Reference Guozhen3, Fact 2.14], we have that $\mathrm {{seq}}^{1-1}(A)$ is also Dedekind finite. As a result, $|\mathcal {S}_{\mathrm {{fin}}}(A)|\neq |\mathrm {{seq}}^{1-1}(A)|$ . Thus $|\mathcal {S}_{\mathrm {{fin}}}(A)|<|\mathrm {{seq}}^{1-1}(A)|$ .

Proof It is easy to see that for an infinite ordinal $\alpha $ , $f\colon \alpha \rightarrow \mathcal {S}_n(\alpha )$ defined by

$$\begin{align*}f(\beta) = \begin{cases} (\beta+1;\beta+2;\dots;\beta+n), & \text{if } \beta+n<\alpha ,\\ (k+2;k+4;\dots;k+2n), & \text{if } \beta+k=\alpha \leq \beta+n \\ \end{cases}\end{align*}$$

is an injection.

Fact 2.6. For any infinite ordinal $\alpha $ , $|\alpha |=|\mathrm {{seq}}(\alpha )|$ .

Proof Cf. [Reference Halbeisen5, Theorem 5.19].

Proof By Theorems 2.1 and 2.5, Fact 2.6, and the Cantor–Bernstein Theorem (which is provable in ZF), these bijections can be constructed.

Proof For convenience, let $|A|=a$ . Since $a\geq 3\cdot 2^n+n>2n$ , $a<2(a-n)$ and so

$$ \begin{align*} |\mathrm{{seq}}_n(A)| = a^n&<(2(a-n))^n\\ &<a\cdot(a-1)\cdot \cdots \cdot(a-(n-1))2^n \\ & \leq a\cdot(a-1)\cdot\cdots\cdot(a-n+1)\left[\frac{a-n}{3}\right] \\ & \leq a\cdot(a-1)\cdot\cdots\cdot(a-n)\left[\frac{1}{0!}-\frac{1}{1!}+\cdots+\frac{(-1)^{n+1}}{(n+1)!}\right]\\ &=\binom{a}{n+1}(n+1)!\left[\frac{1}{0!}-\frac{1}{1!}+\cdots+\frac{(-1)^{n+1}}{(n+1)!}\right]\\ &=|\mathcal{S}_{n+1}(A)| \end{align*} $$

as desired.

Proof By straightforward computation, we can see that

$$\begin{align*}K_n=\max\{2n+1,\binom{n}{0}+0,\dots,\binom{n}{n-1}+n-1\}\end{align*}$$

satisfies the inequality.

Proof Let A be an infinite set. By Lemma 2.9, there exists a natural number $K_n\geq 2n+1$ such that for all natural numbers $k<n$ ,

$$\begin{align*}k!\binom{n}{k}\binom{K_n}{k}\leq (k+1)!\binom{K_n}{k+1}.\end{align*}$$

Since $K_n\geq 2n+1$ , we also have that $\binom {K_n}{n}\leq \binom {K_n}{n+1}$ .

Let $X=\{x_1,x_2,\dots ,x_{K_n}\}\subseteq A$ and for each natural number $k\leq n$ , we define

$$\begin{align*}A_k=\{(a_1,\dots,a_n)\in\mathrm{{seq}}^{1-1}_n(A)\mid |\{a_1,\dots,a_n\}\cap X|=k\}.\end{align*}$$

It suffices to show that for each natural number $k\leq n$ , there exists an injection $f_k\colon A_k\rightarrow \mathcal {S}_{n+1}(A)$ where $f_0,\dots ,f_n$ have disjoint images.

First we deal with the case $k=n$ . We shall create an equivalence relation $\sim $ on $\mathrm {{seq}}^{1-1}_{n+1}(X)$ which tells us that the related sequences will generate the same cyclic permutation. The definition of $\sim $ is as follows:

For any $(a_0,\dots ,a_n),(b_0,\dots ,b_n)\in \mathrm {{seq}}^{1-1}_{n+1}(X)$ ,

$$\begin{align*}(a_0,\dots,a_n)\sim (b_0,\dots,b_n)\leftrightarrow\exists k\in\omega\forall l\in\omega,a_l=b_{l+k},\end{align*}$$

where the indices of $a_i$ and $b_i$ are considered in modulo $n+1$ . Note that

$$\begin{align*}[(a_0,\dots,a_n)]_{\sim}=[(b_0,\dots,b_n)]_{\sim}\leftrightarrow (a_0;\dots;a_n)=(b_0;\dots;b_n).\end{align*}$$

Thus $|\mathrm {{seq}}^{1-1}_{n+1}(X)/{\sim} |\leq |\mathcal {S}_{n+1}(A)|$ by mapping

$$\begin{align*}[(a_0,\dots,a_n)]_\sim \mapsto (a_0;\dots;a_n).\end{align*}$$

Since

$$ \begin{align*} |A_n|=n!\binom{K_n}{n}&\leq n!\binom{K_n}{n+1}\\&=\frac{1}{n+1}|\mathrm{{seq}}^{1-1}_{n+1}(X)|=|\mathrm{{seq}}^{1-1}_{n+1}(X)/{\sim}|, \end{align*} $$

there exists an injection $f_n\colon A_n\to \mathcal {S}_{n+1}(A)$ as desired.

Now, let $k<n$ be a natural number. We may assume that $0,1\notin A$ . We start by defining functions $n_X$ , $i_X$ , $Q_X$ , and $Q_X'$ from the same domain $\mathrm {{seq}}^{1-1}_n(A)$ as follows:

$$ \begin{align*} n_X(a_1,\dots,a_n)& =|\{a_1,\dots,a_n\}\cap X|, \\ i_X(a_1,\dots,a_n)& = (\epsilon_1,\dots,\epsilon_n), \text{where } \epsilon_i=1\text{ if } a_i\in X \text{ and}\\ & \hspace{2.8cm}\epsilon_i=0 \text{ otherwise, } \text{ for each }1\leq i\leq n, \\ Q_X(a_1,\dots,a_n) &= (a_{i_1},\ldots,a_{i_{m}}) \text{ if } \{a_1,\dots,a_n\}\cap X=\{a_{i_1},\dots,a_{i_{m}}\},\\ Q_X'(a_1,\dots,a_n) &=(a_{j_1},\ldots,a_{j_{l}}) \text{ if } \{a_1,\dots,a_n\}\setminus X=\{a_{j_1},\dots,a_{j_{l}}\}, \end{align*} $$

where the indices $i_1,\dots ,i_{m}$ and $j_1,\dots ,j_{l}$ are increasing.

Define $B_k=\{i_X(a)\mid a\in A_k\}$ . We have that

$$\begin{align*}|B_k\times \mathrm{{seq}}^{1-1}_k(X)|=k!\binom{n}{k}\binom{K_n}{k}\leq (k+1)!\binom{K_n}{k+1}=|\mathrm{{seq}}^{1-1}_{k+1}(X)|.\end{align*}$$

Hence there exists an injection $h_k\colon B_k\times \mathrm {{seq}}^{1-1}_k(X)\rightarrow \mathrm {{seq}}^{1-1}_{k+1}(X)$ .

Next, we will construct a cyclic permutation from two injective sequences of two disjoint sets.

For each $a=(a_0,\dots ,a_k)\in \mathrm {{seq}}^{1-1}_{k+1}(X)$ and $b=(b_0,\dots ,b_{n-k-1})\in \mathrm {{seq}}^{1-1}_{n-k}(A\setminus X)$ , we define the concatenation of a and b as follows:

$$\begin{align*}a^\frown b=(a_0;\dots;a_k;b_0;\dots;b_{n-k-1}).\end{align*}$$

Note that for any $a,a'\in \mathrm {{seq}}^{1-1}_{k+1}(X)$ and $b,b'\in \mathrm {{seq}}^{1-1}_{n-k}(A\setminus X)$ , if $a^\frown b=a^{\prime \frown } b',$ then $a=a'$ and $b=b'$ .

Now, we define $f_k\colon A_k\rightarrow \mathcal {S}_{n+1}(A)$ by

$$\begin{align*}f_k(a)=h_k(i_X(a),Q_X(a))^\frown Q_X'(a).\end{align*}$$

Note that $f_k$ moves exactly $k+1$ elements in X.

To show that $f_k$ is injective, let $a,b\in A_k$ be such that $f_k(a)=f_k(b)$ . Then $h_k(i_X(a),Q_X(a))=h_k(i_X(b),Q_X(b))$ and $Q_X'(a)=Q_X'(b)$ . Since $h_k$ is injective, $i_X(a)=i_X(b)$ and $Q_X(a)=Q_X(b)$ . Therefore we can retrieve the sequence a from the information $Q_X(a),Q_X'(a)$ and $i_X(a)$ as follows:

Change the $p^{\text {th}}$ occurrence of $1$ in the sequence $i_X(a)$ to $Q_X(a)(p-1)$ for each $1\leq p\leq k$ and change the $q^{\text {th}}$ occurrence of $0$ in the sequence $i_X(a)$ to $Q_X'(a)(q-1)$ for each $1\leq q\leq n-k$ . We can see that the resulting sequence is $a.$ Since the values of $i_X,Q_X,Q_X'$ at a and b are equal, we can conclude that $a=b.$ Therefore $f_k$ is injective.

Finally, since for each natural number $m\leq n$ and each $a\in A_m$ , $f_m(a)$ moves exactly $m+1$ elements in X, $f_0,\dots ,f_n$ have disjoint images. Thus $\bigcup \limits _{i=0}^{n} f_i\colon \mathrm {{seq}}^{1-1}_n(A)\rightarrow \mathcal {S}_{n+1}(A)$ is an injection.

Proof Let A be a Dedekind infinite set. Without loss of generality, suppose that $A\cap (n\times n)=\emptyset $ . Since there is a canonical bijection from $A\cup (n\times n)$ onto A, it is enough to construct an injection from $\mathrm {{seq}}_n(A)$ into $\mathrm {{seq}}^{1-1}_n(A\cup (n\times n))$ .

For each $a=(a_0,\dots ,a_{n-1})\in \mathrm {{seq}}_n(A)$ and $k<n$ , let $B_{a,k}=\{l<k\mid a_l=a_k\}$ and define

$$\begin{align*}f(a)(k)= \begin{cases} a_k, & \text{if } B_{a,k}=\emptyset, \\ (\min B_{a,k},|B_{a,k}|), & \text{otherwise.} \end{cases}\end{align*}$$

Then $f\colon \mathrm {{seq}}_n(A)\rightarrow \mathrm {{seq}}^{1-1}_n(A\cup (n\times n))$ is injective as desired.