Every II-finite set is III-finite

Question

I need some help proving that if a set $X$ is II-finite then it is III-finite, i.e. if every non-empty family of subsets of $X$ which is linearly ordered by inclusion has a maximal element under inclusion then there is no one-to-one map from $\mathcal{P}(X)$ into a proper subset of $\mathcal{P}(X)$. I know this proof is in Tarki's "Sur Les Ensembles Finis" but it's in french and i don't understand it.

Answer 1

This can be obtained with the following theorem of Kuratowski:

$\omega\leq^*\mathfrak a\iff\omega\leq2^\mathfrak a$

Namely, there is a surjection from $A$ onto $\omega$ if and only if there is an injection from $\omega$ into $\mathcal P(A)$, which in turn is to say that there is an injection from $\mathcal P(A)$ into itself which is not a surjection.

---

Now assume that there is an injection from $\mathcal P(A)$ into a proper subset of itself, therefore there is an injection from $\omega$ into $\mathcal P(A)$, therefore there is a surjection from $f\colon A\to\omega$, and this surjection gives us a chain of subsets without a maximal element, namely $\{f^{-1}(\{0,\ldots,n\})\mid n\in\Bbb N\}$.

Answer 2

Revised, since there was an oversight in my original argument. I’ve now looked at Tarski’s paper; the very old-fashioned notation is a worse problem than the French. I’ve updated it and filled in some details.

The proof in question is on pages $94$ and $95$. In essence he starts by assuming that there is an injection $\varphi:\wp(X)\to\wp(X)$ such that $\varphi[\wp(X)]\subsetneqq\wp(X)$, picking $A_0^{(0)}\in\wp(X)\setminus\varphi[\wp(X)]$, and letting $A_{n+1}^{(0)}=\varphi(A_n^{(0)})$ for $n\in\omega$. Let $\mathscr{A}$ be the closure of the family $\{A_n^{(0)}:n\in\omega\}$ under finite intersections. If there is a sequence $\langle B_n:n\in\omega\rangle$ in $\mathscr{A}$ such that $B_n\supsetneqq B_{n+1}\ne\varnothing$ for each $n\in\omega$, let $D_n=B_{n+1}\setminus B_n$ for $n\in\omega$. The sets $D_n$ are pairwise disjoint and non-empty. For $n\in\omega$ let $C_n=\bigcup_{k\le n}D_k$; then $\{C_n:n\in\omega\}$ is a chain with no maximum element.

Assume, then, that no such sequence $\langle B_n:n\in\omega\rangle$ in $\mathscr{A}$ exists. Then in particular there is no strictly increasing sequence $\langle n_k:k\in\omega\rangle$ in $\omega$ such that

$$\bigcap_{k\le n}A_k^{(0)}\supsetneqq\bigcap_{k\le n+1}A_k^{(0)}$$

for each $k\in\omega$. Thus, there is an $n_0\in\omega$ such that for each $m>n_0$, either $A_m^{(0)}\subseteq\bigcap_{k\le n}A_k^{(0)}$, or $A_m^{(0)}\cap\bigcap_{k\le n}A_k^{(0)}=\varnothing$. It follows that there is a strictly increasing sequence $\langle m_k:k\in\omega\rangle$ in $\omega$ such that $m_0>n_0$, and either $A_{m_\ell}^{(0)}\subseteq\bigcap_{k\le n_0}A_k^{(0)}$ for each $\ell\in\omega$, or $A_{m_\ell}^{(0)}\cap\bigcap_{k\le n_0}A_k^{(0)}=\varnothing$ for each $\ell\in\omega$. For $k\in\omega$ let $A_k^{(1)}=A_{m_k}^{(0)}\setminus\bigcap_{k\le n_0}A_k^{(0)}$; the sets $A_k^{(1)}$ are distinct,

$$\bigcap_{k\in\omega}A_k^{(1)}\subseteq\bigcup_{k\in\omega}A_k^{(0)}\;,$$

and

$$\left(\bigcap_{k\le n_0}A_k^{(0)}\right)\cap\bigcup_{k\in\omega}A_k^{(1)}=\varnothing\;.$$

Recursively construct in this fashion sequences $\langle A_k^{(\ell)}:k\in\omega\rangle$ for $\ell\in\omega$ such that each $A_k^{(\ell)}\in\mathscr{A}$, and for each $\ell\in\omega$

$$\bigcap_{k\in\omega}A_k^{(\ell+1)}\subseteq\bigcup_{k\in\omega}A_k^{(\ell)}\;,$$

and

$$\left(\bigcap_{k\le n_\ell}A_k^{(\ell)}\right)\cap\bigcup_{k\in\omega}A_k^{(\ell+1)}=\varnothing\;.$$

Now for $\ell\in\omega$ let $D_\ell=\bigcap_{k\le n_\ell}A_k^{(\ell)}$; then $\{D_\ell:\ell\in\omega\}$ is a family of pairwise disjoint, non-empty subsets of $X$, and $\left\{\bigcup_{k\le\ell}D_k:\ell\in\omega\right\}$ is a chain in $\wp(X)$ with no largest element.