Argthtjtr

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.

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".

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.¹

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.

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.

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.

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.

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.