Fact 2.2. $\omega _1\preccurlyeq ^\ast \operatorname {\mathrm {\mathscr {P}}}(\omega )$ .

Proof Cf. [Reference Halbeisen3, Theorem 5.11].

Proof Cf. [Reference Levy7, III.2.8].

Proof Cf. [Reference Halbeisen3, Proposition 5.4].

Proof It suffices to take $A=\{x\in \operatorname {\mathrm {dom}}(f)\mid x\notin f(x)\}$ .

Proof Cf. [Reference Specker12, 2.1] or [Reference Levy7, IV.2.24].

Proof Cf. [Reference Halbeisen3, Theorem 5.19].

Proof Let $\alpha $ be an infinite ordinal. Let

$$ \begin{align*} \exp(\omega,\alpha)=\bigl\{t:\alpha\to\omega\bigm|\{\gamma<\alpha\mid t(\gamma)\neq 0\}\text{ is finite}\bigr\}, \end{align*} $$

and let r be the right lexicographic ordering of $\exp (\omega ,\alpha )$ . It is easy to verify that r well-orders $\exp (\omega ,\alpha )$ and the order type of $\langle \exp (\omega ,\alpha ),r\rangle $ is $\omega ^\alpha $ (cf. [Reference Levy7, IV.2.10]). Let g be the unique isomorphism of $\langle \omega ^\alpha ,\in \rangle $ onto $\langle \exp (\omega ,\alpha ),r\rangle $ . Let h be the function on $\exp (\omega ,\alpha )$ defined by

$$ \begin{align*} h(t)=t{\upharpoonright}\{\gamma<\alpha\mid t(\gamma)\neq 0\}. \end{align*} $$

Then h is an injection from $\exp (\omega ,\alpha )$ into $\operatorname {\mathrm {fin}}(\alpha \times \omega )$ . By Lemmas 3.2 and 3.3, we can explicitly define an injection $p:\operatorname {\mathrm {fin}}(\alpha \times \omega )\to \alpha $ . Therefore, $p\circ h\circ g$ is an injection from $\omega ^\alpha $ into $\alpha $ . Now, since the function that maps each $\gamma <\alpha $ to $\omega ^\gamma $ is an injection from $\alpha $ into $\omega ^\alpha $ , it follows from Theorem 2.3 that we can explicitly define a bijection $f:\omega ^\alpha \to \alpha $ .

Fact 3.5. If $A=B\cup C$ is a set of ordinals which is of order type $\omega ^\delta $ , then B or C has order type $\omega ^\delta $ .

Proof Cf. [Reference Levy7, IV.2.22(vii)].

Proof Let $\alpha $ be an uncountable ordinal and let f be a surjection from $\omega \times M$ onto $\alpha $ . For each $n\in \omega $ , let $A_n=f[\{n\}\times M]$ , let $\delta _n$ be the order type of $A_n$ , and let $g_n$ be the unique isomorphism of $\delta _n$ onto $A_n$ . Let $\delta =\bigcup _{n\in \omega }\delta _n$ and let g be the function on $\omega \times \delta $ defined by

$$ \begin{align*} g(n,\gamma)= \begin{cases} g_n(\gamma), & \text{if }\gamma<\delta_n,\\ 0, & \text{otherwise.} \end{cases} \end{align*} $$

Then g is a surjection from $\omega \times \delta $ onto $\alpha $ , which implies that $\delta $ is also an uncountable ordinal. Hence, it follows from Lemma 3.2 that we can explicitly define a surjection from $\delta $ onto $\alpha $ . So it suffices to explicitly define a surjection from M onto $\delta $ . We consider the following two cases:

Case 1. There exists an $n\in \omega $ such that $\delta _n=\delta $ . Let $n_0$ be the least natural number such that $\delta _{n_0}=\delta $ . Then the function that maps each $x\in M$ to $g_{n_0}^{-1}(f(n_0,x))$ is a surjection of M onto $\delta $ .

Case 2. If we are not in Case 1, then, since $\delta =\bigcup _{n\in \omega }\delta _n$ , $\delta $ is a limit ordinal. Since $\delta>\omega $ , without loss of generality, assume that $\delta _n$ is infinite for all $n\in \omega $ . For each $n\in \omega $ , let $\beta _n=\omega ^{\delta _n}$ . By Lemma 3.4, for each $n\in \omega $ , we can explicitly define a bijection $p_n:\beta _n\to \delta _n$ . For each $n\in \omega $ , let $h_n$ be the function on M defined by $h_n(x)=p_n^{-1}(g_n^{-1}(f(n,x)))$ . Then, for any $n\in \omega $ , $h_n$ is a surjection from M onto $\beta _n$ . Let $\beta =\omega ^\delta $ . Clearly, $\beta =\bigcup _{n\in \omega }\beta _n$ . By Lemma 3.4, it suffices to explicitly define a surjection $h:M\twoheadrightarrow \beta $ .

