# Are all prime numbers finite?

If we answer false, then there must be an infinite prime number. But infinity is not a number and we have a contradiction. If we answer true, then there must be a greatest prime number. But Euclid proved otherwise and again we have a contradiction. So does the set of all prime numbers contain all finite elements with no greatest element? How is that possible?

-
Forget about the primes... How does the infinity of natural numbers look like to you? Will you present the same "arguments"? –  Metin Y. May 6 '13 at 0:23
An easier example to think about: The set of whole numbers consists of finite numbers and has no greatest element. If $N$ were the greatest element, then $N + 1$ is also a whole number but it is greater than $N$, a contradiction. –  Henry T. Horton May 6 '13 at 0:23
Your argument doesn't make any sense. You talk about having an "infinite prime number", but prime numbers are natural numbers by definition. –  nigelvr May 6 '13 at 0:25
Sets of natural numbers can be infinite, natural numbers cannot. –  Gastón Burrull May 6 '13 at 0:31
@vi.su. The opposite was proved 2,338 years ago. –  Jim Balter May 6 '13 at 6:44

Every natural number is a finite number. Every prime number (in the usual definition) is a natural number. Thus, every prime number is finite. This does not contradict the fact that there are infinitely many primes, just like the fact that every natural number is finite does not contradict the fact that there are infinitely many natural numbers. You can have infinitely many finite things, and there won't ever be a biggest exemplar.

To make things a bit more complicated (and a lot more interesting), there are extensions of the set of natural numbers that do contain infinite numbers, and even infinite prime numbers. For instance, in any hyperreal extension of the reals, there is a system of hypernatural numbers. Some of these hypernatural numbers are finite and some are infinite. The finite ones are just a copy of the usual set of natural numbers and the primes in it are the usual primes. For the infinite hypernatural numbers, there are also prime numbers. For instance, the hypernatural represented by the sequence $(2,3,5,7,11,13,17,19,\cdots )$ is an infinite prime number.

-
If OP doesn't "get" the standard infinite sets and their finite members, mixing in infinite numbers isn't the brightest idea of an explanation... –  vonbrand May 6 '13 at 0:37
As I wrote in a now-deleted comment, one must resist the temptation of mentioning non-standard models. Those are delicate and confusing... –  Asaf Karagila May 6 '13 at 0:40
The first paragraph explains the situation clearly. The second one opens a door, and, perhaps, is appealing to some intuition OP has that while not standard is also not wrong. Especially that all the infinitude or primes together neatly come together to produce a single infinite prime number, quite like OP seems to think is the case without hypernaturals. –  Ittay Weiss May 6 '13 at 0:44
@cyclochaotic yes, there are sequences of (distinct, if you prefer) integers that approach infinity. On the other hand, any single fixed element is finite, and does not approach anything. –  ronno May 6 '13 at 4:11
@cyclochaotic You seem to think of "approaching infinity" as getting "close to" infinity. This is not really the right way to think about it; since infinity is not a number, it doesn't make sense to think of particular numbers as being "close to" infinity. In other words, infinity isn't some sort of "ceiling" on the integers. Instead, it may be useful to think of "approaches infinity" as meaning "gets arbitrarily far away from 0." –  Kyle Strand May 6 '13 at 4:14

A prime number is an element of the set of all prime numbers, and as an element of that set, a prime number has no cardinality.

The set of all prime numbers is infinite (in cardinality): there are (adverb) infinitely many primes. That's not to say there is a prime that is infinite. But you are correct that "infinity is not a number" here. The set being "infinite" means that no matter how large a prime number you name may be, there is yet a larger prime than that...and after that, yet a greater prime, and so on. There is no end point at which you arrive at the largest prime number.

The set of all prime numbers less than or equal to some positive integer $n$ is finite. But there are then infinitely many more primes greater than $n$, whatever particular $n$ you choose.

-
To add to the confusion, one can manipulate an object called 'infinity' in many ways similar to the manipulations that govern natural numbers. But one does not refer to infinity in common parlance as a number (presumably a natural number). –  Mitch May 6 '13 at 3:07
We do, though. 3 is a finite number. $\omega_0 + 3$ is an infinite ordinal number. The cardinality of $\mathbb{R}$ is an infinite cardinal number. And we say "a finite number of foos" very often, which is "speaking of a number being finite". –  Kundor May 6 '13 at 17:14

Are all prime numbers finite?

Yes.

If we answer false, then there must be an infinite prime number.

That follows.

But infinity is not a number and we have a contradiction.

