I just need help trying to create a proof that shows that an infinite set has a countable subset. Is it as simple as taking arbitrary values of the finite set and listing them in their own subset?
[Math] Prove that every infinite set has a countable subset.
elementary-set-theory
Related Solutions
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.
I think some things can be written in a clearer manner. First, I would change
This implies that there is a sequence $\left\{x_{n}\right\}_{n\in\mathbb{N}}$ where $x_{n}\in A$.
For
This implies we can write $A=\{x_n:n\geqslant 1\}$
or
Let $\{x_n:n\geqslant 1\}$ be an enumeration of $A$.
Then, I would say
If $S$ is a subset of the natural numbers, let $\min S$ denote least element of $S$. Define $S_1=\{k:x_k\in E\}$. $S_2=S_1\setminus \{\min S_1\}$ and in general $$S_{n+1}=S_{n}\setminus\{\min S_1,\ldots,\min S_{n}\}$$ Then define $n_k=\mathscr \min S_k$
I guess the idea is clear: consider the set of subscripts such that $x_k\in E$. By the well ordering of the natural numbers, we can extract a sequence $n_k$ such that $$n_1<n_2<\cdots\\E=\{x_{n_k}:k\geqslant 1\}$$
by considering the first subscript with $x_k\in E$ removing this one from the list and looking at the new first subscript (our second in the list) and so on. Some details should be addressed
$(1)$ The set $S_{n}$ is never empty. Reason: Since $E\subseteq A$; $S_1$ is not empty. Moreover, $E$ is by assumption infinite, thus removing one element every time cannot exhaust it.
$(2)$ The construction exhausts the elements of $E$ -- that is, it is a surjection. Reason: Pick $m$ such that $x_m\in E$. We need to find $k$ such that $n_k=m$. Consider the finite set $\{x_1,\dots,x_m\}$. Keeping the order, remove all elements such that $x_i\notin E$. We're left with a finite set, and it must be the case $\{x_{n_1},\dots,x_{n_k}\}$ for some $k$, and $n_k=m$, by definition of the $n_k$.
$(3)$ The construction is an injection. Reason: By construction, $n_k\neq n_j$ if $j\neq k$ for if $j>k$ then $n_k\notin S_{j}$.
Conclusion We obtain an bijection of $E$ with an infinite subset $F$ of $\Bbb N$. Thus $E\simeq F\simeq \Bbb N$, that is $E\simeq \Bbb N$.
Best Answer
Definition: The statement that a set $S$ is infinite means that if $N$ is a natural number then $S$ contains $N$ distinct elements.
[Note: If an infinite set is defined in this way, then it automatically follows that an infinite set minus a finite set is infinite.]
Suppose $S$ is infinite.
Since $1$ is a natural number, $S$ contains an element $x_1$.
Since $2$ is a natural number, $S$ contains an element $x_2$ distinct from $x_1$.
So there is a two-element subset $U_2=\{x_1,x_2\}$ of distinct elements of $S$.
For each $N\in\mathbb{N}$, $S$ contains an element distinct from each element in $U_N=\{x_1,x_2,\cdots,x_n\}$, so define $U_{N+1}=U_N\cup\{x_{N+1}\}$ where $x_{N+1}$ is an element of $S$ distinct from each element of $U_N$.
Let $$U=\bigcup_{N\in\mathbb{N}}U_N$$
Then $U$ is a countable subset of $S$.
ADDENDUM There is an issue which I glossed over when making this argument.
For each $N$ we know that there is a subset $V$ of $S$ containing $N+1$ elements of $S$. So $V$ contains an element, call it $x_{N+1}$, which is distinct from each element of $U_N=\left\{x_n,x_2,\cdots,x_N\right\}$. Let $U_{N+1}=\left\{x_n,x_2,\cdots,x_N,x_{N+1}\right\}$.