Primes vs. Integers: Are There More?

[nate808]

I was having this discussion in my math class today, and my teacher said that it was not something that he couldn't explain in a manner that we would understand. So the question is, are there more positive integers than primes, or no?

 

[matt grime]

What do you think 'more' means?

The primes are a natural subset of the integers, so you might feel justified in claiming there were more of them, but this is a hand wavy non-mathematical idea about what more means. After all, we can say that if we have 3 apples and 4 oranges that we have more oranges than apples, so we need to be able to compare things that are not of the same type, thus using simple notions of subsets won't come up with an acceptable mathematical version of more. Moreness or lessness should somehow be a so-called invariant of the set. That is the size of a set of 3 apples is the same as the size of a set of 3 oranges, ie 3.

So, what should a mathematician try and do about size? It took a hell of a long time, and not a little argument for the definition we use today to become the accepted notion of size.

Two finite sets are said to be the same size if one is in bijection with the the other. this means that we can pair up every element in one set with an element in the other and have none left over. Thus we can say a set of three apples has the same size as a set of 3 oranges because we can essentially count like we did in kindergarten (i'm writing this whilst in the states, and it feels natural to use that term) by sort of doing a one potato two potato thing.

when we pass to infinite sets of things, then this definition produces some strange (at least superficially) results. in particular the set of positive integers has the same size as the set of primes since there are an infinite number of primes.

ah, here i am assuming that the problem would be in discussing cardinality, but conceivably you also would need to be shown that the set of primes is infinite too. let's assume it's the cardinality thing and you understand that there are infinitely many primes; it's an easy result with many very pretty proofs.

in particular any infinite subset of the natural numbers (positive integers) has the same size as the natural numbers. why? well, we can label the subset as follows

x(1)<x(2)<x(3)<...

by just writing them out in order and then the correspondence is that we identify n in the positive integers with x(n).

so there are as many positive integers as primes, even positive integers, odd positive integers, and indeed integers, and even rational numbers, algebraic integers, algebraic numbers, polynomials with integer coefficients etc.

there is however no way of writing down a paring up of the natural numbers and the real numbers.

 

[Tide]

Matt,

I think you can do a one to one pairing between the natural numbers and primes by using Euclid's proof that there is no largest prime. E.g., starting with the first prime, $p_1 = 2$, Euclid tells us there is a next finite prime, $p_1 < p_2 <= p_1 + 1$ since the right side is not divisible by the first prime. Given those two, Euclid tells us once again there is a next finite prime $p_2 < p_3 <= p_1 \times p_2 + 1$ since the right side is not divisbile by either of the first two primes and so on.

We may not be able to explicitly list the values of all those primes but we do know they exist and we have a one to one correspondence.

 

[shmoe]

I think you can do a one to one pairing between the natural numbers and primes by using Euclid's proof that there is no largest prime. E.g., starting with the first prime, $p_1 = 2$, Euclid tells us there is a next finite prime, $p_1 < p_2 <= p_1 + 1$ since the right side is not divisible by the first prime. Given those two, Euclid tells us once again there is a next finite prime $p_2 < p_3 <= p_1 \times p_2 + 1$ since the right side is not divisbile by either of the first two primes and so on.

Why do anything more complicated than just invoking the natural order the primes have from being a subset of the naturals and knowing there are infinitely many of them?



matt has handled the cadinality ideas, so I just want to mention the idea of asymptotic density. This is a different measurement of 'how many' than cardinality as it takes into account *where* the primes are sitting in the naturals.

If we let pi(x) be the number of primes less than or equal to x, asymptotic density considers the behavior of pi(x)/x, this is just the ratio of primes in the set {1,2,...,x}. The prime number theorem tells us that pi(x)~x/log(x), so pi(x)/x~1/log(x), here ~ means asymptotic, you can think of it as 'relatively close when x is large' for now if you haven't seen this before. As x->infinity we then have pi(x)/x->0. So in this sense there are less primes than naturals, more precisely the primes 'thin out' as you consider larger and larger values. Compare with asymptotic densities of other sets, like the perfect squares, or the even integers, etc.

 

[Tide]

shmoe,

Why do anything more complicated than just invoking the natural order the primes have from being a subset of the naturals and knowing there are infinitely many of them?

Because it's a more complete explanation (simultaneously demonstrating an infinity of primes and ordering), it's very easy to understand, it's not complicated and doesn't assume a great deal of mathematical sophistication on the part of either the student or the instructor.

 

[HallsofIvy]

Matt,

I think you can do a one to one pairing between the natural numbers and primes by using Euclid's proof that there is no largest prime. E.g., starting with the first prime, $p_1 = 2$, Euclid tells us there is a next finite prime, $p_1 < p_2 <= p_1 + 1$ since the right side is not divisible by the first prime. Given those two, Euclid tells us once again there is a next finite prime $p_2 < p_3 <= p_1 \times p_2 + 1$ since the right side is not divisbile by either of the first two primes and so on.

We may not be able to explicitly list the values of all those primes but we do know they exist and we have a one to one correspondence.

This is "just invoking the natural order the primes have from being a subset of the naturals and knowing there are infinitely many of them"!

 

[shmoe]

...simultaneously demonstrating an infinity of primes...

I didn't consider this as one of the goals as I figured the OP almost surely knew this, fair enough

This is "just invoking the natural order the primes have from being a subset of the naturals and knowing there are infinitely many of them"!

If it was, there would be no need to use ideas of Euclid to prove there is a next prime, that would already be known. My point was Euclid adds nothing here to actually give you the ordering, beyond showing there are infinitely many primes (which is a good enough reason to use it).

 

[matt grime]

As I said in my post I was assuming that the question was not about the fact that there are infinitely many primes, since that is relatively easy to explain, and I can't believe a teacher would label that as too difficult to explain.