0
$\begingroup$

I'm a bit confused about this.

I know that there is an infinite amount of prime numbers, a set having infinitely many elements does not necessarily make that set bounded. For example, the set $A$ of all real numbers between $1$ and $2$ has an infinite amount of elements, but is bounded clearly (because there exist numbers $C$ and $D$ such that $C<a<D$ for all $a\in A$.

Here is my attempt to explain that the set of all prime numbers is not bounded.

Let $N$ be the set of all prime numbers. We know that there are an infinite amount of prime numbers. Thus we know that there does not exist a number $R$ such that $n<R$ for all $n \in N$.

But do we know that?

According to Euclid's theorem of infinite primes, the proof just states that there is always at least 1 prime number in the set of all primes, and therefore there is an infinite amount of prime numbers. However, it explicitly states that what is found in this proof is another prime--one not in the given initial set. There is no size restriction on this new prime, it may even be smaller than some of those in the initial set.

So is the set of all prime numbers bounded? If so, how do I explain that.

Any help would be appreciated.

$\endgroup$
  • $\begingroup$ "According to Euclid's theorem of infinite primes, the proof just states that there is always at least 1 prime number in the set of all primes, and therefore there is an infinite amount of prime numbers. However, it explicitly states that what is found in this proof is another prime--one not in the given initial set. There is no size restriction on this new prime, it may even be smaller than some of those in the initial set." Not at all. the prime you find in Euclid's proof is bigger than the other primes you start with. $\endgroup$ – PITTALUGA Nov 4 '15 at 8:05
  • 1
    $\begingroup$ @PITTALUGA Not necessarily. For the proof, it is enough to assume that the list is complete. It is not necessary to assume that all primes upto the largest number are in the list. In principal, the primes upto the largest number in the list can be determined, but Euclid's proof also works, if this is not the case. $\endgroup$ – Peter Nov 7 '15 at 22:18
6
$\begingroup$

An infinite collection of natural numbers is always unbounded.

$\endgroup$
1
$\begingroup$

Let $(p_n)_{n\geq 1}$ be the infinite ordered sequence of prime numbers. Show by induction that for all $n$ :

$$p_n> n $$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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