Math Is Fun Forum

{7/3}

Member

Registered: 2013-02-11

Posts: 210

cardinality of primes

if P is the set of primes then is |P| = |N| true?

---

There are 10 kinds of people in the world,people who understand binary and people who don't.

SteveB

Member

Registered: 2013-03-07

Posts: 595

Re: cardinality of primes

The cardinality of the number of primes in total is countably infinite. That is they can have a bijection with the
natural numbers. Consider listing them with the natural number as an index reference and the prime as the
item. The cardinality result is then obvious.

However I am not exactly sure at this time as to whether that was the question. The icon has obscured it to some extent,
also I think more words would have been a good idea. Did you mean some property of subsets of primes?

I think I might have just have thought about what is not obvious about it - I presume you haven't done the theorem
concerning cardinality of rationals being the same as the cardinality of integers and natural numbers. In which case
yes intuitively the primes may seem like a smaller set than the natural numbers, but it is known to be not finite,
so how could we have a smaller set? (I don't think we can)

The strange aspect of the Cantor/Schroeder/Bernstein results is/are that the real numbers have higher cardinality,
that is a strange result after the natural/integer/rational result. There are more real numbers than integers to the
extent that you can never list a complete set of them, or something like that - rephrase that more precisely perhaps.
I cannot remember how you prove the result with the reals, but the rational proof draws a diagram involving a sort
of rotation around the 2 dimensional number plane in which the p/q rationals in simplest form are "listed" in a
systematic manner. The proof involving reals being higher in cardinaility involves a method which I have a vague memory
of involving using the fact that there are an infinite number of numbers available after each point in an infinitely accurate
decimal representation. I think it uses a contradiction argument in a generalized listing to prove that some items must
have been missed out and that therefore no such listing can be made.

Compared to that the prime number set cardinality is quite simple which is why I wondered whether there was a result
involving finite cardinality of subsets of the primes constrained somehow, but there is not enough information in the
question to ask such a thing.

Last edited by SteveB (2013-07-30 06:29:55)

Bob

Administrator

Registered: 2010-06-20

Posts: 10,621

Re: cardinality of primes

I have corrected the smiley bug in the first post by adding spaces.

Bob

---

Children are not defined by school ...........The Fonz
You cannot teach a man anything;  you can only help him find it within himself..........Galileo Galilei
Sometimes I deliberately make mistakes, just to test you!  …………….Bob

SteveB

Member

Registered: 2013-03-07

Posts: 595

Re: cardinality of primes

Thanks Bob.

I have just read an interesting wikipedia article on a related matter concerning cardinality of the reals and other sets:

http://en.wikipedia.org/wiki/Cardinalit … _continuum

It says that Georg Cantor proved the matter in 1874. Interestingly the power set always has higher infinite cardinality
than the original infinite set. Also the power set of the integer set has the same cardinality of the reals I notice.

I did wonder whether you meant the power set of the prime numbers. That would be the same as the power set of
the naturals. That I suppose would be the same as the reals. However Bob's post suggests that it was just the set
of primes in the {7/3} question.

I have never seen the power set property proven. Disappointingly I don't find the wikipedia explanation very clear
at the current time. I suppose if I worked on it a bit it might make more sense. I had previously assumed that the
set of all subsets of a set had equal cardinality to the original set in the infinite case, but this is not true.
I wouldn't like to prove the result for the cardinality of sets of subsets of an infinite set, but yes it sounds like the
wikipedia article is correct. I suppose textbooks still have a use then - because online sources do not always explain
these things very clearly even if the facts are correct.

Last edited by SteveB (2013-07-30 06:57:53)

{7/3}

Member

Registered: 2013-02-11

Posts: 210

Re: cardinality of primes

I know about those theorems, I also know  that infinite sets can have same cardinality as their proper subsets,I wanted to know if |P| = |N| then what is the bijection between them?

---

There are 10 kinds of people in the world,people who understand binary and people who don't.

SteveB

Member

Registered: 2013-03-07

Posts: 595

Re: cardinality of primes

I'm not sure whether this is the official answer as such, but remember that the bijection does not have to be unique
it merely has to exist so:

1 - 2
2 - 3
3 - 5
4 - 7
5 - 11
6 - 13
7 - 17
8 - 19
9 - 23
10 - 29

(For each addition of one of the left hand number, the right hand number is the next prime number in numeric order)

Keep on going with the natural numbers from 1 to infinity. Give each of them the next prime in sequence.
If you were to run out of prime numbers then this would contradict the proven theory that there must be
an infinite number of them otherwise you could multiply the finite set of them and add one to generate another.
You cannot run out of the natural numbers either because if you did then just take the highest one and add one
and you have another. Also you must always be able to continue indexing them like this without missing any
out of the list. For any given prime we will be able to give it an index if you had unlimited computing power and every
index has a prime number associated with it according to the numeric ordering of primes.
The fact that the computer would not be powerful enough to do this is irrelevant - in theory it still has
a unique index for each and every prime number, and a unique prime number for every index.
Hence the cardinality is the same as natural numbers, integers and rational numbers.

Last edited by SteveB (2013-07-30 18:27:54)

{7/3}

Member

Registered: 2013-02-11

Posts: 210

Re: cardinality of primes

thanks

---

There are 10 kinds of people in the world,people who understand binary and people who don't.