We first define by recursion two sequences $\langle B_n\rangle _{n\in \omega }$ and $\langle q_n\rangle _{n\in \omega }$ as follows. Let $B_0=M$ . Let $n\in \omega $ and assume that $B_n\subseteq M$ has been defined so that

(1) $$ \begin{align} \beta=\bigcup\bigl\{\eta\bigm|\eta=\beta_k\text{ for some }k\in\omega\text{ such that }h_k[B_n]\text{ has order type }\beta_k\bigr\}. \end{align} $$

We define a subset $B_{n+1}$ of $B_n$ and a surjection $q_n:B_n\setminus B_{n+1}\twoheadrightarrow \beta _n$ as follows. Since $\beta _n<\beta $ , by (1), there is a least $k\in \omega $ such that $\beta _n<\beta _k$ and $h_k[B_n]$ has order type $\beta _k$ . Let t be the unique isomorphism of $h_k[B_n]$ onto $\beta _k$ , and let

$$ \begin{align*} D=\{x\in B_n\mid t(h_k(x))<\beta _n\}.\end{align*} $$

Since $\beta _k=\omega ^{\delta _k}$ is closed under ordinal addition, it follows that $\beta _n\cdot 2<\beta _k$ . Now, if (1) holds with $B_n$ replaced by D, we define $B_{n+1}=D$ and let $q_n$ be the function on $B_n\setminus D$ defined by

$$ \begin{align*} q_n(x)= \begin{cases} \text{the unique }\gamma<\beta_n\text{ such that }t(h_k(x))=\beta_n+\gamma, & \text{if }t(h_k(x))<\beta_n\cdot2,\\ 0, & \text{otherwise.} \end{cases} \end{align*} $$

Otherwise, it follows from (1) and Fact 3.5 that (1) holds with $B_n$ replaced by $B_n\setminus D$ , and then we define $B_{n+1}=B_n\setminus D$ and let $q_n$ be the function on D defined by $q_n(x)=t(h_k(x))$ . Clearly, in either case, $B_{n+1}\subseteq B_n$ , (1) holds with $B_n$ replaced by $B_{n+1}$ , and $q_n$ is a surjection from $B_n\setminus B_{n+1}$ onto $\beta _n$ . Now, it suffices to define $h=\bigcup _{n\in \omega }q_n\cup (\bigcap _{n\in \omega }B_n\times \{0\})$ .

Proof Cf. [Reference Shen8, Theorem 5.3].

Proof Assume towards a contradiction that there exist an infinite set M and a surjection $\Phi :\omega \times M\twoheadrightarrow \operatorname {\mathrm {\mathscr {P}}}(M)$ . We first prove that M is power Dedekind infinite. Let $\Psi $ be the restriction of $\Phi $ to the set $\{(n,x)\in \omega \times M\mid \Phi (n,x)=\Phi (k,x)\text { for no }k<n\}$ . Clearly, $\Psi $ is a surjection from a subset of $\omega \times M$ onto $\operatorname {\mathrm {\mathscr {P}}}(M)$ such that, for all $x\in M$ , $\Psi {\upharpoonright }(\omega \times \{x\})$ is injective. If M is power Dedekind finite, then $\operatorname {\mathrm {dom}}(\Psi )\cap (\omega \times \{x\})$ is finite for all $x\in M$ , and thus there exists a finite-to-one function from $\operatorname {\mathrm {dom}}(\Psi )$ to M, contradicting Lemma 3.7. Hence, M is power Dedekind infinite.

Now, it follows from Theorem 2.4 that $\omega \preccurlyeq ^\ast M$ , and thus, by Fact 2.2, $\omega _1\preccurlyeq ^\ast \operatorname {\mathrm {\mathscr {P}}}(\omega )\preccurlyeq \operatorname {\mathrm {\mathscr {P}}}(M)\preccurlyeq ^\ast \omega \times M$ , which implies that $\omega _1\preccurlyeq ^\ast M$ by Lemma 3.6 and hence $\omega _1\preccurlyeq \operatorname {\mathrm {\mathscr {P}}}(M)$ . Let h be an injection from $\omega _1$ into $\operatorname {\mathrm {\mathscr {P}}}(M)$ . In what follows, we get a contradiction by constructing by recursion an injection H from $\mathrm {Ord}$ (the class of all ordinals) into $\operatorname {\mathrm {\mathscr {P}}}(M)$ .

