0
$\begingroup$

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"

  • 0
    @mehdi: Let $f$ be a *particular* injection from the set $X$ to $\mathbb{N}$. If $f$ is not a bijection, you **cannot** conclude that $X$ is not countably infinite. In fact, if $X$ is infinite, then it is countably infinite. The proof is not hard, and we can use $f$ to produce an explicit bijection from $X$ to \mathbb{N}$.2012-06-28

1 Answers 1

2

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.

  • 0
    @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}$2012-06-27