proof there are infinitely many prime numbers using induction

Euclid proved that there are infinitely many primes. His proof doesn't exactly use induction but it is close. Rewrite the proof to use proof by induction.

Euclid's proof

Basis

Induction Hypothesis
let be an exhaustive list of prime numbers where k is an integer greater than 0
Induction step
consider has cardinality k

let
then
Therefore but not in

Conclusion
by the PMI there are infinitely many prime numbers

Why? This is not a proof that follows from PFI. You're not doing induction on the naturals, because almost all naturals are not primes, and you're not doing induction on primes because you'd need to assume the answer beforehand.

Just to clarify (since I can't figure out how to edit the original post):

The reason you can't do induction on primes to prove there are infinitely many primes is that induction can only prove that any item from the set under consideration must have the property you want. The property you're trying to prove (that there exist infinitely many primes) is not a property of the individual primes. You can't establish a base case or an inductive step if you don't have a provable property for the individual items.

So your argument is flawed because you assume exactly what you're trying to show. Notice you say, "let S_k+1 = [...]p_k+1". "Let" means you just assumed that a larger set of primes exists, with one additional prime when you did that, even though that's what you're trying to show. You derive a contradiction but it's because you put it in there yourself.

The proper way induction works:

1) You have a set of things that you can prove is well-ordered (which means they're totally ordered and every subset has a least element). We can expand this idea to different kinds of orders (well-founded relations, larger countable ordinals, uncountable ordinals, etc.), but for simplicity here you can assume this is a naturally-ordered set that behaves just like the natural numbers (both primes and naturals behave like this).

2) You prove the property you want to show holds for one or more consecutive base cases.

3) You prove that anytime the property holds for a set of cases, it must also hold for the least case not in that set.

4) By FIP, this proves that the property holds for all cases which are at least as large as the smallest base case. (If the smallest base case is the smallest case, it proves the set of things is equal to the set of things having the property.) But again, you need a property of individual items that you want to show.

Quote:

---

Originally Posted by Jskid

Euclid proved that there are infinitely many primes. His proof doesn't exactly use induction but it is close. Rewrite the proof to use proof by induction.

Euclid's proof

Basis

Induction Hypothesis
let be an exhaustive list of prime numbers where k is an integer greater than 0
Induction step
consider has cardinality k

let
then
Therefore but not in

Conclusion
by the PMI there are infinitely many prime numbers

---

Try this:

For any natural number N there is a prime greater than N.

Base case: N=1, since 2 is prime this holds.

Induction step, suppose for some k there is a prime greater than k, now show that there is a prime greater than k+1.

(this is a bit peculiar since we do not need to use that there is a prime greater than k to prove there is a prime greater than k+1, but it is still induction..)

CB