# Proving every infinite set is a subset of some denumerable set and vice versa

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 :)

• 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"?
– user17762
Apr 9, 2013 at 4:09
• 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. Nov 8, 2017 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.

• 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! Apr 9, 2013 at 4:20
• You're welcome! Apr 9, 2013 at 4:25