Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
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
up vote 2 down vote accepted

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.

share|cite|improve this answer
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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.