I have 2 sets of statements that I wish to prove and I believe they are very closely related. I can prove one of them and the other I'm not so sure!

1: Every infinite set has a denumerable subset

2: Every infinite set is a subset of some denumerable set

As you can see these two statements are closely related. I believe I can prove the first statement as follows:

Proof #1: $S$ is an infinite set. Choose any $S_1$ in $S$. Since $S$ is infinite and {$s_1$} is finite, $S$ does not equal {$s_1$} and so $S$ $-$ {$s_1$} does not equal the empty set. Next, choose $s_2$ and with similar reasoning we have $S$ does not equal {$s_1,s_2$} and $S$ $-$ {$s_1,s_2$} is not the empty set. If we continue like this, we can create a set, say $A$ where $A$ $=$ {$s_1,s_2,s_3...$} with no two elements of $A$ being equal.

That makes sense for the proof of statement #1 hopefully!

For statement #2, I am not so sure. How can I show that every infinite set is a subset of some denumerable set? Is the proof similar to above?

Help would be appreciated! Thank you :)

  • 4
    $\begingroup$ Your second statement is clearly false. For instance, $\mathbb{R}$ is not a subset of any denumerable set. Do you mean "Every finite set is a subset of some denumerable set"? $\endgroup$ – user17762 Apr 9 '13 at 4:09
  • $\begingroup$ There is a theorem which says If $S$ is countable then every subset of $S$ is countable. So, if there exist a subset of $S$ Which is not countable then $S$ is not countable. This means $S$ is not finite nor countabley infinite (denumerable). For sure $S$ is infinite. So your second statement is false. $\endgroup$ – H. R. Nov 8 '17 at 8:42

Your proof for the first statement is on the right track: you are on your way to showing that any denumerable set $A$, finite or not, is a subset of an infinite set $S$, by constructing a set $A$ containing only but not necessarily all of the elements of $S$.

  • For a denumerable set $S$, it may be that $A$ is
    • a proper finite subset of a denumerable set $S$,
    • a denumerable subset of a denumerable set $S$ (think of denumerable $\mathbb N \subset \mathbb Z \subset \mathbb Q$, all denumerable sets.
    • is equal to $S$, in which case it would be a nonproper subset $S$.
  • If $S$ is infinite but not denumerable (i.e. if S is uncountable), then any denumerable set A, finite or otherwise, which contains only elements of $S$, will be a proper subset of $S$. Since we are investigating only the existence of a denumerable subset $A$ of an infinite set $S$, if $S$ is uncountable, then $A$ would necessarily be a proper subset whose elements do not contain all elements of $S$.

For the second statement - there's no "proof" for it because it is not true for all infinite sets.

E.g., consider $\mathbb R$: it is certainly an infinite set, but it is uncountable, and hence not denumerable, so it cannot be the subset of any denumerable set. If it were a subset of a denumerable set $S$, then as a subset of $S$, it would contain only, and at most all, elements of $S$ . Which means it would contain at most a countable number of elements, which contradicts the fact that $\mathbb R$ is uncountable.

  • $\begingroup$ Ah I see. So I would have to cover the fact that $S$ might be denumerable OR uncountable. Thank you for your answer and time! $\endgroup$ – nicefella Apr 9 '13 at 4:20
  • $\begingroup$ You're welcome! $\endgroup$ – Namaste Apr 9 '13 at 4:25

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.