1
$\begingroup$

Let A be a countable set. How to prove that the set

$\mathcal A = \{X \subseteq A : |X| = n $ for some $n \in \omega \}$

of all finite subsets of A is countable?. I checked similar questions subset but they are not discussing about finite subsets. It seems the question is unclear because the finite subsets can be countable.

$\endgroup$
  • 1
    $\begingroup$ (This has been answered on this site probably a dozen more times already) $\endgroup$ – MJD May 8 '14 at 12:10
1
$\begingroup$

If $A$ is finite, then the power set of $A$ is the set of finite subsets of $A$ and is also finite. So we can take $A$ to be countably infinite.

In this case, there exists some bijection of $A$ with the natural numbers $\mathbb{N}$. So, without loss of generality, we can think of $A$ as the natural numbers $\mathbb{N}$.

Let $S$ be the set of all finite subsets of $\mathbb{N}$. We define a map $\phi$ from $S$ to $\mathbb{N}$ as follows: Given a finite subset $X$ of $\mathbb{N}$, say $\{x_{0}, \ldots, x_{n}\}$, we place the elements in increasing order and then defin $$\phi(X) = x_{n}x_{n-1}\cdots x_{0}$$ where the term on the right refers to the decimal expansion of $\phi(X)$. Then, $\phi$ is injective, because if $X$ and $X'$ are finite subsets of $\mathbb{N}$ with different entires then $\phi(X)$ will not be $\phi(X').$

Hence, we have an injection of $X$ into a countably infinite set and hence $X$ is countable. Additionally, $X$ is obviously infinite (because every singleton is in $X$.)

$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.