# Trying to show that set of all one-element subsets of a denumerable set is denumerable

Let $A$ be a denumerable and put $X = \{ B : B \subset A, \; \; |B| =1 \}$. Then $X$ is denumerable:

I know there is a bijection $f: A \to \mathbb{N}$. If I consider the functions $g: \mathbb{N} \to X$ given by $g(n) = \{ n \}$ then can we conclude that $g$ is bijective ?

There is no reason to believe that $g: n \mapsto \{n\}$ is even a proper function from $\mathbb{N}$ to $X$, much less a bijection. If we take $A=\{\text{Banana}\}$, then $X = \{\{\text{Banana}\}\}$ does not even intersect the range of $g$. On the other hand, if we take $A= \mathbb{Z}$ (the set of all integers), then $X$ is denumerable, but $g$ fails to surject onto $X$ (since, in particular, $\{-1\} \not\in \operatorname{Range}(g)$).
The definition of $g$ you want* is $g(n) = \{f(n)\}$. This follows from the fact that, for any $x \in X$, we can write $x=\{a\}$ for a unique $a \in A$, and we can write $a=f(n)$ for a unique $n\in\mathbb{N}$ because $f$ is a bijection.
*: It can actually be shown that all bijections $g: \mathbb{N} \to X$ can be written as $g(n) = \{f(n)\}$ for some bijection $f:\mathbb{N} \to A$: I'll leave the proof as an exercise.
• thanks alot for your time. Question: Can we extend this to sets of the form for all $k \in \mathbb{N}$ , $X = \{ B : B \subset A, \; \; |B| = k \}$ ? – user203867 Apr 12 '15 at 23:44
• I guess that depends on what you mean be 'extend.' We can't just use the same construction, since for $k\not=1$ it's not obvious how to match an element of $A$ to a set in $X$. I suppose a sort of generalization would be to first take a bijection $h:\mathbb{N} \to C$, where $C$ is the set of all elements of $\mathbb{N}^k$ with no repeats (you'd have to know $C$ is countable first, though). Then, you could define a map $f^*(n): C \to X$ which sends $(n_1, n_2, \cdots, n_k)$ to $\{f(n_1), f(n_2), \cdots, f(n_k)\}$. Thus, $h\circ f^*$ would be a bijection from $\mathbb{N}$ to $X$. – user88319 Apr 13 '15 at 18:04
• Personally, I would rather just notice that $f:\mathbb{N} \to A$ naturally defines an order on $A$, and define $S_a \subset X$ as set of elements of $X$ having $a$ as their largest element. Then, each $S_a$ is countable (in fact, finite), so $\bigcup_{a\in A} S_a$ is the countable union of countable sets, which must be countable. – user88319 Apr 13 '15 at 18:09
There is obviously a bijection between $A$ and $X$ defined by $a \mapsto \{a\}$. And there is a bijection from $A$ to $\mathbb{N}$. And their composition is again a bijection.