21
$\begingroup$

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?

$\endgroup$
  • 62
    $\begingroup$ Forget about the primes... How does the infinity of natural numbers look like to you? Will you present the same "arguments"? $\endgroup$ – Metin Y. May 6 '13 at 0:23
  • 12
    $\begingroup$ Your argument doesn't make any sense. You talk about having an "infinite prime number", but prime numbers are natural numbers by definition. $\endgroup$ – nigel May 6 '13 at 0:25
  • 32
    $\begingroup$ Sets of natural numbers can be infinite, natural numbers cannot. $\endgroup$ – Gaston Burrull May 6 '13 at 0:31
  • 18
    $\begingroup$ @vi.su. The opposite was proved 2,338 years ago. $\endgroup$ – Jim Balter May 6 '13 at 6:44
  • 13
    $\begingroup$ how on earth does this question have upvotes? $\endgroup$ – Jonathan May 6 '13 at 16:17
84
$\begingroup$

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.

$\endgroup$
  • 29
    $\begingroup$ 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... $\endgroup$ – vonbrand May 6 '13 at 0:37
  • 18
    $\begingroup$ As I wrote in a now-deleted comment, one must resist the temptation of mentioning non-standard models. Those are delicate and confusing... $\endgroup$ – Asaf Karagila May 6 '13 at 0:40
  • 23
    $\begingroup$ 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. $\endgroup$ – Ittay Weiss May 6 '13 at 0:44
  • 6
    $\begingroup$ @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. $\endgroup$ – ronno May 6 '13 at 4:11
  • 8
    $\begingroup$ @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." $\endgroup$ – Kyle Strand May 6 '13 at 4:14
56
$\begingroup$

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 countably infinite (in cardinality, equal to $|\mathbb N|$): 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.

It is true that 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.

$\endgroup$
  • 2
    $\begingroup$ 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). $\endgroup$ – Mitch May 6 '13 at 3:07
  • 2
    $\begingroup$ 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". $\endgroup$ – Kundor May 6 '13 at 17:14
  • $\begingroup$ Yeah, natural number in Peano Arithmetic might not have a cardinality, but natural number as finite ordinal number in ZFC has a cardinality. But I don't know whether this is really related to the question of the OP. I guess the OP has another confusion and thinks the set of prime numbers is bounded, which would be possible for sets of ordinals, for example {0,1,...,omega}, the set omega+1 is bounded. $\endgroup$ – j4n bur53 Jun 6 '18 at 21:27
30
$\begingroup$

Are all prime numbers finite?

Yes.

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

That follows ... but we didn't "answer false", so we don't have to worry about it.

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. In any case, we didn't "answer false", so we don't have to worry about this supposed contradiction.

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, or greatest.

Consider for instance the non-negative reals less than 1: [0, 1). There are of course infinitely many of them, but they are all finite (less than 1, in fact), and there is no largest one. (Proof: suppose there were a largest one, L. Then (L+1)/2, which is halfway between L and 1, would also be in the set but would be larger than L. That really is a contradiction.)

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.

$\endgroup$
  • 4
    $\begingroup$ @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. $\endgroup$ – Kundor May 6 '13 at 17:19
  • 2
    $\begingroup$ 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. $\endgroup$ – cyclochaotic May 7 '13 at 1:48
  • 1
    $\begingroup$ @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! $\endgroup$ – cyclochaotic May 7 '13 at 13:10
  • 1
    $\begingroup$ " 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. $\endgroup$ – Jim Balter May 7 '13 at 19:38
  • 5
    $\begingroup$ "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. $\endgroup$ – Jim Balter May 9 '13 at 10:34
3
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
  • 3
    $\begingroup$ 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. $\endgroup$ – Asaf Karagila May 6 '13 at 15:36
  • $\begingroup$ 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. $\endgroup$ – Asaf Karagila May 6 '13 at 15:38
0
$\begingroup$

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.

$\endgroup$
-2
$\begingroup$

If you allow ordinal numbers as numbers, then there is something like infinite prime numbers. But with these prime ordinals, we do not have anymore Goldbach's Conjecture. Side note in Axiomatic Set Theory, by Patrick Suppes;

you find prime ordinals itself in wiki. The definition reads:

A prime ordinal is an ordinal greater than 1 that cannot be written as a product of two smaller ordinals. Some of the first primes are 2, 3, 5, ... , ω, ω+1, ω^2+1, ω^3+1, ..., ω^ω, ω^ω+1, ω^(ω+1)+1, ...

So since ω is a prime ordinal, the set A={2,3,5,..,ω} would be a bounded set of prime ordinals. So a scenario as the OP asked for, is possible since this set contains all finite prime ordinals.

If the OP would have asked more precisely all finite prime ordinals and only all finite prime ordinals in the set A, then a bounded set A would not be possible.

$\endgroup$

protected by Community May 8 at 0:16

Thank you for your interest in this question. Because it has attracted low-quality or spam answers that had to be removed, posting an answer now requires 10 reputation on this site (the association bonus does not count).

Would you like to answer one of these unanswered questions instead?

Not the answer you're looking for? Browse other questions tagged or ask your own question.