2
$\begingroup$

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?

  • 0
    While not a question in classical cardinal arithmetics, this is a question about cardinals. I have added the relevant tag, but if anyone disagrees I am willing to debate this further.2012-05-11

1 Answers 1

2

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.

  • 1
    @Cameron: Amusingly enough this is exactly what I just thought and added before seeing your comment.2012-05-11