set of subsets of all primes

coolamit · P versus NP Offline Joined: 22 Aug 2005 Posts: 45

Let $\mathbb{P}$ be the set of primes and $\mathbb{N}$ be the set of natural numbers
then $|\mathbb{P}|=|\mathbb{N}|$ where the symbol $|\mathbb{A}|$ denotes the cardinality of $\mathbb{A}$

note that $|\mathbb{N}| = \aleph_0$
let $\mathbb{S}=2^\mathbb{P}$ (The power set of $\mathbb{P}$ or the set of all subsets of $\mathbb{P}$ ). Thus we know that $|\mathbb{S}|=|\mathbb{R}|=\aleph_1$

However, define mapping $u: \mathbb{S} \mapsto \mathbb{N}$ such that each element of $\mathbb{S}$ maps to to the product of all its elements.
eg. if $\mathbb{A} = \{2, 7, 11\} \in \mathbb{S}$ , then $u(\mathbb{A}) = (2.7.11) = 154$

Note that this mapping is injective.
However note that $\mathbb{S}$ is a proper subset of $\mathbb{N}$ since only the numbers which are not product of prime powers are in $\mathbb{S}$ .
Thus $|\mathbb{S}| < |\mathbb{N}|$ and no bijection exists from $\mathbb{N} \mapsto \mathbb{S}$ (we cannot map to numbers like $2.2.3=12$ using the mapping $u$ )

Isn't this a contradiction?

[Note: I edited this post to make it latex compatible]

MysticTerminator

http://www.artofproblemsolving.com/Forum/viewtopic.php?t=49289

darij was right, y'know; no need to look for second opinions

**Posted:** Mon Aug 22, 2005 6:35 am

_________________
I am THE BOB

rgep · Poincare Conjecture Offline Joined: 03 Jan 2005 Posts: 169

The mapping $u$ isn'tdefined on all of $S$ because you can't take the product of an infinite set of primes. Your argument shows that the set of finite subsets of $P$ is countable. Incidentally, $\aleph_1$ is the next largest cardinal after $\aleph_0$ , not necessarily $2^{\aleph_0}$ --- that's a form of the Continuum Hypothesis.

**Posted:** Mon Aug 22, 2005 6:51 am

dblues

I read the link...
Just have a question, hopefully it doesn't sound too stupid...
Is it true that if we define $\mid \mathbb{R} \mid = 2^{\aleph_0}$ as having cardinality $\aleph_k$ for any $k \in \mathbb{N}$ , $k$ not necessarily $1$ , it is still consistent with the Zermelo-Fränkel axiomatic system and of the axiom of choice? What are the implications if $k>1$ , or does it really matter?

**Posted:** Mon Aug 22, 2005 8:50 am

coolamit · P versus NP Offline Joined: 22 Aug 2005 Posts: 45

Even I was surprised when I first found out.

$\aleph_1 = \aleph_i$ for all integers $i > 1$ .

The first cardinal greater than $\aleph_1$ is $\aleph_\omega$ where $\omega = \aleph_0$

**Posted:** Tue Aug 23, 2005 7:29 am

_________________
continuum hypothesis is false!