3
$\begingroup$

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.

  • 0
    In addition to the suggestion by @Henning, I would also add the definition given in Brian's answer to the equivalence.2012-12-15

3 Answers 3

3

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.

2

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 ...

0

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.