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 $\displaystyle 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?
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, $\displaystyle 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.
Re: when is a counter example not enough?
Quote:
Originally Posted by
Jskid
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.
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.