Discussion about math, puzzles, games and fun. Useful symbols: ÷ × ½ √ ∞ ≠ ≤ ≥ ≈ ⇒ ± ∈ Δ θ ∴ ∑ ∫ π -¹ ² ³ °

You are not logged in.

- Topics: Active | Unanswered

Pages: **1**

**{7/3}****Member**- Registered: 2013-02-11
- Posts: 210

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.

Offline

**SteveB****Member**- Registered: 2013-03-07
- Posts: 595

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)*

Offline

**bob bundy****Administrator**- Registered: 2010-06-20
- Posts: 8,065

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

Offline

**SteveB****Member**- Registered: 2013-03-07
- Posts: 595

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)*

Offline

**{7/3}****Member**- Registered: 2013-02-11
- Posts: 210

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.

Offline

**SteveB****Member**- Registered: 2013-03-07
- Posts: 595

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)*

Offline

**{7/3}****Member**- Registered: 2013-02-11
- Posts: 210

thanks

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

Offline

Pages: **1**