Is the Concept of Prime Numbers Finite or Infinite?

[ZeAsYn51]

Okay, maybe I didn't use the best wording, but my point is that there is no proof that primes are finite in number and I do not believe there can be such a proof.

 

[shmoe]

Okay, maybe I didn't use the best wording, but my point is that there is no proof that primes are finite in number and I do not believe there can be such a proof.

Of course there can't be a proof that the primes are finite because they are not. See one of Atheist's post for a proof. (different proofs are available on request)

 

[ZeAsYn51]

Okay, Shmoe. I did go back and look at Atheists posts, but I didn't really find anything useful. I was, however, looking at what you just described to me (post #30) earlier today, but I'm not quite sure I understand it. Could you please take a few mins to explain it to me.

 

[Alkatran]

multiply all known primes together and add 1. This number cannot have any factors of the primes, or factors which have the primes as factors.

That means either the number is a higher prime or it has a factor which is of a higher prime.

 

[shmoe]

Okay, Shmoe. I did go back and look at Atheists posts, but I didn't really find anything useful. I was, however, looking at what you just described to me (post #30) earlier today, but I'm not quite sure I understand it. Could you please take a few mins to explain it to me.

Sure. pi(x)=number of primes less than or equal to x. So pi(3)=2, pi(3.5)=2, pi(10)=4, and so on. If you were to randomly select an integer less than x with uniform probability (equal chance of each) the probability you get a prime would be close to pi(x)/x. The prime number theorem tells us pi(x) is asymptotic to x/log(x) as x goes to infinity, so if x is very large the probability that a randomly selected integer between 1 and x is prime will be very close to 1/log(x). This goes to zero as x->infinity, so it's a fair thing to say that there are signifigantly less primes than there are natural numbers. The get sparse as you go higher, signifigantly sparse.

Compare with multiples of 2. If you randomly select an integer less than x the probability it will be a multiple of 2 is pretty close to 1/2, even for very large x. There is no sparseness with this sequence.

 

[Alkatran]

Sure. pi(x)=number of primes less than or equal to x. So pi(3)=2, pi(3.5)=2, pi(10)=4, and so on. If you were to randomly select an integer less than x with uniform probability (equal chance of each) the probability you get a prime would be close to pi(x)/x. The prime number theorem tells us pi(x) is asymptotic to x/log(x) as x goes to infinity, so if x is very large the probability that a randomly selected integer between 1 and x is prime will be very close to 1/log(x). This goes to zero as x->infinity, so it's a fair thing to say that there are signifigantly less primes than there are natural numbers. The get sparse as you go higher, signifigantly sparse.

Compare with multiples of 2. If you randomly select an integer less than x the probability it will be a multiple of 2 is pretty close to 1/2, even for very large x. There is no sparseness with this sequence.

You're asking it the number of primes is a 'countable' infinity or not?

For example, the area under y^x is countable as x goes from 0 to infinity if y < 1.

 

[matt grime]

This isn't about countability (or size), it's about distribution. Euclid's proof shows that the cardinality of the set of primes is the same as the set of naturals, but that is neither here nor there.

I don't think you know what countable means, judging by the last sentence, though.

 

[shmoe]

You're asking it the number of primes is a 'countable' infinity or not?

For example, the area under y^x is countable as x goes from 0 to infinity if y < 1.

I don't understand what you mean. The area under that graph will be finite, what do you mean by 'countable'?

 

[Alkatran]

This isn't about countability (or size), it's about distribution. Euclid's proof shows that the cardinality of the set of primes is the same as the set of naturals, but that is neither here nor there.

I don't think you know what countable means, judging by the last sentence, though.

No, I don't understand it. Explain, please?

I was thinking something along the lines of number or primes until x divided by x, does this number approach anything?

 

[matt grime]

Shmoe told you what happened - pi(x) is asymptotically x/logx (prime number theorem), see about 3 posts back.

A set is countable if it is in bijection with a subset of the natural numbers. (note I adopt the convention that finite sets are countable, some people restrict countable to mean infinite and in bijection with N, which I'd call countably infinite).

The area you obtain in your integral is finite, in the sense that is some real number, but it isn't really saying something about it as a set.

If we were to consider the set of points bound by the graph and the x-axis then it is an uncountable set.

 

[mathwonk]

actually there is another step missing, and one that becomes important in trying to generalize euclid's result to other rings.

i.e. by definition a prime integer is a non zero integer which is not invertible, which boils down in the integers to not being equal to 1 or -1. So one must check the rather trivial fact that your number X+1 is not invertible,l i.e. that it is not equal to 1 or -1.


There are other interesting rings, such as a power series ring k[[X]] over a field, in which, whenever you add 1 to a product of series with no constant term, you do get an invertible element. in these rings, there are not an infinite number of essentially distinct primes. Indeed the only essential prime is X. Howvere since there is an infinite number of invertible elements u, all elements of form uX are prime, where u is invertible, but these are not essentially different from X.

If the field is finite, then there only a finite actual number of primes, even not taking equivalence into account.


when this question came up in graduate algebra, as to how to prove there are infinitely many prime integers, I naively asserted "Euclid proved that", (falsely assuming the rpoof would generalize to power series rings). My professor's retort was "Yes, but Euclid was intelligent!"

However, here is the actual proof of Euclid, and he does not actually fill in the step my professor implied he did. I was hustled! (But I have never forgotten the point I was hustled into noticing.)

"Prime numbers are more than any assigned multitude of prime numbers. Let A, B, and C be the assigned prime numbers.

I say that there are more prime numbers than A, B, and C.
Take the least number DE measured by A, B, and C. Add the unit DF to DE.

Then EF is either prime or not.

First, let it be prime. Then the prime numbers A, B, C, and EF have been found which are more than A, B, and C.
java applet or image Next, let EF not be prime. Therefore it is measured by some prime number. Let it be measured by the prime number G. VII.31 I say that G is not the same with any of the numbers A, B, and C.

If possible, let it be so.

Now A, B, and C measure DE, therefore G also measures DE. But it also measures EF. Therefore G, being a number, measures the remainder, the unit DF, which is absurd.

Therefore G is not the same with anyone of the numbers A, B, and C. And by hypothesis it is prime. Therefore the prime numbers A, B, C, and G have been found which are more than the assigned multitude of A, B, and C.
Therefore, prime numbers are more than any assigned multitude of prime numbers."

(for the translation, google on euclid's elements.)