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
    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.2012-05-11
  • 0
    Because it isn't true.2012-05-11
  • 0
    Leon is interpreting me correctly.2012-05-11
  • 0
    Asaf, do you mean that the claim is incorrect, as I suspected, or that the proposed equivalence fails to hold?2012-05-11
  • 0
    Cameron: I posted an answer (which I was working on for roughly 16 minutes now).2012-05-11
  • 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.

  • 0
    Excellent! I thought they'd made a mistake, there, but I knew the result itself was valid.2012-05-11
  • 0
    Why is $\{\{x,f(x)\} \colon x \in X\}$ D-finite?2012-05-11
  • 0
    @Levon: It is the image of the injective map $x\mapsto\{x,f(x)\}$.2012-05-11
  • 0
    @Cameron: I see you took this from Herrlich's book. I noted a few mistakes there myself. Perhaps an errata page is in order.2012-05-11
  • 0
    Indeed, perhaps so. I believe that for the map to be injective, we will need to (and may, WLOG) assume that $X,Y$ are disjoint.2012-05-11
  • 1
    @Cameron: Amusingly enough this is exactly what I just thought and added before seeing your comment.2012-05-11