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

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.

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).

-
Tip for searching the site, use (for example) +Dedekind +finite +power [axiom-of-choice] for a refined search which includes all the terms and posts in the tag [axiom-of-choice]. – Asaf Karagila Jan 1 '13 at 19:13
@AsafKaragila, ok great thanks. – alancalvitti Jan 1 '13 at 22:33

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.

-
Alternately, Andres illustrated the proof of that last result in his fine answer to this question. – Cameron Buie Jan 1 '13 at 18:40
Out of curiosity, Andres, "D-finite=finite" is a strictly stronger principle than "there are no amorphous sets", isn't it? So it's still consistent that there are infinite D-finite sets $A$ with $\mathcal{P}(A)$ D-finite, even if there aren't any amorphous sets? – Cameron Buie Jan 1 '13 at 18:43
@CameronBuie Yes, this is consistent. In the "Consequences of the axiom of choice" book, form 64 is "There are no amorphous sets", and form 82 is "$\mathcal P(X)$ is Dedekind-infinite for any infinite $X$". So we want a model where 64 holds and 82 fails. The book lists some examples. – Andrés Caicedo Jan 1 '13 at 20:02
@Cameron: As I wrote, in Cohen's first model the power set of an infinite set is Dedekind-infinite. This is inconsistent with the existence of an amorphous set, as the power set of an amorphous set is Dedekind-finite. – Asaf Karagila Jan 1 '13 at 22:40
@AndresCaicedo, curious why you refer to $\omega$ as opposed to $\mathbb N$? I thought $\omega$ denotes an ordinal, but don't see how that comes into play. – alancalvitti Jan 3 '13 at 12:59

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.

-
Hi Andreas. I should have said something about this. Yes, $F$ is the function one obtains when combining the two stages I described, and usually this is how the result is presented. But I feel that this "breaking" $F$ into stages helps me (one?) understand better what is happening, and lends itself to generalizations. – Andrés Caicedo Jan 2 '13 at 0:50
(And let me further add that we get more this way, not just injecting $\omega$ but $\mathcal P(\omega)$ into $\mathcal P^2(X)$.) – Andrés Caicedo Feb 17 '13 at 6:57

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.

-
Thanks Asaf, +1. I accepted Andres' answer but could have gone with yours too. Question: "consistent" here means w.r.t $ZF$? – alancalvitti Jan 1 '13 at 21:47
Yes, of course. Everything is relative to the consistency of ZF. – Asaf Karagila Jan 1 '13 at 21:55
The "reverse mathematics" folks don't have a say in that? What about the constructivists? I'm searching for the universal. – alancalvitti Jan 1 '13 at 21:58
But why should mathematics be applicable to things? – Asaf Karagila Jan 2 '13 at 7:05
@alancalvitti: I see. So because of the Banach-Tarski paradox, which is completely dissolved if you only discuss measurable sets, ALL GEOMETRY IS INVALID FOREVER! in ZFC? That's nonsense. That's taking up one single issue and blowing it up. As I keep pointing out, if we insist that all sets are Lebesgue measurable then we can partition the real numbers into more parts than points. Does that make more sense to you? Taking a set and slicing it up into strictly more non-empty parts than points? I don't know, I think it's weirder than the BT theorem. – Asaf Karagila Jan 3 '13 at 11:47

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".

-