Results 1 to 4 of 4

Math Help - when is a counter example not enough?

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

    when is a counter example not enough?

    My textbook states "To show a theorem is false, it is enough to find a single case where the implication does not hold. However to show that a theorem is true, we must give a proof that covers all cases".

    Then it asks "There exists a positive integer n such that n^2<n Would it make sense to attempt to prove this statement with a counter example?" The answer is no you need to prove it for all n.

    But it just said you can prove a theorem false with a counter example?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Member
    Joined
    May 2011
    From
    Sacramento, CA
    Posts
    165

    Re: when is a counter example not enough?

    The statement in question says that there exists SOME n for which its square is strictly less than n. If you show a counter example, there is nothing barring the fact that you simply chose the wrong n. A theorem would be something like "for all integers n, n \leq n^2." Notice the universal quantifier on this statement. To show it is false, you simply have to show that "for all" does not hold true. But as I emphasized above, the statement you provided was not a universal statement. It had an existential quantifier. Therefore, you need to know what it is you are countering. You would need to counter that actual n for which it is supposed to be true. However, you don't know which n that could be. It can be any positive integer. Therefore, you need to prove it is false for all possible choices of positive integers.

    To think about it differently, suppose you run the dialog in your head.

    "There exists a positive integer for which its square is strictly less than it." Yeah, but the square of 1 is not less than 1. "That is true, but there still exists a positive integer for which it is true."

    You see the problem there? You would reasonably charge the person with "well, which positive integer is it?!" It is like saying "there exists intelligent life on other planets." Yeah, but look at Mars, we don't see any intelligent life. "Yeah, so? It's still out there somewhere." To prove that charge false, you would have to show that on every planet out there in the universe, there is no intelligent life. Of course, that is probably impossible. However, proving the statement you provided is not so impossible. In fact, it is quite easy to demonstrate that it cannot be true of the positive integers.
    Follow Math Help Forum on Facebook and Google+

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

    Re: when is a counter example not enough?

    Quote Originally Posted by Jskid View Post
    My textbook states "To show a theorem is false [...]".
    What textbook is that? We don't show that a theorem is false. By definition, a theorem is a statement that is provable from the axioms, thus a theorem is TRUE given the truth of the axioms.
    Follow Math Help Forum on Facebook and Google+

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

    Re: when is a counter example not enough?

    I see I was confused. The book is Discrete Mathematics for Logic and Foundations. I was paraphrasing and it may be technically correct but in general I hate this book.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. [SOLVED] Trying to Find a Counter Example
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: April 11th 2011, 06:55 PM
  2. box counter problem
    Posted in the Statistics Forum
    Replies: 6
    Last Post: May 15th 2010, 08:54 AM
  3. counter examples!
    Posted in the Advanced Algebra Forum
    Replies: 4
    Last Post: December 8th 2009, 02:09 PM
  4. counter example
    Posted in the Advanced Algebra Forum
    Replies: 2
    Last Post: December 2nd 2009, 12:07 AM
  5. I need a counter example
    Posted in the Advanced Algebra Forum
    Replies: 5
    Last Post: April 13th 2009, 02:34 AM

Search Tags


/mathhelpforum @mathhelpforum