For $\gamma <\omega _1$ , we take $H(\gamma )=h(\gamma )$ . Now, we assume that $\alpha $ is an uncountable ordinal and that $H{\upharpoonright }\alpha $ is an injection from $\alpha $ into $\operatorname {\mathrm {\mathscr {P}}}(M)$ . Then $(H{\upharpoonright }\alpha )^{-1}\circ \Phi $ is a surjection from a subset of $\omega \times M$ onto $\alpha $ and hence can be extended by zero to a surjection $f:\omega \times M\twoheadrightarrow \alpha $ . By Lemma 3.6, f explicitly provides a surjection $g:M\twoheadrightarrow \alpha $ . Since $(H{\upharpoonright }\alpha )\circ g$ is a surjection from M onto $H[\alpha ]$ , it follows from Theorem 3.1 that we can explicitly define an $H(\alpha )\in \operatorname {\mathrm {\mathscr {P}}}(M)\setminus H[\alpha ]$ from $H{\upharpoonright }\alpha $ (and $\Phi $ ).

Proof By Lemma 3.2, we can explicitly define an injection $p:\alpha \times \alpha \to \alpha $ . Let f be the function on $\operatorname {\mathrm {\mathscr {P}}}(\alpha )$ defined by

$$ \begin{align*} f(A)= \begin{cases} p[A\times\{0\}], & \text{if }A\text{ is infinite,}\\ p[(\alpha\setminus A)\times\{1\}], & \text{otherwise.} \end{cases} \end{align*} $$

Then it is easy to see that f is an injection from $\operatorname {\mathrm {\mathscr {P}}}(\alpha )$ into $\operatorname {\mathrm {\mathscr {P}_{\infty }}}(\alpha )$ .

Proof Cf. [Reference Shen8, Lemma 5.2].

Proof Assume towards a contradiction that there exist an infinite set M and a set N such that there exist a finite-to-one function $f:N\to M$ and a surjection $\Phi :N\twoheadrightarrow \operatorname {\mathrm {\mathscr {P}_{\infty }}}(M)$ . Clearly, the function that maps each cofinite subset A of M to the cardinality of $M\setminus A$ is a surjection from a subset of $\operatorname {\mathrm {\mathscr {P}_{\infty }}}(M)$ onto $\omega $ , and hence $\omega \preccurlyeq ^\ast \operatorname {\mathrm {\mathscr {P}_{\infty }}}(M)\preccurlyeq ^\ast N$ , which implies that $\omega \preccurlyeq ^\ast M$ by Lemma 4.2. Thus $\omega \preccurlyeq \operatorname {\mathrm {\mathscr {P}_{\infty }}}(\omega )\preccurlyeq \operatorname {\mathrm {\mathscr {P}_{\infty }}}(M)$ . Let h be an injection from $\omega $ into $\operatorname {\mathrm {\mathscr {P}_{\infty }}}(M)$ . In what follows, we get a contradiction by constructing by recursion an injection H from $\mathrm {Ord}$ into $\operatorname {\mathrm {\mathscr {P}_{\infty }}}(M)$ .

For $n\in \omega $ , we take $H(n)=h(n)$ . Now, we assume that $\alpha $ is an infinite ordinal and that $H{\upharpoonright }\alpha $ is an injection from $\alpha $ into $\operatorname {\mathrm {\mathscr {P}_{\infty }}}(M)$ . Then $(H{\upharpoonright }\alpha )^{-1}\circ \Phi $ is a surjection from a subset of N onto $\alpha $ and hence can be extended by zero to a surjection $g:N\twoheadrightarrow \alpha $ . By Lemma 4.2, from M, f, and g, we can explicitly define a surjection $p:M\twoheadrightarrow \alpha $ . Then the function q on $\operatorname {\mathrm {\mathscr {P}_{\infty }}}(\alpha )$ defined by $q(A)=p^{-1}[A]$ is an injection from $\operatorname {\mathrm {\mathscr {P}_{\infty }}}(\alpha )$ into $\operatorname {\mathrm {\mathscr {P}_{\infty }}}(M)$ , and thus it follows from Lemma 4.1 that we can explicitly define an injection $t:\operatorname {\mathrm {\mathscr {P}}}(\alpha )\to \operatorname {\mathrm {\mathscr {P}_{\infty }}}(M)$ . Then $t^{-1}\circ (H{\upharpoonright }\alpha )$ is a bijection between a subset of $\alpha $ and $t^{-1}[H[\alpha ]]$ , and thus can be extended by zero to a function $u:\alpha \to \operatorname {\mathrm {\mathscr {P}}}(\alpha )$ . By Theorem 3.1, we can explicitly define a $B\in \operatorname {\mathrm {\mathscr {P}}}(\alpha )\setminus \operatorname {\mathrm {ran}}(u)$ . Since $t^{-1}[H[\alpha ]]\subseteq \operatorname {\mathrm {ran}}(u)$ , it follows that $B\notin t^{-1}[H[\alpha ]]$ , which implies that $t(B)\notin H[\alpha ]$ . Now, it suffices to define $H(\alpha )=t(B)$ .

