Set Theory

[NSX]

Radical Edward said in post #3 (http://www.scienceforums.net/forums/showthread.php?s=&postid=27140#post27140):
well in terms of set theory, there are the same number of odd numbers as there are naturals, since you can create a 1:1 correlation. however you can't do this with primes so far as I am aware :)

has my avatar been corrupted for everyone else too?

heh

I was reading about that last month or so, when I drifted off topic.

Here's the site i was reading: http://mathforum.org/isaac/problems/prime1.html

Most notably:
Theorem: There are infinitely many prime numbers.

As far as your question goes, I'm not really sure, but I suppose the theorem implies something :p. I hope that site helps.

As for the avatar? blike said it had something to do w/ the forum shift.
:/

[Radical Edward]

I have been avidly learning set theory for the past day and a half, and I was wondering if anyone knows if the set of prime numbers is smaller than the set of natural numbers. I would hypothesise that it is, and I have been trying to think of methods to prove it but I am perplexed... is there a method for this?

thanks

[YT2095]

sounds a bit like trying to find the ratio of primes to naturals. Like yourself, I`de go with primes being in a lesser quantity.
Man, You guys get some neat questions!
I base my reasoning upon this, and this only: all Prime numbers are ODD, natural numbers can be either (ODD/EVEN), so for a start you`re down to 50%.
I know of at least 1 number that is ODD but is NOT a prime. therefore I`de conclude that there are less primes than naturals. :)

[Radical Edward]

well in terms of set theory, there are the same number of odd numbers as there are naturals, since you can create a 1:1 correlation. however you can't do this with primes so far as I am aware :)

has my avatar been corrupted for everyone else too?

[YT2095]

pass? been so long since ya said anything and all that, but it still looks ok to me :)

[dave]

If you can prove that there's not a bijection between the two sets, then you can prove that they don't have the same cardinality.

At a guess, I don't think there's a bijection, but it seems like a little bit of a git to prove.

And your avatar is corrupted for me.

[wolfson]

Euclid proved there are infinitely many primes ... are you
familiar with his proof?

Then you can put the primes in 1-1 correspondence with the
natural numbers, with p(n) being the nth prime (so the function
maps 1 <-> 2, 2 <-> 3, 3 <-> 5, and so on.

Does that help?

[dave]

Well, the cardinality (a kindof posh way of saying 'size' but not that exact) of a set can be different even if the set is infinite. For example, the 'size' of the set of natural numbers is different from that of the rationals and reals.

[dave]

Also I'm not sure whether that bijection is actually a proper one, you'd have to give a definitive proof.

[matt grime]

Let us clear some things up.

Two sets have te same cardinality iff there is a bijection between them.

There is a bijection between N and the set of primes in N, and further there is a bijection between N and any infinite subset of N. There is also a bijection with Q.

Sets that biject with N are called countable,

The set of Reals is not countable, nor is the power set of N.

[MandrakeRoot]

I would reason as follows :

Since there are infinitely many prime numbers and since they are a subset of N, the set of prime numbers is clearly a countably infinite set and has thus the same cardinality as N.

Mandrake