Whether or not infinity is a number, there are infinite (or "transfinite") numbers. And even if there weren't, this still wouldn't be a contradiction, any more than "Not all horses are ugly" is a contradiction just because beauty is not an animal. This isn't about logic or math, it's about misuse of the English language.

If we answer true, then there must be a greatest prime number.

No, that does not follow at all. All primes are finite, but there is no greatest one, just as there is no greatest integer or even integer, etc. That there are infinitely many of something doesn't require that any of them be infinite, or infinity.

But Euclid proved otherwise and again we have a contradiction.

He did, but there is no contradiction.

So does the set of all prime numbers contain all finite elements with no greatest element?

Yes.

How is that possible?

There's no reason for it to be impossible, and Euclid proved it not only possible but true. You appear to have assumed it impossible in order to reach your conclusion of a contradiction, which is a circular argument.

-
@Jaydee: Because there isn't a last one; there's always more. Suppose there were just a finite number of natural numbers, like 5,024. Then we couldn't have a 5,025th number. But that's absurd. –  Kundor May 6 '13 at 17:19
This is about logic and math. But most of your points are valid. Assuming a greatest element must exist is a misconception. In addition, I maintain that I communicated my perplexity very effectively via the English language. –  cyclochaotic May 7 '13 at 1:48
@Jaydee. Think of it in terms of even numbers. There is a bag of natural numbers. I reach into the bag and grab a $2$ and put that into the set of even numbers. I reach into the bag again and grab a $4$, then a $6$, and so on. If I pull out a $2n$ and someone challenges me to find a greater even number, the natural numbers produces $2n+2$. The natural numbers has the property of being an unlimited source. We describe this by saying that the set of even numbers has "infinitely many" elements, yet every single element is finite! –  cyclochaotic May 7 '13 at 13:10
" If ALL members of the set are finite, then the set must be finite." -- There is no basis whatsoever for that assertion, any more for the claim that someone who tends fat cows must be fat. Imagine that there were, in fact, some infinite set ... say the set of positive integers. What do we know about its elements? Well, we know that they are all finite, because all positive integers are finite. So, we have an example of an infinite set all of whose members are finite, contrary to your claim. If such a set cannot exist, it must be for some other reason than the one you claim. –  Jim Balter May 7 '13 at 19:38
"the staircase can be infitly long without being infinitly high" -- The correct statement is that, given an infinitely long and infinitely high staircase, no individual step is infinitely high ... nor, to reach that step, will you have gone an infinite distance. But because no step is the last step, the staircase itself is infinite. –  Jim Balter May 9 '13 at 10:34

You can have an infinite number of objects, each with finite size, the sequence of which is not bounded, so yes all primes are finite... by definition of a prime number almost. It's meaningless to talk about a natural number being 'infinite' until you define that term.

-

The modern definition of an infinite set is one which can be expressed in a one to one relationship with a subset of it self: eg: 2 4 6 8 and 1 2 3 4. this video produced by bbc horizon explores infitity, why there are at least two sizes of infitity... yup and many more aspects of infinity and its very wachable too... http://www.youtube.com/watch?v=FiMigmLwwTM

The answer to your question is that you question is not a correctly stated mathematical problem in the english language. You are mixing up values within a set and the number of values within that set.

This response was written before the question was edited. Still recommend the video though.

-
That's inaccurate. The modern definition of an infinite set is a set which cannot be put in one-to-one correspondence with a bounded initial segment of the natural numbers. That is the canonical definition of finite. Dedekind infinite sets are those which can be injected into a proper subset. While the integers are certainly both, and assuming the axiom of choice every infinite set is Dedekind-infinite (and vice versa), when we say "infinite" we really just mean "not finite". Do note that we can characterize "finite" without appealing to the integers, Tarski has such a characterization. –  Asaf Karagila May 6 '13 at 15:36
Just to finish the above comment, Tarski's definition of finite is as follows, a set $X$ is finite if and only if whenever $\mathcal U\subseteq\mathcal P(X)$ is a non-empty family of subsets of $X$, then $\cal U$ has a $\subseteq$-maximal element. This definition doesn't refer to the integers at all, and does not require the axiom of choice to be true. Interestingly, however, if we replace "family of subsets" by "$\subseteq$-chain" then one needs to use the axiom of choice to prove the equivalence. –  Asaf Karagila May 6 '13 at 15:38

The answer depends on what you mean by number and in fact there are infinite prime numbers if and only if there are infinite numbers, by the tranfer principle. Namely, consider the first order statement that for every $n$, there is a prime $p$ greater than $n$. By transfer this is true for all $n$ including a particular infinite $n=H$. But any prime $p$ greater than $H$ would also be infinite.

-