3
$\begingroup$

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

$\endgroup$
2
  • 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, 2013 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$
    – Hosein Rahnama
    Nov 8, 2017 at 8:42

1 Answer 1

Reset to default
5
$\begingroup$

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.

$\endgroup$
2
  • $\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, 2013 at 4:20
  • $\begingroup$ You're welcome! $\endgroup$
    – amWhy
    Apr 9, 2013 at 4:25

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .