39
$\begingroup$

I am taking a basic analysis course. This is a general question that I often encounter in weekly homework. How should we start to attack this type of question: if the statement is true, prove it; if not true, give a counterexample? Yesterday evening I spent four hours looking for a counterexample, and finally figured that the statement was indeed true. I tried so hard to find a counterexample because I was not able to prove the statement at first. Are there any steps to follow in terms of this type of questions? In particular, sometimes a statement does not look like it is true. In this case, how can I quickly figure out whether I should try counterexamples or keep the efforts on proving the statement is true? The core problem is that this type of question is very time-consuming according to my homework experience. I desperately doubt I could figure out a correct answer during a timed exam next week.

$\endgroup$
  • 54
    $\begingroup$ That's exactly the routine in mathematical research $\endgroup$ – lhf Feb 13 at 15:09
  • 12
    $\begingroup$ If I am not mistaken you want to know from the beggining if something is wrong or true? If this is the case then math would be uninteresting, I suppose... $\endgroup$ – dmtri Feb 13 at 15:33
  • 4
    $\begingroup$ I didn't see anyone mention that it happens that it is unprovable to be true or false. So be prepared for this case too - any logic system that is sufficiently complicated to be interesting has unprovable statements [google 'Gödel'] $\endgroup$ – Aganju Feb 13 at 22:43
  • 3
    $\begingroup$ @lhf: Only half. The other half is finding the correct questions. Also, once you have an answer, finding the right answer (not just correct). $\endgroup$ – tomasz Feb 13 at 23:22
  • 7
    $\begingroup$ @Aganju: That's overwhelmingly unlikely to be asked as a homework question in an undergraduate course. $\endgroup$ – Daniel R. Collins Feb 14 at 0:14
41
$\begingroup$

What was the original problem? Oh, no matter.

