Proof Let $P\in \mathscr {B}(A)$ . If ${\operatorname {ns}}(P)\subseteq \mathscr {P}(A_m)$ for some $m\in \omega $ , then clearly ${\operatorname {fix}_{\mathcal {G}}}(A_m)\subseteq {\operatorname {sym}_{\mathcal {G}}}(P)$ , which implies that $P\in \mathcal {V}_{\mathscr {B}}$ . For the other direction, suppose $P\in \mathcal {V}_{\mathscr {B}}$ and let $m\in \omega $ be such that ${\operatorname {fix}_{\mathcal {G}}}(A_m)\subseteq {\operatorname {sym}_{\mathcal {G}}}(P)$ ; that is, every $\pi \in \mathcal {G}$ fixing $A_m$ pointwise also fixes P. We claim ${\operatorname {ns}}(P)\subseteq \mathscr {P}(A_m)$ . Assume towards a contradiction that $x\sim _Py$ for some distinct $x,y$ such that one of x and y is not in $A_m$ . Suppose that $x=(n,Q,k)$ and $y=(n',Q',k')$ , and assume without loss of generality $n'\leqslant n$ . Then $x\notin A_m$ and thus $m\leqslant n$ . Let $l\in \omega $ be such that $(n,Q,l)\notin [y]_P$ and let q be the transposition that swaps k and l. Since P is finitary, such an l exists. Let h be the permutation of $A_{n+1}$ such that h fixes $A_n$ pointwise and for all $R\in \mathscr {B}(A_n)$ and all $j\in \omega $ , $h(n,R,j)=(n,R,q(j))$ if $R=Q$ , and $h(n,R,j)=(n,R,j)$ otherwise. Then $h\in \mathcal {G}_{n+1}$ fixes $A_{n+1}\setminus \{x,(n,Q,l)\}$ pointwise. Hence $h(y)=y$ . Extend h in a straightforward way to some $\pi \in \mathcal {G}$ . Then $\pi \in {\operatorname {fix}_{\mathcal {G}}}(A_m\cup \{y\})$ and $\pi (x)=(n,Q,l)\notin [y]_P$ . Thus $\pi $ moves P, which is a contradiction.

Proof Let $\Phi $ be the function on $\{P\in \mathscr {B}(A)\mid \exists m\in \omega ({\operatorname {ns}}(P)\subseteq \mathscr {P}(A_m))\}$ defined by

$$\begin{align*}\Phi(P)=\{(n_P,P\cap\mathscr{P}(A_{n_P}),k)\mid k\in\omega\}, \end{align*}$$

where $n_P$ is the least $m\in \omega $ such that ${\operatorname {ns}}(P)\subseteq \mathscr {P}(A_m)$ . Clearly, $\Phi \in \mathcal {V}_{\mathscr {B}}$ . In $\mathcal {V}_{\mathscr {B}}$ , by Lemma 3.1, $\Phi $ is an injection from $\mathscr {B}(A)$ into $\mathscr {P}(A)$ , and the sets in the range of $\Phi $ are pairwise disjoint, which implies that $|\mathscr {B}(A)|\leqslant ^\ast |A|$ . Since $|\mathscr {P}(A)|\nleqslant ^\ast |A|$ by Cantor’s theorem, it follows that $|\mathscr {B}(A)|<|\mathscr {P}(A)|$ .

Proof Let $P\in \mathcal {V}_{\mathrm {M}}$ be a finitary partition of A and let E be a finite support of P. We claim ${\operatorname {ns}}(P)\subseteq \mathscr {P}(E)$ . Assume towards a contradiction that $x\sim _Py$ for some distinct $x,y$ such that $x\notin E$ . Since P is finitary, we can find a $\pi \in {\operatorname {fix}_{\mathcal {G}}}(E\cup \{y\})$ such that $\pi (x)\notin [y]_P$ . Hence $\pi $ moves P, contradicting that E is a support of P. Thus ${\operatorname {ns}}(P)\subseteq \mathscr {P}(E)$ , so $P\in {\mathscr {B}_{\operatorname {fin}}}(A)$ .

Proof For each $n\in \omega $ , let $B_n$ be the nth Bell number; that is, $B_n=|\mathscr {B}(n)|$ . Recall Dobinski’s formula (see, for example, [Reference Rota11]):

$$\begin{align*}B_n=\frac{1}{e}\sum_{k=0}^\infty\frac{k^n}{k!}. \end{align*}$$

It is easy to see that $B_n=B_n^\star +B_{n+1}^\star $ . Hence, for $n\geqslant 23$ , we have

$$\begin{align*}B_n^\star>\frac{B_{n-1}}{2}>\frac{8^{n-1}}{2e\cdot8!}=\frac{2^{n-5}}{2e\cdot8!}\cdot2^{2n+2} \geqslant\frac{2^{18}}{2e\cdot8!}\cdot2^{2n+2}>2^{2n+2}.\\[-40pt] \end{align*}$$

Proof In $\mathcal {V}_{\mathrm {M}}$ , since $\mathscr {P}(A^2)$ is Dedekind finite, and the injections constructed in the proofs of Facts 2.15 and 2.18 are clearly not surjective, it follows that $|\mathscr {B}_{\mathrm {fin}}(A)|<|\mathrm {Part}_{\mathrm {fin}}(A)|<|\mathrm {Part}(A)|<|\mathscr {P}(A^2)|$ . By Lemma 3.4, it remains to show that $|\mathscr {P}(A)|<|\mathscr {B}(A)|$ .

For a finite subset E of A, we can use $<_{\mathrm {M}}$ to define an ordering of the subsets of A supported by E and an ordering of the finitary partitions P of A with ${\operatorname {ns}}(P)\subseteq \mathscr {P}(E)$ . Let $D=\{a_i\mid i<46\}$ be a $46$ -element subset of A. In $\mathcal {V}_{\mathrm {M}}$ , we define an injection f from $\mathscr {P}(A)$ into $\mathscr {B}(A)$ as follows.

Let $C\in \mathcal {V}_{\mathrm {M}}$ be a subset of A. By Lemma 3.5, C has a least support E. Suppose that C is the kth subset of A with E as its least support. Let $n=|D\bigtriangleup E|$ , where $\bigtriangleup $ denotes the symmetric difference. Now, if $|E|\geqslant 23$ , define $f(C)$ to be the kth finitary partition P of A with $\bigcup {\operatorname {ns}}(P)=E$ ; otherwise, define $f(C)$ to be the $(B_n^\star -k-1)$ th finitary partition P of A with $\bigcup {\operatorname {ns}}(P)=D\bigtriangleup E$ . In the second case, $n\geqslant 23$ , and thus $B_n^\star -k-1>2^{2n+1}$ by Lemmas 3.6 and 3.7. Thus f is injective. Since D is a finite support of f, it follows that $f\in \mathcal {V}_{\mathrm {M}}$ .

Finally, since $\mathscr {B}(A)$ is Dedekind finite and f is not surjective, it follows that $|\mathscr {P}(A)|<|\mathscr {B}(A)|$ .

Proof (1) $|\mathscr {B}(A)|\nleqslant |\mathrm {Part}_{\mathrm {fin}}(A)|$ . Assume towards a contradiction that in $\mathcal {V}_{\mathrm {F}}$ there is an injection f from $\mathscr {B}(A)$ into ${\operatorname {Part}_{\operatorname {fin}}}(A)$ . Let B be a countable support of f. Let $\{a_n\mid n\in \omega \}\subseteq A\setminus B$ with $a_i\neq a_j$ whenever $i\neq j$ . Consider the finitary partition $P=\{\{a_{2n},a_{2n+1}\}\mid n\in \omega \}\cup [A\setminus \{a_n\mid n\in \omega \}]^1\in \mathcal {V}_{\mathrm {F}}$ . Since $f(P)$ is a finite partition, there must be $i,j\in \omega $ with $i\neq j$ such that $a_{2i}$ and $a_{2j}$ are in the same block of $f(P)$ . The transposition that swaps $a_{2i}$ and $a_{2i+1}$ fixes P, and thus also fixes $f(P)$ , which implies that $a_{2i+1}$ and $a_{2j}$ are also in the same block of $f(P)$ . Hence, the transposition that swaps $a_{2i+1}$ and $a_{2j}$ fixes $f(P)$ , but it moves P, contradicting that f is injective.

(2) $|\mathscr {B}_{\mathrm {fin}}(A)|\nleqslant |\mathscr {P}(A)|$ . Assume towards a contradiction that in $\mathcal {V}_{\mathrm {F}}$ there is an injection g from ${\mathscr {B}_{\operatorname {fin}}}(A)$ into $\mathscr {P}(A)$ . Let C be a countable support of g. Let $a_0,a_1,a_2,a_3$ be four distinct elements of $A\setminus C$ . Consider the finitary partition $P=\{\{a_0,a_1\},\{a_2,a_3\}\}\cup [A\setminus \{a_0,a_1,a_2,a_3\}]^1\in \mathcal {V}_{\mathrm {F}}$ . Clearly, for any $i,j<4$ with $i\neq j$ , there is a $\pi \in {\operatorname {fix}_{\mathcal {G}}}(C)$ such that $\pi (P)=P$ and $\pi (a_i)=a_j$ . Hence, $\{a_0,a_1,a_2,a_3\}\subseteq g(P)$ or $\{a_0,a_1,a_2,a_3\}\subseteq A\setminus g(P)$ . Thus, the transposition that swaps $a_0$ and $a_2$ fixes $g(P)$ , but it moves P, contradicting that g is injective.

(3) $|\mathscr {P}(A)|\nleqslant |\mathscr {B}(A)|$ . Assume towards a contradiction that in $\mathcal {V}_{\mathrm {F}}$ there is an injection h from $\mathscr {P}(A)$ into $\mathscr {B}(A)$ . Let D be a countable support of h. Let C be a denumerable subset of $A\setminus D$ . Take $x\in C$ and $y\in A\setminus (C\cup D)$ . We claim that $\{x\}\in h(C)$ . Assume not; since $h(C)$ is finitary, we can find a $z\in C$ such that $z\notin [x]_{h(C)}$ , and then the transposition that swaps x and z would fix C but move $h(C)$ , which is a contradiction. Similarly, $\{y\}\in h(C)$ . Hence, the transposition that swaps x and y fixes $h(C)$ , but it moves C, contradicting that h is injective.

Proof See [Reference Specker18, 2.1].

Proof See [Reference Halbeisen4, Theorem 5.19].

Proof See [Reference Shen12, Lemma 3.3].

Proof Let f be an injection from $\alpha $ into $\operatorname {fin}(A)$ , where $\alpha $ is an infinite ordinal. Let $\sim $ be the equivalence relation on A defined by

$$\begin{align*}x\sim y\quad\text{if and only if}\quad\forall\beta<\alpha(x\in f(\beta)\leftrightarrow y\in f(\beta)). \end{align*}$$

Clearly, for every $x\in \bigcup {\operatorname {ran}}(f)$ , the equivalence class $[x]_\sim $ is finite.

We want to show that there are $\alpha $ many such equivalence classes. In order to prove this, define a function $\Psi $ on $\bigcup {\operatorname {ran}}(f)$ by

$$\begin{align*}\Psi(x)=\bigl\{\gamma<\alpha\bigm|x\in f(\gamma)\text{ and } \textstyle\bigcap\{f(\beta)\mid\beta<\gamma\text{ and }x\in f(\beta)\}\nsubseteq f(\gamma)\bigr\}. \end{align*}$$

We claim that, for all $x,y\in \bigcup {\operatorname {ran}}(f)$ ,

(1) $$ \begin{align} x\sim y\quad\text{if and only if}\quad\Psi(x)=\Psi(y). \end{align} $$

Clearly, if $x\sim y$ then $\Psi (x)=\Psi (y)$ . For the other direction, assume towards a contradiction that $\Psi (x)=\Psi (y)$ but not $x\sim y$ . Let $\delta <\alpha $ be the least ordinal such that $x\in f(\delta )$ is not equivalent to $y\in f(\delta )$ . Without loss of generality, assume that $x\in f(\delta )$ but $y\notin f(\delta )$ . Since $y\notin f(\delta )$ , we have $\delta \notin \Psi (y)=\Psi (x)$ , which implies that $\bigcap \{f(\beta )\mid \beta <\delta \text { and }x\in f(\beta )\}\subseteq f(\delta )$ . Since, for all $\beta <\delta $ , $x\in f(\beta )$ if and only if $y\in f(\beta )$ , it follows that $y\in \bigcap \{f(\beta )\mid \beta <\delta \text { and }x\in f(\beta )\}\subseteq f(\delta )$ , which is a contradiction.

We also claim that, for all $x\in \bigcup {\operatorname {ran}}(f)$ ,

(2) $$ \begin{align} \Psi(x)\in\operatorname{fin}(\alpha). \end{align} $$

Let $\xi $ be the least ordinal such that $x\in f(\xi )$ . Then $\xi $ is the first element of $\Psi (x)$ . For all $\gamma ,\delta \in \Psi (x)$ with $\gamma <\delta $ , if $f(\xi )\cap f(\gamma )=f(\xi )\cap f(\delta )$ , then $\bigcap \{f(\beta )\mid \beta <\delta \text { and }x\in f(\beta )\}\subseteq f(\xi )\cap f(\gamma )\subseteq f(\delta )$ , contradicting that $\delta \in \Psi (x)$ . Hence, the function that maps each $\gamma \in \Psi (x)$ to $f(\xi )\cap f(\gamma )$ is an injection from $\Psi (x)$ into $\mathscr {P}(f(\xi ))$ . Since $\mathscr {P}(f(\xi ))$ is finite, it follows that $\Psi (x)$ is finite.

Now, by Lemma 4.4, we can explicitly define an injection $p:\operatorname {fin}(\alpha )\to \alpha $ . By (2), ${\operatorname {ran}}(\Psi )\subseteq \operatorname {fin}(\alpha )$ . Let R be the well-ordering of ${\operatorname {ran}}(\Psi )$ induced by p; that is, $R=\{(a,b)\mid a,b\in {\operatorname {ran}}(\Psi )\text { and }p(a)<p(b)\}$ . Let $\theta $ be the order type of $\langle {\operatorname {ran}}(\Psi ),R\rangle$ , and let $\Theta $ be the unique isomorphism of $\langle {\operatorname {ran}}(\Psi ),R\rangle$ onto $\langle \theta ,\in \rangle$ . It is easy to see that $\theta $ is an infinite ordinal.

Again, by Lemma 4.4, we can explicitly define an injection $q:\operatorname {fin}(\theta )\to \theta $ . By (1), the function that maps each $\beta <\alpha $ to $\Psi [f(\beta )]$ is an injection from $\alpha $ into $\operatorname {fin}({\operatorname {ran}}(\Psi ))$ . Let g be the function on $\alpha $ defined by

$$\begin{align*}g(\beta)=\Theta^{-1}(q(\Theta[\Psi[f(\beta)]])). \end{align*}$$

g is visualized by the following diagram:

$$\begin{align*}\begin{matrix} g: & \alpha & \to & \operatorname{fin}({\operatorname{ran}}(\Psi)) & \to & \operatorname{fin}(\theta) & \to & \theta & \to & {\operatorname{ran}}(\Psi)\\ & \beta & \mapsto & \Psi[f(\beta)] & \mapsto & \Theta[\Psi[f(\beta)]] & \mapsto & q(\Theta[\Psi[f(\beta)]]) & \mapsto & g(\beta). \end{matrix} \end{align*}$$

Hence, g is an injection from $\alpha $ into ${\operatorname {ran}}(\Psi )$ .

By Lemma 4.3, we can explicitly define an injection $s:\alpha \times \alpha \to \alpha $ . Then the function h on $\alpha $ defined by

$$\begin{align*}h(\beta)=\Psi^{-1}[\{g(s(\beta,0)),g(s(\beta,1))\}] \end{align*}$$

is the required function.

Proof Let f be an injection from $\alpha $ into $\operatorname {fin}(A)$ , where $\alpha $ is an infinite ordinal. By Lemma 4.6, we can explicitly define an injection $h:\alpha \to \operatorname {fin}(A)$ such that the sets in ${\operatorname {ran}}(h)$ are pairwise disjoint and contain at least two elements. Now, the function g on A defined by

$$\begin{align*}g(x)= \begin{cases} \text{the unique }\beta<\alpha\text{ for which }x\in h(\beta), & \text{if}\ x\in\bigcup{\operatorname{ran}}(h),\\ 0, & \text{otherwise,} \end{cases} \end{align*}$$

is a surjection from A onto $\alpha $ , and the function t on $\alpha $ defined by

$$\begin{align*}t(\beta)= \begin{cases} \{h(0)\}\cup\{\{x\}\mid x\in A\setminus\bigcup{\operatorname{ran}}(h)\}, & \text{if}\ \beta=0,\\ \{h(\beta)\}, & \text{otherwise,} \end{cases} \end{align*}$$

is an auxiliary function for g.

Proof Assume towards a contradiction that $\mathscr {B}(A)$ is Dedekind infinite and there is a Dedekind finite-to-one function $\Phi :\mathscr {B}(A)\to \operatorname {fin}(A)$ . Let h be an injection from $\omega $ into $\mathscr {B}(A)$ . In what follows, we get a contradiction by constructing by recursion an injection H from the proper class of ordinals into the set $\mathscr {B}(A)$ .

For $n\in \omega $ , take $H(n)=h(n)$ . Now, we assume that $\alpha $ is an infinite ordinal and $H{\upharpoonright }\alpha $ is an injection from $\alpha $ into $\mathscr {B}(A)$ . Then $\Phi \circ (H{\upharpoonright }\alpha )$ is a Dedekind finite-to-one function from $\alpha $ to $\operatorname {fin}(A)$ . Since all Dedekind finite subsets of $\alpha $ are finite, $\Phi \circ (H{\upharpoonright }\alpha )$ is finite-to-one. By Lemma 4.5, $\Phi \circ (H{\upharpoonright }\alpha )$ explicitly provides an injection $f:\alpha \to \operatorname {fin}(A)$ . Therefore, by Corollary 4.7, from f, we can explicitly define a surjection $g:A\twoheadrightarrow \alpha $ and an auxiliary function t for g. Then $(H{\upharpoonright }\alpha )\circ g$ is a surjection from A onto $H[\alpha ]$ and $t\circ (H{\upharpoonright }\alpha )^{-1}$ is an auxiliary function for $(H{\upharpoonright }\alpha )\circ g$ . Hence, it follows from Lemma 4.2 that we can explicitly define an $H(\alpha )\in \mathscr {B}(A)\setminus H[\alpha ]$ from $H{\upharpoonright }\alpha $ (and $\Phi $ ).

Proof Suppose $\mathscr {B}(A)\neq {\mathscr {B}_{\operatorname {fin}}}(A)$ . Clearly, $|\mathscr {B}_{\mathrm {fin}}(A)|\leqslant |\mathscr {B}(A)|$ . If $|\mathscr {B}(A)|=|\mathscr {B}_{\mathrm {fin}}(A)|$ , since ${\mathscr {B}_{\operatorname {fin}}}(A)\subset \mathscr {B}(A)$ , it follows that $\mathscr {B}(A)$ is Dedekind infinite, contradicting Corollary 4.10. Hence, $|\mathscr {B}_{\mathrm {fin}}(A)|<|\mathscr {B}(A)|$ .

Proof By Fact 2.19, $|\mathrm {fin}(A)|\leqslant |\mathscr {B}_{\mathrm {fin}}(A)|\leqslant |\mathscr {B}(A)|$ . If $|\mathscr {B}(A)|=|\mathrm {fin}(A)|$ , since the injection constructed in the proof of Fact 2.19 is not surjective, it follows that $\mathscr {B}(A)$ is Dedekind infinite, contradicting Theorem 4.8. Thus, $|\mathrm {fin}(A)|<|\mathscr {B}(A)|$ .

Proof (i) ${}\Rightarrow {}$ (ii). Suppose that $\mathscr {B}(A)$ is Dedekind infinite. Assume towards a contradiction that ${\operatorname {ns}}(P)$ is power Dedekind finite for all $P\in \mathscr {B}(A)$ . Let $\langle P_k\mid k\in \omega \rangle$ be a denumerable family of finitary partitions of A. We define by recursion a sequence $\langle Q_n\mid n\in \omega \rangle$ of finitary partitions of A such that ${\operatorname {ns}}(Q_j)\neq \varnothing $ and $\bigcup {\operatorname {ns}}(Q_i)\cap \bigcup {\operatorname {ns}}(Q_j)=\varnothing $ whenever $i\neq j$ as follows.

Let $n\in \omega $ and assume that $Q_i$ has already been defined for all $i<n$ . Let $B=\bigcup _{i<n}\bigcup {\operatorname {ns}}(Q_i)$ . By assumption, ${\operatorname {ns}}(Q_i)$ is power Dedekind finite, so is $\bigcup {\operatorname {ns}}(Q_i)$ by Fact 2.5. Hence, B is power Dedekind finite. Consider the following two cases:

Case 1. For a least $k\in \omega $ , $x\sim _{P_k}y$ for some distinct $x,y\in A\setminus B$ . Then we define

$$\begin{align*}Q_n=\{[z]_{P_k}\setminus B\mid z\in A\setminus B\}\cup\{\{z\}\mid z\in B\}. \end{align*}$$

It is easy to see that $Q_n$ is a finitary partition of A such that ${\operatorname {ns}}(Q_n)\neq \varnothing $ and $\bigcup {\operatorname {ns}}(Q_i)\cap \bigcup {\operatorname {ns}}(Q_n)=\varnothing $ for all $i<n$ .

Case 2. Otherwise. Then, for all $k\in \omega $ and all $x\in \bigcup {\operatorname {ns}}(P_k)\setminus B$ ,

(3) $$ \begin{align} [x]_{P_k}\cap B\neq\varnothing\text{ and }[x]_{P_k}\setminus B=\{x\}. \end{align} $$

Define by recursion a sequence $\langle k_m\mid m\in \omega \rangle$ of natural numbers as follows.

Let $m\in \omega $ and assume that $k_j$ has been defined for $j<m$ . By assumption, ${\operatorname {ns}}(P_{k_j})$ is power Dedekind finite, so is $\bigcup {\operatorname {ns}}(P_{k_j})$ by Fact 2.5. Therefore, ${B\cup \bigcup _{j<m}\bigcup {\operatorname {ns}}(P_{k_j})}$ is power Dedekind finite. Hence, there is a $k\in \omega $ such that ${\operatorname {ns}}(P_k)\nsubseteq\mathscr {P}(B\cup \bigcup _{j<m}\bigcup {\operatorname {ns}}(P_{k_j}))$ . Define $k_m$ to be the least such k. Then

(4) $$ \begin{align} {\textstyle\bigcup}{\operatorname{ns}}(P_{k_m})\nsubseteq B\cup\bigcup_{j<m}{\textstyle\bigcup}{\operatorname{ns}}(P_{k_j}). \end{align} $$

Let f and g be the functions on $\omega $ defined by

$$ \begin{align*} f(m) & ={\textstyle\bigcup}{\operatorname{ns}}(P_{k_m})\setminus\bigl(B\cup\bigcup_{j<m}{\textstyle\bigcup}{\operatorname{ns}}(P_{k_j})\bigr),\\ g(m) & =\{[x]_{P_{k_m}}\cap B\mid x\in f(m)\}. \end{align*} $$

By (3), for every $m\in \omega $ , $g(m)$ is a finitary partition of a subset of B, and hence $\sim _{g(m)}$ is an element of $\mathscr {P}(B^2)$ . Since $\mathscr {P}(B^2)$ is Dedekind finite by Fact 2.6, there are least $l_0,l_1\in \omega $ with $l_0<l_1$ such that ${\sim _{g(l_0)}}={\sim _{g(l_1)}}$ , and thus $g(l_0)=g(l_1)$ . Let

$$\begin{align*}D=\bigl\{\{x,y\}\bigm|x\in f(l_0),y\in f(l_1)\text{ and }[x]_{P_{k_{l_0}}}\cap B=[y]_{P_{k_{l_1}}}\cap B\bigr\}. \end{align*}$$

Since $l_0<l_1$ , $f(l_0)\cap f(l_1)=\varnothing $ , and thus, by (3), the sets in D are pairwise disjoint. By (4), $f(m)\neq \varnothing $ for all $m\in \omega $ , and since $g(l_0)=g(l_1)$ , it follows that $D\neq \varnothing $ . Now, we define

$$\begin{align*}Q_n=D\cup\{\{z\}\mid z\in A\setminus\textstyle\bigcup D\}. \end{align*}$$

Then $Q_n$ is a finitary partition of A such that ${\operatorname {ns}}(Q_n)=D\neq \varnothing $ ; since $B\cap \bigcup D=\varnothing $ , it follows that $\bigcup {\operatorname {ns}}(Q_i)\cap \bigcup {\operatorname {ns}}(Q_n)=\varnothing $ for all $i<n$ .

Finally,

$$\begin{align*}Q=\bigcup_{n\in\omega}{\operatorname{ns}}(Q_n)\cup\bigl\{\{z\}\bigm|z\in A\setminus\bigcup_{n\in\omega}{\textstyle\bigcup}{\operatorname{ns}}(Q_n)\bigr\} \end{align*}$$

is a finitary partition of A such that ${\operatorname {ns}}(Q)=\bigcup _{n\in \omega }{\operatorname {ns}}(Q_n)$ is power Dedekind infinite, which is a contradiction.

(ii) ${}\Rightarrow {}$ (iii). Suppose that P is a finitary partition of A such that ${\operatorname {ns}}(P)$ is power Dedekind infinite. Let p be a surjection from ${\operatorname {ns}}(P)$ onto $\omega $ . Then the function h on $\mathscr {P}(\omega )$ defined by

$$\begin{align*}h(u)=p^{-1}[u]\cup\{\{z\}\mid z\in A\setminus\textstyle\bigcup p^{-1}[u]\} \end{align*}$$

is an injection from $\mathscr {P}(\omega )$ into $\mathscr {B}(A)$ .

(iii) ${}\Rightarrow {}$ (i). Obviously.

Proof Assume towards a contradiction that $\mathscr {B}(A)$ is Dedekind infinite and there exists a Dedekind finite-to-one function from $\mathscr {B}(A)$ to ${\operatorname {seq}}(A)$ . If A is Dedekind infinite, then ${\operatorname {seq}}(A)\approx {\operatorname {seq}^{1-1}}(A)$ by Fact 2.14, contradicting Corollary 4.9. Otherwise, by Fact 2.13, there is a Dedekind finite-to-one function from ${\operatorname {seq}}(A)$ to $\omega $ . By Theorem 4.13, $\mathscr {B}(\omega )\approx \mathscr {P}(\omega )\preccurlyeq \mathscr {B}(A)$ , and therefore there is a Dedekind finite-to-one function from $\mathscr {B}(\omega )$ to $\omega $ , contradicting again Corollary 4.9.

Proof For all non-empty sets A, if $|\mathscr {B}(A)|=|\mathrm {seq}(A)|$ , then it follows from Fact 2.12 that $\mathscr {B}(A)$ is Dedekind infinite, contradicting Corollary 4.14.

Proof Let $n\in \omega $ and let A be a set with at least $2n(2^{n+1}-1)$ elements. Since $2^{i}=1+\sum _{k<i}2^k$ , we can choose $2n(2^{n+1}-1)$ distinct elements of A so that they are divided into $n+1$ sets $H_i$ ( $i\leqslant n$ ) with

$$\begin{align*}H_i=\{a_{i,j}\mid j<2n\}\cup\{b_{i,x}\mid x\in H_k\text{ for some }k<i\}. \end{align*}$$

We construct an injection f from $A^n$ into ${\mathscr {B}_{\operatorname {fin}}}(A)$ as follows. Without loss of generality, assume that $A\cap \omega =\varnothing $ .

Let $s\in A^n$ . Let $i_s$ be the least $i\leqslant n$ for which $\mathrm {ran}(s)\cap H_i=\varnothing $ . There is such an i because $|\mathrm {ran}(s)|\leqslant n$ . Let $t_s$ be the function on n defined by

$$\begin{align*}t_s(j)= \begin{cases} s(j), & \text{if}\ s(j)\neq s(k)\ \text{for all}\ k<j,\\ \max\{k<j\mid s(j)=s(k)\}, & \text{otherwise.} \end{cases} \end{align*}$$

Clearly, $t_s\in {\operatorname {seq}^{1-1}}(A\cup n)$ . Let $u_s$ be the function on n defined by

$$\begin{align*}u_s(j)= \begin{cases} a_{i_s,n+t_s(j)}, & \text{if}\ t_s(j)\in n,\\ b_{i_s,t_s(j)}, & \text{if}\ t_s(j)\in H_k\ \text{for some}\ k<i_s,\\ t_s(j), & \text{otherwise.} \end{cases} \end{align*}$$

Then it is easy to see that $u_s\in {\operatorname {seq}^{1-1}}(A)$ . Now, we define

$$\begin{align*}f(s)=\bigl\{\{a_{i_s,j},u_s(j)\}\bigm|j<n\bigr\}\cup\bigl\{\{z\}\bigm|z\in A\setminus(\{a_{i_s,j}\mid j<n\}\cup{\operatorname{ran}}(u_s))\bigr\}. \end{align*}$$

Clearly, $f(s)\in {\mathscr {B}_{\operatorname {fin}}}(A)$ . We prove that f is injective by showing that s is uniquely determined by $f(s)$ in the following way.

First, $i_s$ is the least $i\leqslant n$ such that $H_i\cap \bigcup {\operatorname {ns}}(f(s))\neq \varnothing $ . Second, $u_s$ is the function on n such that $\{a_{i_s,j},u_s(j)\}\in f(s)$ for all $j<n$ . Then, $t_s$ is the function on n such that, for every $j<n$ , either $t_s(j)$ is the unique element of n for which ${u_s(j)=a_{i_s,n+t_s(j)}}$ , or $t_s(j)$ is the unique element of $\bigcup _{k<i_s}H_k$ for which ${u_s(j)=b_{i_s,t_s(j)}}$ , or $t_s(j)=u_s(j)\notin H_{i_s}$ . Finally, s is the function on n recursively determined by

$$\begin{align*}s(j)= \begin{cases} t_s(j), & \text{if}\ t_s(j)\in A,\\ s(t_s(j)), & \text{otherwise.} \end{cases} \end{align*}$$

Hence, f is an injection from $A^n$ into ${\mathscr {B}_{\operatorname {fin}}}(A)$ .

Proof By Lemma 4.16, $|A^n|\leqslant |\mathscr {B}_{\mathrm {fin}}(A)|\leqslant |\mathscr {B}(A)|$ . If $|\mathscr {B}(A)|=|A^n|$ , since the injection constructed in the proof of Lemma 4.16 is not surjective, $\mathscr {B}(A)$ is Dedekind infinite, contradicting Corollary 4.14. Thus, $|A^n|<|\mathscr {B}(A)|$ .

Proof Let h be an injection from $\omega $ into A. By the proof of Lemma 4.16, from $h{\upharpoonright }(2n(2^{n+1}-1))$ , we can explicitly define an injection

$$\begin{align*}f_n:A^n\to\{P\in\mathscr{B}(A)\mid|\mathrm{ns}(P)|=n\}. \end{align*}$$

Then $\bigcup _{n\in \omega }f_n$ is an injection from ${\operatorname {seq}}(A)$ into ${\mathscr {B}_{\operatorname {fin}}}(A)$ .

Proof Let P be a finitary partition of A without singleton blocks, and let f be a surjection from A onto $\alpha $ , where $\alpha $ is an infinite ordinal. Let

$$\begin{align*}Q=\{f[E]\mid E\in P\}. \end{align*}$$

Clearly, $Q\subseteq \operatorname {fin}(\alpha )$ . By Lemma 4.4, we can explicitly define an injection ${p:\mathrm {fin}(\alpha )\to \alpha} $ . Let R be the well-ordering of Q induced by p; that is, $R=\{(a,b)\mid a,b\in Q\text { and }p(a)<p(b)\}$ . Since P is a partition of A, Q is a cover of $\alpha $ . Define a function h from $\alpha $ to Q by setting, for $\beta \in \alpha $ ,

$$\begin{align*}h(\beta)=\text{the}\ R\text{-least }c\in Q\text{ such that }\beta\in c. \end{align*}$$

Since $\beta \in h(\beta )$ and $h(\beta )$ is finite for all $\beta \in \alpha $ , h is a finite-to-one function from $\alpha $ to Q. Hence, by Lemma 4.5, h explicitly provides an injection from $\alpha $ into Q. Since $p{\upharpoonright }Q$ is an injection from Q into $\alpha $ , it follows from Theorem 2.2 that we can explicitly define a bijection q between Q and $\alpha $ .

Now, the function g on A defined by

$$\begin{align*}g(x)=q(f[[x]_P]) \end{align*}$$

is a surjection from A onto $\alpha $ , and the function t on $\alpha $ defined by

$$\begin{align*}t(\beta)=\{E\in P\mid q(f[E])=\beta\} \end{align*}$$

is an auxiliary function for g.

Proof Let A be an infinite set and let P be a finitary partition of A without singleton blocks. Assume towards a contradiction that there is a surjection ${\Phi :A\twoheadrightarrow \mathscr {B}(A)}$ . By Corollary 2.20, $\mathscr {B}(A)$ is power Dedekind infinite, so is A. Since $\bigcup {\operatorname {ns}}(P)=A$ is power Dedekind infinite, so is ${\operatorname {ns}}(P)$ by Fact 2.5. Hence, by Theorem 4.13, $\mathscr {B}(A)$ is Dedekind infinite. Let h be an injection from $\omega $ into $\mathscr {B}(A)$ . In what follows, we get a contradiction by constructing by recursion an injection H from the proper class of ordinals into $\mathscr {B}(A)$ .

For $n\in \omega $ , take $H(n)=h(n)$ . Now, we assume that $\alpha $ is an infinite ordinal and $H{\upharpoonright }\alpha $ is an injection from $\alpha $ into $\mathscr {B}(A)$ . Then $(H{\upharpoonright }\alpha )^{-1}\circ \Phi $ is a surjection from a subset of A onto $\alpha $ and thus can be extended by zero to a surjection $f:A\twoheadrightarrow \alpha $ . By Lemma 4.20, from P and f, we can explicitly define a surjection $g:A\twoheadrightarrow \alpha $ and an auxiliary function t for g. Then $(H{\upharpoonright }\alpha )\circ g$ is a surjection from A onto $H[\alpha ]$ and $t\circ (H{\upharpoonright }\alpha )^{-1}$ is an auxiliary function for $(H{\upharpoonright }\alpha )\circ g$ . Hence, it follows from Lemma 4.2 that we can explicitly define an $H(\alpha )\in \mathscr {B}(A)\setminus H[\alpha ]$ from $H{\upharpoonright }\alpha $ (and $P,\Phi $ ).

Proof Let A be an infinite set and let P be a finitary partition of A without singleton blocks. Assume towards a contradiction that there is a finite-to-one function from $\mathscr {B}(A)$ to $A^n$ for some $n\in \omega $ . By Corollary 2.20, $\mathscr {B}(A)$ is power Dedekind infinite, so is A by Facts 2.5 and 2.6. Since $\bigcup {\operatorname {ns}}(P)=A$ is power Dedekind infinite, so is ${\operatorname {ns}}(P)$ by Fact 2.5. Hence, by Theorem 4.13, $\mathscr {B}(A)$ is Dedekind infinite, contradicting Corollary 4.14.

Proof See [Reference Shen12, Corollary 3.7].

Proof Let A be an infinite set. By Fact 2.18, $|\mathscr {B}_{\mathrm {fin}}(A)|\leqslant |\mathrm {Part}_{\mathrm {fin}}(A)|$ . Assume $|\mathrm {Part}_{\mathrm {fin}}(A)|=|\mathscr {B}_{\mathrm {fin}}(A)|$ . Since the injection constructed in the proof of Fact 2.18 is not surjective, ${\operatorname {Part}_{\operatorname {fin}}}(A)$ is Dedekind infinite, and thus A is power Dedekind infinite by Corollary 2.16. Now, by Fact 2.19, $|\mathscr {P}(A)|\leqslant |\mathrm {Part}_{\mathrm {fin}}(A)|=|\mathscr {B}_{\mathrm {fin}}(A)|$ , contradicting Corollary 4.24. Hence, $|\mathscr {B}_{\mathrm {fin}}(A)|<|\mathrm {Part}_{\mathrm {fin}}(A)|$ .

Proof Let $m\geqslant 3$ . Then $B_m>4$ . It suffices to prove that $B_m$ is not divisible by  $8$ . By [Reference Lunnon, Pleasants and Stephens7, Theorem 6.4], $B_{n+24}\equiv B_n\pmod {8}$ for all $n\in \omega $ . But $B_n$ modulo $8$ for n from $0$ to $23$ are

$$\begin{align*}1,1,2,5,7,4,3,5,4,3,7,2,5,5,2,1,3,4,7,1,4,7,3,2. \end{align*}$$

Hence, $B_m$ is not divisible by $8$ .

Proof See [Reference Shen13, Theorem 3.2].

Proof If A is a singleton, $|\mathscr {P}(A)|=2\neq 1=|\mathscr {B}_{\mathrm {fin}}(A)|$ . Suppose $|A|\geqslant 2$ , and fix two distinct elements $a,b$ of A. Assume toward a contradiction that there is a bijection $\Phi $ between $\mathscr {P}(A)$ and ${\mathscr {B}_{\operatorname {fin}}}(A)$ . We define by recursion an injection f from $\omega $ into $\operatorname {fin}(\mathscr {P}(A))$ as follows.

Take $f(0)=\{\{a\},\{b\}\}$ . Let $n\in \omega $ , and assume that $f(0),\dots ,f(n)$ have been defined and are pairwise distinct elements of $\operatorname {fin}(\mathscr {P}(A))$ . Let $\sim $ be the equivalence relation on A defined by

$$\begin{align*}x\sim y\quad\text{if and only if}\quad\forall C\in f(0)\cup\dots\cup f(n)(x\in C\leftrightarrow y\in C). \end{align*}$$

Since $f(0),\dots ,f(n)$ are finite, the quotient set $A/{\sim }$ is a finite partition of A. Let $k=|A/{\sim }|$ and let $U=\{\bigcup W\mid W\subseteq A/{\sim }\}$ . Then $|U|=2^k$ and

(5) $$ \begin{align} f(0)\cup\dots\cup f(n)\subseteq U. \end{align} $$

Since $\{a\},\{b\}\in A/{\sim }$ , we have $k\geqslant 2$ . Let $D=\bigcup \{\bigcup {\operatorname {ns}}(P)\mid P\in \Phi [U]\}$ . Since U is finite and $\Phi [U]\subseteq {\mathscr {B}_{\operatorname {fin}}}(A)$ , it follows that D is finite. Let $m=|D|$ and let $E=\{P\in {\mathscr {B}_{\operatorname {fin}}}(A)\mid \bigcup {\operatorname {ns}}(P)\subseteq D\}$ . Then $|E|=B_m$ and $\Phi [U]\subseteq E$ . Hence, $2^k=|U|=|\Phi [U]|\leqslant |E|=B_m$ . Since $k\geqslant 2$ , we have $m\geqslant 3$ , which implies that $B_m\neq 2^k$ by Lemma 4.26, and hence $\Phi [U]\subset E$ . Now, we define $f(n+1)=\Phi ^{-1}[E\setminus \Phi [U]]$ . Then $f(n+1)$ is a non-void finite subset of $\mathscr {P}(A)$ . By (5), it follows that $f(n+1)$ is disjoint from each of $f(0),\dots ,f(n)$ , and thus is distinct from each of them.

The existence of the above injection f shows that $\operatorname {fin}(\mathscr {P}(A))$ is Dedekind infinite, which implies that, by Lemma 4.27, A is power Dedekind infinite, contradicting Corollary 4.24.