Results 1 to 10 of 10

Math Help - proving infinite n

  1. #1
    Newbie
    Joined
    Sep 2011
    Posts
    7

    proving infinite n

    Hello

    Given

    \forall n0, \exists n> n0, P(n)

    I am trying to prove that there are an infinite number of values n for which the
    property
    P(n) is true.

    My initial thoughts are to assume only a limited n for which P(n) is true, for example only P(1), P(2) and P(3) are true and the rest is false. Then prove impossible, but I got stuck.

    Could someone please help?

    Thanks in advance
    Kardash
    Follow Math Help Forum on Facebook and Google+

  2. #2
    A Plied Mathematician
    Joined
    Jun 2010
    From
    CT, USA
    Posts
    6,318
    Thanks
    4
    Awards
    2

    Re: proving infinite n

    As a clarification, what is the property P(n)?
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Sep 2011
    Posts
    7

    Re: proving infinite n

    Quote Originally Posted by Ackbeet View Post
    As a clarification, what is the property P(n)?
    Unfortunately, the question has not specified it. Is it possible to solve it without knowking P?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    A Plied Mathematician
    Joined
    Jun 2010
    From
    CT, USA
    Posts
    6,318
    Thanks
    4
    Awards
    2

    Re: proving infinite n

    Quote Originally Posted by kardash View Post
    Unfortunately, the question has not specified it. Is it possible to solve it without knowking P?
    Come to think of it, I think the answer is yes. Last night I don't think I was thinking clearly. You are given the statement that

    (\forall n_{0})(\exists n)((n>n_{0})\land P(n)).

    I think your proof method is on the right track. If P(n) is not true for an infinite number of n's, then there is some maximum value N such that P(N) is true. Can you see how to set up a contradiction here?
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Newbie
    Joined
    Sep 2011
    Posts
    7

    Re: proving infinite n

    Thanks for replying.

    This is what I am thinking about, but appreciate your help to formalize it and state it in proper math terms.

    First I negated the sentence
    \exists n0, \forall n> n0, P(n)

    Then I assume P(n) is only true for P(1), P(2)

    Then I assume n0=10

    In this case P(n) does not hold.


    Could you help to formalize this properly?

    Kardash
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Senior Member
    Joined
    Feb 2010
    Posts
    466
    Thanks
    4

    Re: proving infinite n

    Suppose there are only finitely many n such that P(n). If there are no n such that P(n), then given any m there is a k>m such that P(k), which contradicts that there are no n such that P(n). If there is an n such that P(n), then let m be the maximum such n, but then there is a k>m such that P(k), which contradicts that m is the maximum. It's that easy. The important lemma used is that any finite set of natural numbers has a maximum member.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Newbie
    Joined
    Sep 2011
    Posts
    7

    Re: proving infinite n

    Thank you for your reply. You are an expert and I was not able to understand your statement fully. Kindly help me understand.

    Quote Originally Posted by MoeBlee View Post
    Suppose there are only finitely many n such that P(n). If there are no n such that P(n), then given any m there is a k>m such that P(k), which contradicts that there are no n such that P(n).
    We assume there is finite P(n), OK. Then what is meant by "If there are no n such that P(n)" ?? Could you give me an example?


    Quote Originally Posted by MoeBlee View Post
    If there is an n such that P(n), then let m be the maximum such n, but then there is a k>m such that P(k), which contradicts that m is the maximum. It's that easy. The important lemma used is that any finite set of natural numbers has a maximum member.
    Could you explain by examples?

    Was my initial thoughts correct? Or you have suggested a new approach?


    My apologies but I was not able to understand. I am a beginner ....Thanks
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Senior Member
    Joined
    Feb 2010
    Posts
    466
    Thanks
    4

    Re: proving infinite n

    Quote Originally Posted by kardash View Post
    You are an expert
    Not really.

    Quote Originally Posted by kardash View Post
    what is meant by "If there are no n such that P(n)" ?
    It means: It is not the case that there exists a natural number n such that P(n) holds.

    The expression "P(n)" stands for (in a manner of speaking) "n has the property P". To say "there is no (natural number) n such that P(n)" is to say that there is no natural number with the property P.

    The argument is simple:

    The assumption of the problem is that given any natural number m there is a natural number k greater than m that has property P. So let m be any natural number whatsoever. So there is a natural number k greater than m that has property k. So the set of natural numbers having property P is nonempty. Now, toward a contradiction suppose that the set of natural numbers having property P is a finite set. So the set of natural numbers that have property P is nonempty and finite. So there is a greatest natural number m having property P. But then, by the assumption of the problem, there is a natural number k greater than m such that k has property P. But that contradicts that m is the greatest natural number having property P. So the set of natural numbers having property P is not a finite set, i.e., the set of natural numbers having property P is an infinite set.
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Newbie
    Joined
    Sep 2011
    Posts
    7

    Re: proving infinite n

    Thank you for clarifying that.

    In this case, I guess there is no need for me to negate the sentence, right? Will it be sufficient to explain in words?


    Thanks again
    Follow Math Help Forum on Facebook and Google+

  10. #10
    Senior Member
    Joined
    Feb 2010
    Posts
    466
    Thanks
    4

    Re: proving infinite n

    We assume the negation of "there are infinitely many n such that P9n)", then derive a contradiction, then conclude "there are infinitely many n such that P(n)".

    As to what is sufficient for this proof, it depends on the context, whether the exercise is with regard to a certain mathematical system in a certain formula language, or just ordinary mathematics that mixes symbols and natural language, or whatever. In any case, the argument I gave is adequate as an ordinary mathematical argument.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. proving an infinite set
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: August 19th 2011, 10:21 AM
  2. closed subset proving in infinite sequence
    Posted in the Differential Geometry Forum
    Replies: 0
    Last Post: October 14th 2010, 11:11 AM
  3. Proving that A~B then B~A for infinite sets
    Posted in the Differential Geometry Forum
    Replies: 1
    Last Post: September 21st 2010, 10:11 AM
  4. Replies: 6
    Last Post: September 10th 2008, 03:44 PM
  5. Help proving that an infinite series diverges
    Posted in the Calculus Forum
    Replies: 2
    Last Post: April 22nd 2008, 06:23 AM

Search Tags


/mathhelpforum @mathhelpforum