# Equivalences to “D-finite = finite”

By a D-finite set, we mean a set admitting no injection from the natural numbers (or equivalently, a set not in bijection with any proper subset).

I have encountered a proof that the following are equivalent in ZF:

A. Every D-finite set is finite.

B. D-finite unions of D-finite sets are D-finite.

C. Images of D-finite sets are D-finite.

D. Power sets of D-finite sets are D-finite.

C implies D implies A implies B is achieved without difficulty, but it seems to me that they took a circular approach to showing that B implies C. They proceeded as follows:

Assume $X$ D-finite, $f:X\to Y$ a surjection. Then $Y=\bigcup_{x\in X}\{f(x)\}$, so as a D-finite union of D-finite sets, $Y$ is D-finite.

Of course, singletons are D-finite since finite, and of course $Y$ is the union of said singletons since $f$ is surjective. However, since the set of such singletons is in bijection with $Y$, isn't the D-finite union claim tantamount to claiming the conclusion is true?

Does anyone know of an alternate approach one can take to prove these are all equivalent?

-
I think the OP means that if we want to use B we need to show that $\{\{f(x)\} \colon x \in X\}$ is D-finite, which isn't trivial. – Levon Haykazyan May 11 '12 at 20:39
Because it isn't true. – Asaf Karagila May 11 '12 at 20:39
Leon is interpreting me correctly. – Cameron Buie May 11 '12 at 20:41
Asaf, do you mean that the claim is incorrect, as I suspected, or that the proposed equivalence fails to hold? – Cameron Buie May 11 '12 at 20:43
Cameron: I posted an answer (which I was working on for roughly 16 minutes now). – Asaf Karagila May 11 '12 at 20:44

The proof you present that B implies C is wrong. When we say that D-finite unions of D-finite sets are D-finite we mean that if $D$ is D-finite and for all $x\in D$, $x$ is $D$ finite, then $\bigcup D$ is D-finite.

However it is perfectly fine to have a D-finite set mapped onto $\omega$, in which case this proof fails because the collection of singletons is countably infinite.

Suppose that D-finite unions of D-finite sets are D-finite, let $X$ be a D-finite set, and $f\colon X\to Y$ a surjective function. Without loss of generality we may assume that $X\cap Y=\varnothing$ as well. Consider the following union:

$$\bigcup\Big\{\{x,f(x)\}\mathrel{}\Big|\mathrel{} x\in X\Big\}=X\cup Y$$

We take union on the image of the function $x\mapsto\{x,f(x)\}$, which is injective and therefore preserves D-finiteness. If so, the union is a D-finite union of D-finite sets and therefore D-finite. We have that $Y$ is a subset of a D-finite set and therefore it is a D-finite set itself, as wanted.

-
Excellent! I thought they'd made a mistake, there, but I knew the result itself was valid. – Cameron Buie May 11 '12 at 20:49
Why is $\{\{x,f(x)\} \colon x \in X\}$ D-finite? – Levon Haykazyan May 11 '12 at 21:07
@Levon: It is the image of the injective map $x\mapsto\{x,f(x)\}$. – Asaf Karagila May 11 '12 at 21:08
@Cameron: I see you took this from Herrlich's book. I noted a few mistakes there myself. Perhaps an errata page is in order. – Asaf Karagila May 11 '12 at 21:13
@Cameron: Amusingly enough this is exactly what I just thought and added before seeing your comment. – Asaf Karagila May 11 '12 at 21:31