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

1

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
    "Let all possible finite sets A, that can be formed, be a an element of B." I am very sorry2012-06-27
  • 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