Public Service Announcement

I'd like to share a heuristic for problem solving in mathematics. It is easy to state and apply, and seems very useful, but many students I've talked with or tutored seem either not to have learned to use it, or not to have recognized its role in their thinking.

Here it is:

When attempting to prove a statement, try to find a logically equivalent statement (e.g. the contrapositive) whose hypothesis and conclusion are more 'constructive'.

What do I mean by 'constructive' statements? Ones which assert the existence of objects, preferably small, easy-to-exhibit ones. By constrast, universal statements, often asserting the nonexistence of certain objects, are 'nonconstructive'.

Here's an example:

Claim: A connected metric space with more than one point is uncountable.

If you're familiar with these terms (wiki them), it should be clear that hypothesis and conclusion are both nonconstructive. Thus, try to prove the contrapositive instead:

A countable metric space with more than one point is disconnected.

This way, we start with an enumeration of points and try to construct a separation.

This strategy is related to 'proof by contradiction', but I'm trying to give some sense of when such strategies are likely to succeed. An example from complexity theory, where this heuristic is close to the heart of our existing methodologies:

Karp-Lipton Theorem: If the Polynomial Hierarchy is infinite, then NP does not have polynomial-sized circuits.

This form of the statement gives the 'lesson' that we want to take home: one plausible complexity hypothesis implies a further kind of complexity. But the proof (like most complexity proofs) is constructive, showing how one kind of simplicity (small circuits for NP) implies another (a PH collapse).

Finally, a beloved classic, arguably prophetic of diagonalization: the infinitude of the prime numbers. This time we find a more constructive equivalent statement that is not quite a contrapositive: 'given a finite list of primes, there exists a prime not on the list'. Then we show a simple algorithm to produce such a missing prime (and if you haven't seen this, I strongly encourage you to try.)