One strategy is to first try to prove by contradiction that the statement is true. Such an effort will identify necessary conditions for a counterexample. If through such an analysis you realise you can also give sufficient conditions for a counterexample, and you can work out how to satisfy them, you'll have a counterexample. With any luck, in the event the statement is true you'll find a valid proof soon enough. (Once you do, it's worth checking whether it can be rewritten to not use contradiction; students new to proof-writing sometimes unnecessarily add a contradiction "wrapper" around a direct proof.)

Note that if a counterexample exists in a textbook exercise, there will be a simple one that slightly complicates a situation that illustrates a weaker true claim. For example, if I asked you to prove or refute-by-counterexample the claim that all finite groups are Abelian, the hope is you'd quickly find this counterexample. It's slightly more complicated, though only slightly, than the case of a finite group with a single generator, which of course would be Abelian. So the hope is you'd think, "let's try to make a group with two generators; that might do it".

$\endgroup$
49
$\begingroup$

I disagree with the approach of proving by contradiction as a start.

In most cases, and which ones are the exception simply requires experience, you should just start by trying to prove the statement as if it were true. There's no point in starting with a proof by contradiction. Just try to prove it.1

If you are careful, and again experience is needed here, then your derivation will either be successful, or you will get stuck.

Now ask yourself. Why did you get stuck? Maybe you need to assume that $x+1=y$, or maybe you need to assume that the function is continuous at $0$. Who knows? It depends on the problem and on your attempt to prove it. The next step, then, is to try and engineer a counterexample using the failure of this assumption. If you need to assume $x+1=y$ in order for it to work, take an example where $x=0$ and $y=3$. And so on. If that works, well done, you found a counterexample, and you even got a free bonus information: you found a condition that will let you complete the proof.

Of course, it might be that your attempt at a proof was bad. Maybe you tried to do something wrong. Who knows. But if your attempted counterexample failed, that gives you new information, it tells you that the information you thought was crucial for the proof is in fact not crucial for the proof.

So you have to start over again, and try a different method and a different approach. And repeat this until the result is satisfactory.

Unfortunately, it will not be the case that this will always work. Sometimes you are missing a crucial piece of knowledge that would simplify the work. Or sometimes you just made a series of mistakes in your proof, and you thought you proved it, whereas you haven't actually proved the right statement. This is why it is a good idea to work with a friend, where you can check each other and discuss these kind of things.

One last thing, which might be worth discussing, is how to approach a proof to begin with. Well, if you want to prove that things fall down to the earth, you start by letting a few things fall down and see how that works out. Similarly in mathematics, experimenting is not a bad idea. If you need to prove some equation holds, try plugging in some small numbers, $0$ and $1$ are perhaps $\sqrt2$, if the equation makes it convenient. If you have to prove something about functions, try a constant function, or $e^x$, or whatever.

Toy examples are very important towards understanding why something is true, and if you get some general idea as to why something might be true, it will also give you an idea as to how it should be proved.


  1. Of course, if the natural angle of attack is by contradiction, there's no point in not doing that either.
$\endgroup$
  • $\begingroup$ Thanks, Asaf! I prefer figuring out answers on my own instead of working with friends, though it often takes me more time. However, the experience of pushing myself to think over the edge truly develops the deeper understanding in math. $\endgroup$ – James Wang Feb 13 at 22:32
  • 11
    $\begingroup$ There's is an old Jewish saying "Knife only sharpens on the leg of its fellow" (well, it translates poorly). There is another saying, "Torah is only bought in a group". The point is that you need someone to discuss and quibble about the definitions, about the theorems, about the derivations. That's how you learn things. Doing it on your own is fine, but ultimately, mathematics is a social activity. If you can't do it with other people, you are not really doing it. $\endgroup$ – Asaf Karagila Feb 13 at 22:34
  • $\begingroup$ Got it. Will try! $\endgroup$ – James Wang Feb 13 at 22:36
21
$\begingroup$

As @lhf comments, this is exactly what you encounter doing mathematical research.

You suspect something is true. You try to prove it. If you keep running into dead ends you change your guess and suspect it's false. Then you look for counterexamples. If you keep running into dead ends you change your guess again - and so on until you understand the situation, or decide to work on another problem.

That strategy is good for this kind of homework question too. You learn a lot in the back and forth. Since it's homework and not a research question, you will probably reach the correct solution in a reasonable length of time.

On an exam this kind of question is reasonable only if the answer is clear to someone who has mastered the material - you know a theorem that applies, or you recognize that some important hypothesis is missing.

$\endgroup$
9
$\begingroup$

It is a good habit to try to prove and to try to get a counterexample simultaneously. That type of mentality is necessary to be a successful mathematician. You also need to have a feeling about when to leave a problem; you will get that from solving lots of problems. Follow the book How to Solve It by Pólya for more detailed explanation.

$\endgroup$
  • 1
    $\begingroup$ That's a really good book, by the way; my copy's so well-read it's in poor shape. It's useful not just for "obvious" mathematicians but also other problem-solvers you could argue are doing maths of sorts, such as programmers. $\endgroup$ – J.G. Feb 13 at 16:23
  • 1
    $\begingroup$ @J.G. It is not very useful for Computer Scientists, there is another version of it specially for Computer Scientist named as How to solve it by Computer . See the preface here. $\endgroup$ – tarit goswami Feb 13 at 17:30
  • 1
    $\begingroup$ I had a different kind of computer expert in mind. I know a team leader of developers who swears by it. $\endgroup$ – J.G. Feb 13 at 17:48
7
$\begingroup$

To the solutions elsewhere, I'd add some rules of thumb in the nature of pursuing a math degree on the under graduate level.

I found that when given such a problem, a counter example was usually apparent within a few minutes contemplation. If you couldn't find one by then, you probably had something you needed to prove.

Review your earlier work. Such questions are usually just a mild extension of something previously addressed in examples or homework.

Perhaps the prof went easy on us, so such problems seemed among the easiest. I think it more likely I had exceptionally good study partners and we were careful to share info instead of copy for the sake of having homework to turn in.

I recommend making it a group activity and make sure you do your homework. Seems like you are doing the latter very well, spending four hours on a problem on your own. Shows a lot of dedication. But I stress that you do not have to struggle alone.

$\endgroup$
  • 2
    $\begingroup$ +1 for the "review earlier work" comment. Typically a handful of functions will provide all you need for that basic analysis course. Have them up your sleeve for the exam. $\endgroup$ – Keith Feb 14 at 1:51
5
$\begingroup$
  1. Ask yourself what must necessarily be true about the counterexample.
  2. If those conditions seem at odds with each other, try to prove they are inconsistent. Maybe it's clear that only trivial examples exist. If they seem compatible, try to find some object that satisfies them.
  3. If you find an object, see if it's a counterexample. If it's not, then figure out what condition it's missing to be a true counterexample. Add that to your list of conditions, and repeat.
$\endgroup$
4
$\begingroup$

All of the other answers are great. I would second everything they’ve said, plus the following:

  1. For every “if then” statement in a Theorem, find an example that aligns with the proof. This should be an example that isn’t super easy, but illustrates what’s going on in the proof.
  2. For the theorems listed above, find several examples that match the conclusion, but don’t match the criteria in the hypothesis.
  3. For the same Theorem, find several examples that don’t match the criteria, and don’t find the conclusion.

To work the problems well, one must have a strong understanding of the theorems complete with examples and counter-examples. Doing this has helped me find counterexamples/proofs faster by finding when the theorems apply/don’t apply.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.