Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
1  
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. –  Henning Makholm Dec 15 '12 at 23:03
    
In addition to the suggestion by @Henning, I would also add the definition given in Brian's answer to the equivalence. –  Asaf Karagila Dec 15 '12 at 23:10
add comment

3 Answers 3

up vote 3 down vote accepted

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.

share|improve this answer
add comment

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

share|improve this answer
add comment

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.

share|improve this answer
add comment

Your Answer

 
discard

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.