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

Question

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

Answer 1

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.

---