Results 1 to 4 of 4

Math Help - proof there are infinitely many prime numbers using induction

  1. #1
    Member Jskid's Avatar
    Joined
    Jul 2010
    Posts
    160

    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
    S={2,3,5,7,11,13...}
    Induction Hypothesis
    let S_k={p_1, p_2, p_3,...,p_k} be an exhaustive list of prime numbers where k is an integer greater than 0
    Induction step
    consider S_k={p_1, p_2, p_3,...,p_k}has cardinality k

    let S_{k+1}={p_1, p_2, p_3,...,p_k, p_{k+1}}
    then S_{k+1}={S_k, p_{k+1}}
    Therefore p_{k+1} \in S_{k+1} but P_{K+1} not in S_k

    Conclusion
    by the PMI there are infinitely many prime numbers
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Member
    Joined
    Aug 2011
    Posts
    127

    Re: proof there are infinitely many prime numbers using induction

    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.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member
    Joined
    Aug 2011
    Posts
    127

    Re: proof there are infinitely many prime numbers using induction

    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.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Grand Panjandrum
    Joined
    Nov 2005
    From
    someplace
    Posts
    14,972
    Thanks
    4

    Re: proof there are infinitely many prime numbers using induction

    Quote Originally Posted by Jskid View Post
    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
    S={2,3,5,7,11,13...}
    Induction Hypothesis
    let S_k={p_1, p_2, p_3,...,p_k} be an exhaustive list of prime numbers where k is an integer greater than 0
    Induction step
    consider S_k={p_1, p_2, p_3,...,p_k}has cardinality k

    let S_{k+1}={p_1, p_2, p_3,...,p_k, p_{k+1}}
    then S_{k+1}={S_k, p_{k+1}}
    Therefore p_{k+1} \in S_{k+1} but P_{K+1} not in S_k

    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
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. induction..prime number proof
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: November 30th 2010, 09:47 AM
  2. proof with perfect and prime numbers
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: September 28th 2010, 08:46 PM
  3. Proof relating to prime numbers
    Posted in the Number Theory Forum
    Replies: 6
    Last Post: January 13th 2010, 12:31 PM
  4. Proof relating to prime numbers
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: January 13th 2010, 11:02 AM
  5. Proof with prime numbers
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: October 25th 2009, 09:58 PM

Search Tags


/mathhelpforum @mathhelpforum