Q&A

In If and Only If Proofs, why's the proof for one direction easier than the other?

+1
−3

This list. this question substantiates proofs where one direction can be proved effortlessly, but the other direction is grueling to prove. Why? If two propositions are equivalent, wouldn't their proofs have the same level of difficulty?

Please don't troll with frivolous "proofs" like 'Fermat's last theorem' iff 0+0=0, but that Reddit thread instances two common cases like Hall's Theorem and a sequence of real numbers converges iff it is Cauchy. In latter, $\Leftarrow$ is effortless but $\Rightarrow$ is grueling.

Why does this post require moderator attention?
Why should this post be closed?

+2
−0

One thing to consider is that the equivalences are generally based on the validity of certain axioms. And then, one direction may only depend on a smaller set of axioms. Now it is possible that the additional axioms help also in the direction that doesn't need it, but it is also possible that the easiest proof still relies only on that smaller set of axioms. Obviously if you effectively start with a different premise (the larger set of axioms plus the property rather than the smaller set of axioms plus the property) that may affect the difficulty of the proof (in either way).

Take for example the Cauchy convergence example you mentioned. It clearly rests on the axioms of the real numbers. If you relax those axioms to, say, those of an ordered field (that is, remove the axiom that the real numbers are complete), then the equivalence does no longer hold, as the rational numbers show: They are an ordered field in which not all sequences converge (a sequence of rational numbers can converge to an irrational number).

On the other hand, the fact that all convergent series are Cauchy series also holds in ordered fields. Therefore the equivalence does not hold in arbitrary ordered fields, but one of the directions can be proved already there.

Now whether the proof that all Cauchy sequences convergence is harder of easier depends on which construction of the real numbers (that is, which set of axioms) you use. If you construct the real numbers through Cauchy sequences, then the proof that each Cauchy sequence converges is trivial: That's how you constructed the real numbers, after all! But if you construct the real numbers by another way (for example, with Dedekind cuts, or with nested intervals), the proof may be more involved.

For better illustration, let's use another equivalence, this time in the natural numbers. The theorem is simple:

An even number is larger than 2 iff it is larger than 3.

Of course the proof is also simple, but it still is easier in one direction:

$\implies$: A natural number larger than 2 either equals 3 or is larger than 3. But 3 is not even, therefore all even numbers larger than 2 are also larger than 3.

$\impliedby$: Any number that is larger than 3 is also larger than 2. This obviously also holds for even numbers.

Clearly the $\impliedby$ direction is simpler (though not by much). And it is simpler precisely because we didn't even have to use the definition of “even”, nor any properties of the natural numbers other than that they are totally ordered and that $3>2$.

Another case where the two directions generally have different difficulty is when an existence statement is involved. To prove “there does exist” all you have to do is to provide an example, which often (but not always!) is easy. On the other hand, when taking “there exists” as condition, this is equivalent to proving the nonexistence when the equivalent condition is not fulfilled. Obviously proving nonexistence can be very hard, as the negation of a “there exists” statement is a “for all” statement.

Why does this post require moderator attention?