Proof We proceed along the lines of the proof of Theorem 3.8. Assume towards a contradiction that there exist an infinite set M and a surjection $\Phi :\omega \times M\twoheadrightarrow \operatorname {\mathrm {\mathscr {P}_{\infty }}}(M)$ . We first prove that M is power Dedekind infinite. Let $\Psi $ be the restriction of $\Phi $ to the set $\{(n,x)\in \omega \times M\mid \Phi (n,x)=\Phi (k,x)\text { for no }k<n\}$ . Clearly, $\Psi $ is a surjection from a subset of $\omega \times M$ onto $\operatorname {\mathrm {\mathscr {P}_{\infty }}}(M)$ such that, for all $x\in M$ , $\Psi {\upharpoonright }(\omega \times \{x\})$ is injective. If M is power Dedekind finite, then $\operatorname {\mathrm {dom}}(\Psi )\cap (\omega \times \{x\})$ is finite for all $x\in M$ , and thus there exists a finite-to-one function from $\operatorname {\mathrm {dom}}(\Psi )$ to M, contradicting Lemma 4.3. Hence, M is power Dedekind infinite.

Now, it follows from Theorem 2.4 that $\omega \preccurlyeq ^\ast M$ , and thus, by Fact 2.2 and Lemma 4.1, $\omega _1\preccurlyeq ^\ast \operatorname {\mathrm {\mathscr {P}}}(\omega )\preccurlyeq \operatorname {\mathrm {\mathscr {P}_{\infty }}}(\omega )\preccurlyeq \operatorname {\mathrm {\mathscr {P}_{\infty }}}(M)\preccurlyeq ^\ast \omega \times M$ , which implies that $\omega _1\preccurlyeq ^\ast M$ by Lemma 3.6 and hence $\omega _1\preccurlyeq \operatorname {\mathrm {\mathscr {P}_{\infty }}}(\omega _1)\preccurlyeq \operatorname {\mathrm {\mathscr {P}_{\infty }}}(M)$ . Let h be an injection from $\omega _1$ into $\operatorname {\mathrm {\mathscr {P}_{\infty }}}(M)$ . In what follows, we get a contradiction by constructing by recursion an injection H from $\mathrm {Ord}$ into $\operatorname {\mathrm {\mathscr {P}_{\infty }}}(M)$ .

For $\gamma <\omega _1$ , we take $H(\gamma )=h(\gamma )$ . Now, we assume that $\alpha $ is an uncountable ordinal and that $H{\upharpoonright }\alpha $ is an injection from $\alpha $ into $\operatorname {\mathrm {\mathscr {P}_{\infty }}}(M)$ . Then $(H{\upharpoonright }\alpha )^{-1}\circ \Phi $ is a surjection from a subset of $\omega \times M$ onto $\alpha $ and hence can be extended by zero to a surjection $f:\omega \times M\twoheadrightarrow \alpha $ . By Lemma 3.6, f explicitly provides a surjection $g:M\twoheadrightarrow \alpha $ . Then the function q on $\operatorname {\mathrm {\mathscr {P}_{\infty }}}(\alpha )$ defined by $q(A)=g^{-1}[A]$ is an injection from $\operatorname {\mathrm {\mathscr {P}_{\infty }}}(\alpha )$ into $\operatorname {\mathrm {\mathscr {P}_{\infty }}}(M)$ , and thus it follows from Lemma 4.1 that we can explicitly define an injection $t:\operatorname {\mathrm {\mathscr {P}}}(\alpha )\to \operatorname {\mathrm {\mathscr {P}_{\infty }}}(M)$ . Then $t^{-1}\circ (H{\upharpoonright }\alpha )$ is a bijection between a subset of $\alpha $ and $t^{-1}[H[\alpha ]]$ , and thus can be extended by zero to a function $u:\alpha \to \operatorname {\mathrm {\mathscr {P}}}(\alpha )$ . By Theorem 3.1, we can explicitly define a $B\in \operatorname {\mathrm {\mathscr {P}}}(\alpha )\setminus \operatorname {\mathrm {ran}}(u)$ . Since $t^{-1}[H[\alpha ]]\subseteq \operatorname {\mathrm {ran}}(u)$ , it follows that $B\notin t^{-1}[H[\alpha ]]$ , which implies that $t(B)\notin H[\alpha ]$ . Now, it suffices to define $H(\alpha )=t(B)$ .