Is the powerset of every Dedekind-finite set Dedekind-finite?

Question

Is the powerset of every Dedekind-finite set Dedekind-finite?

I think this statement can be written in $\textbf{Set}$: If every mono (=injection) $f: A \to A$ is iso (=bijection), then every mono $g: 2^A \to 2^A$ is iso.

(Please edit if necessary)

Does the answer depend on some Choice principle?

Off-hand I don't see a referent to this. The Wikipedia entry for Dedekind-infinite only states that the powerset of a D-infinite set is D-infinite. (I tried searching Math.SE with the obvious keywords and faced ~5k entries).

Answer 1

No: Suppose $X$ is infinite. Then there is a surjection from the collection $Fin(X)$ of finite subsets of $X$ onto $\omega$, namely, $Y\mapsto|Y|$. Since $Fin(X)\subseteq\mathcal P(X)$, we get a surjection from $\mathcal P(X)$ onto $\omega$.

But if there is a surjection $\varphi$ from $A$ onto $B$, then there is an injection from $\mathcal P(B)$ into $\mathcal P(A)$, namely $Y\mapsto \varphi^{-1}(Y)=\{a\in A\mid \varphi(a)\in Y\}$.

In particular, $\mathcal P(\omega)$ (and therefore $\omega$) injects into $\mathcal P(\mathcal P(X))$ for any infinite set $X$. That is to say that $\mathcal P(\mathcal P(X))$ is always either finite, or D-infinite.

On the other hand, it is consistent that there are D-finite infinite sets $A$ such that $\mathcal P(A)$ is also D-finite. For example, any amorphous set $A$ is like this. Recall that $A$ is amorphous iff it is infinite but any subset of $A$ is either finite, or has finite complement in $A$.

The reason here is that if $A$ is amorphous, then there is no surjection from $A$ onto $\omega$. But one can check that the following are equivalent for any $X$:

• $\omega$ injects into $\mathcal P(X)$,
• $X$ surjects onto $\omega$.

So, if $A$ is amorphous, $\mathcal P(A)$ is D-finite. See this blog post of mine for this result, due to Kuratowski.

Answer 2

Check out this related question for some equivalences to that statement (and hopefully, an answer to your question). In particular, it's equivalent to the (very weak) choice principle "D-finite=finite".

Answer 3

Not without some choice. In fact if the power set of every D-finite set is D-finite, then there are no infinite D-finite sets.

It follows from the following results:

1. If $f\colon X\to\omega$ is surjective, then $\mathcal P(X)$ is D-infinite.

   To see that this holds, note that $n\mapsto\{x\in X\mid f(x)=n\}$ is an injection from $\omega$ into $\mathcal P(X)$, and this is an equivalent condition to D-infiniteness.

2. If $X$ is infinite then $\mathcal P(X)$ can be mapped onto $\omega$.

   To see this holds we can use the map: $A\mapsto\begin{cases} 0 & A\text{ infinite}\\ |A| &\text{otherwise.}\end{cases}$ is surjective because $X$ is infinite.

Now it follows, if $X$ is an infinite D-finite set, either $\mathcal P(X)$ is D-infinite and we are done; or $\mathcal P(X)$ is D-finite and can be mapped onto $\omega$, therefore $\mathcal{P(P(}X))$ is the power set of a D-finite set, and is D-infinite.

---

Some consistency remarks:

1. It is consistent that there are no infinite Dedekind-finite sets which cannot be mapped onto $\omega$. For example in Cohen's first model.

2. It is consistent that there infinite Dedekind-finite sets which cannot be mapped onto $\omega$. For example in models where there is an amorphous sets (sets which cannot be written as a disjoint union of two infinite sets).

3. The axiom "Every countable $\cal A$ of non-empty sets has an infinite $\cal B\subseteq A$ such that $\prod\cal B\neq\varnothing$", which is weaker than countable choice proper, implies that every D-finite is finite, so it implies that the power set of a D-finite set is D-finite.

Answer 4

The following is implicit in the answers given by Andres and Asaf, but it looks simpler, so it might be worthwhile to make it explicit. Let $X$ be any infinite set, possibly Dedekind-finite. Let $F$ be the function with domain $\omega$ defined by assigning to each natural number $n$ the family of all $n$-element subsets of $X$. Then $F$ is a one-to-one function from $\omega$ into $\mathcal P(\mathcal P(X))$, the power set of the power set of $X$. So if $X$ is D-finite, then either $X$ itself or $\mathcal P(X)$ is a D-finite set with D-infinite power set.