Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.


I'm interested in the issue of "explanatory" mathematical proofs and would like to try to find out what intuitions mathematicians have about proofs of "if and only if" claims, like this one from graph theory "a connected graph is Eulerian if and only if all of its vertices have even degree", and this example from real analysis "a sequence of real numbers is convergent if and only if it is Cauchy". I know that "explanation" and "explanatory" are very vague words, but I'm just hoping to find out what mathematicians think about a particular issue.


In a lot of "if and only if" proofs that I've come across, one direction seems to do some explanatory work, whilst the other direction seems to be "trivial" or "obvious" and so of little, if any, explanatory power. So I was wondering if anyone had an example of a particular proof of an "if and only if" claim where they felt both directions to be explanatory? If you do, I'd be very grateful if you could post them here, and possibly try to indicate what about both directions you find explanatory? Thanks in advance for your help.

share|improve this question
Most likely you want this to be community wiki and have the big list tag, unless I am missing the point of your question. –  B. Bischof Apr 17 '10 at 20:17
I don't really like this question. There are zillions of answers, and I don't feel like making a big list of them is going to be particularly helpful to anybody or for anything. But I've been surprised many times on MO, so I'll wait and see what happens. –  Kevin H. Lin Apr 17 '10 at 20:58
I have absolutely no idea what you mean by "explanatory". From your examples, it seems that one direction is "easy" and so, by implication, the "explanatory" direction is the hard direction. Is that it? –  Andrew Stacey Apr 17 '10 at 21:08
The motivation behind this question might also help. In science, there's supposed to be an asymmetry in explanation, so if A explains B then B cannot explain A, but in maths we can often prove A iff B, so I was curious as to what intuitions people had about whether this gives us a mathematical explanation of B from A and a mathematical explanation of A from B. –  Lea M Apr 17 '10 at 21:28
I know very little about this, but often one can make the notion of "difficult side of an iff proof" quite precise using reverse mathematics. Basically, you try to weaken the axioms of mathematical inference until one direction holds but the other doesn't. I'm not sure what precise role the word "explanatory" plays in this question, but the idea that the easy direction doesn't tell you anything you didn't know before can be put into some formal language. –  S. Carnahan Apr 17 '10 at 22:20
show 2 more comments

closed as off-topic by Steven Landsburg, Andres Caicedo, Daniel Moskovich, Karl Schwede, Carlo Beenakker Nov 17 '13 at 19:33

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "This question does not appear to be about research level mathematics within the scope defined in the help center." – Steven Landsburg, Andres Caicedo, Daniel Moskovich, Karl Schwede, Carlo Beenakker
If this question can be reworded to fit the rules in the help center, please edit the question.

2 Answers

up vote 3 down vote accepted

I think that, in most proofs of equivalence between models of computation (“a function can be computed by an automaton of type A iff it can be computed by an automaton of type B”), both directions usually offer some insight.

This is a simple but fundamental example from complexity theory. Define NP to be the class of languages (equivalently, decision problems) recognised by nondeterministic Turing machines operating in polynomial time. Then:

Theorem. A language L is in NP iff there exist a deterministic Turing machine M operating in polynomial time and a polynomial p such that, for each string x,

  • if xL then there exists a string y with |y| ≤ p(|x|) such that M accepts (x, y);

  • if xL then M rejects (x, y) for all strings y with |y| ≤ p(|x|).

The deterministic Turing machine M can be called a verifier, and the strings y accompanying each string xL that make M accept are called short certificates: they constitute an easily verifiable proof of membership of x in the language; no string outside L possesses such a membership proof.

For a proof of this theorem see, for instance, this page on Wikipedia; notice that both implications have an easy but not completely trivial proof.

The proof of “L has short certificates ⇒ LNP” shows how the “magic” of nondeterminism can be used to guess a certificate (if it exists for a particular input string).

The proof of “LNPL has short certificates”, on the other hand, shows that nondeterminism, which might appear an unrealistic notion, implies the very concrete existence of short, easily checkable proofs for some properties of the input that might be too hard to decide efficiently.

share|improve this answer
Thanks so much for your answer. I like the particular example very much. –  Lea M Apr 18 '10 at 17:07
add comment

This is not really an answer so much as a series of comments. I think the problem is that mathematicians generally view proofs as explanations, so part your question isn't quite meaningful. Of course, not all proofs are the same. Some proofs may be preferred to others based on aesthetic criteria such as brevity, clarity, elegance... To address your other point, in "if and only if" proofs, there often is an easy direction and a hard direction, but not always. Sometimes both directions are at the same level (to take a trivial example x+y = z iff x = z-y). Or it may be embedded in a cycle of implications such as A => B => C=>A, where only some links in the chain are trivial. I'm not sure if this clarifies anything, but if it doesn't, then perhaps you can reformulate the question.

share|improve this answer
add comment

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