# cardinality of possible prime decompositions, countably infinite bijection

Let $A = \{ p_{i},p_{i+1},\ldots,p_{n}\}$ be any finite set of prime numbers, where $i,n \in \mathbb{N}$. And $p_{i}\in A$, is the $i$th prime number i.e. $p_{2} = 3$.

Let all possible finite sets A, that can be formed, be element of set B.

The question is, prove or disprove that there exist a bijective function $f:B\rightarrow\mathbb{N}$ such that $f(A) =p_{i}\times p_{i+1}\times\cdots\times p_{n}$

for example $f(A) = 4$ does not satisfy, because it should be $A=\{p_2,p_2\}$ which contains same element twice, and this means that cardinality of set $B$ is not $\aleph_0$ (no bijection with $\mathbb{N}$). But in a book, author uses this argument to prove that "set of all finite subsets of natural numbers, is countably infinite"

-
So you have to prove that $f$ is injective and that $f$ is surjective. What are you having trouble with? –  Qiaochu Yuan Jun 27 '12 at 21:08
edited question –  mehdi Jun 27 '12 at 21:11
Two questions: (1) Is $A$ supposed to be a finite set of consecutive primes, e.g., $\{ 293, 307, 311, 313, 317, 331 \}$, or can it be any finite set of primes? (2) What is $B$ supposed to be? (The wording of the second paragraph is confusing me.) –  Arthur Fischer Jun 27 '12 at 21:12
not need to be a set of consequent primes –  mehdi Jun 27 '12 at 21:14
$A$ should be a multiset, not a set, of primes. –  Qiaochu Yuan Jun 27 '12 at 21:14

You have a few problems here. Your second sentence, "Let all possible finite sets A, that can be formed, are subsets of B." isn't a sentence, A has been defined as one particular set, and we haven't met B before. Also please be consistent with A vs. $A$. It would be better to say "Let $B$ be the set of all subsets of $A$. They are all finite because $A$ is. Now your function is from an element $b$ of $B$ to $\mathbb N$. This function cannot be a bijection with $\mathbb N$ as it is clearly finite, but it can be a bijection with its range as a subset of $\mathbb N$. Finally just because there are some elements of $\mathbb N$ that are not $f(b \in B)$ doesn't mean that $B$ is not infinite. An example would be to let $C= \mathbb N$ and $g(c \in C)=2c$. There are elements of $\mathbb N$ not in the range of $g$ (the odd numbers), but $C$ is still infinite.
@mehdi: So $A$ and A are different? A now is any finite set of naturals. If so, it would be better to use another letter for it. It looks like B and $B$ are the same. I think you want your function to go from $\{a_1, a_2, \ldots a_n\}$ to $p_{a_1}p_{a_2} \ldots p_{a_n}$ –  Ross Millikan Jun 27 '12 at 22:27