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
    So you have to prove that $f$ is injective and that $f$ is surjective. What are you having trouble with?2012-06-27
  • 0
    edited question2012-06-27
  • 1
    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.)2012-06-27
  • 0
    not need to be a set of consequent primes2012-06-27
  • 0
    $A$ should be a multiset, not a set, of primes.2012-06-27
  • 0
    B contains all possible sets which have finite cardinality and only consists of unique primes (set elements must be unique as known) i.e. B= {{2,7} {13,31..,101} ...}2012-06-27
  • 0
    Then is it correct to say that since function f is not bijective, set B is not countably infinite.2012-06-27
  • 0
    In the book to show that set B has cardinality aleph naught, the author proves injection but doesnot touch surjection and says that we can write all possible sets A as alist so it has cardinality alep naught. But this contradicts to his proof2012-06-27
  • 0
    What book? ${}{}$2012-06-27
  • 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