0
$\begingroup$

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 ?

$\endgroup$
0
$\begingroup$

Frank has already covered the answer quite sufficiently: I'll address your second paragraph.

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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ 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 \} $ ? $\endgroup$ – user203867 Apr 12 '15 at 23:44
  • $\begingroup$ 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$. $\endgroup$ – user88319 Apr 13 '15 at 18:04
  • $\begingroup$ 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. $\endgroup$ – user88319 Apr 13 '15 at 18:09
2
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy