A is called D-finite if A is not containing countable subset.

With the above strange definition I need to show the following two properties:

  1. For a D-finite set A, and finite B, the union of A and B is D-finite.

  2. The union of two D-finite sets is D-finite.

By the way, can we construct such D-finite set?

Only hints...

Thank you.

  • 1
    $\begingroup$ Note: This concept is properly called Dedekind-finite, and the original formulation was less strange: Dedekind proposed that a "finite" set could be defined as one whose cardinality is different from any of its proper subsets. It is an instructive exercise to see that this is equivalent to your "strange" definition. $\endgroup$ – Henning Makholm Dec 15 '12 at 23:03
  • $\begingroup$ In addition to the suggestion by @Henning, I would also add the definition given in Brian's answer to the equivalence. $\endgroup$ – Asaf Karagila Dec 15 '12 at 23:10

We can't really construct an infinite D-finite set by defining it, simply because it is consistent that there are no such sets (i.e. all the D-finite sets are finite).

We can construct models in which the axiom of choice fails and there are infinite D-finite sets, but those constructions are difficult and involve forcing in many cases.

First note that a finite set is D-finite. So to solve the second question means to solve the first one as well.

To show that if $A$ and $B$ are D-finite then $A\cup B$ is also D-finite, assume by contradiction that $A\cup B$ is not D-finite then there is some $X\subseteq A\cup B$ such that $|X|=\aleph_0$. Consider $X\cap A$ and $X\cap B$, and show that at least one of those has size $\aleph_0$, in contradiction to the assumption that both sets are D-finite.


HINT: Note that a set $S$ is D-finite if and only if there is no injection from $\omega$ into $S$. If there is an injective $f:\omega\to A\cup B$, then ...


Hints only:

The first property may be shown directly.

The second however... Try showing what happens when the union of two sets is not D-finite.

Hope it helps.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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