Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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"

share|cite|improve this question
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.) – arjafi 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.

share|cite|improve this answer
"Let all possible finite sets A, that can be formed, be a an element of B." I am very sorry – mehdi Jun 27 '12 at 21:49
@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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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