Set Theory

[NSX]

Radical Edward said in post #3 :

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 . 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