In "if and only if" proofs, why's 1 direction easier to prove than the other?
This list on Math StackExchange instantiates (biconditional) logical equivalences where one direction can be proved swimmingly, but the other direction is racking to prove. If two propositions are equivalent, why can't they be proved with the same level of difficulty?
Please don't troll with frivolous "proofs" like
This Reddit thread instances two common cases like Hall's Theorem, and a sequence of complex numbers converges $\iff$ it is Cauchy ($\Leftarrow$ is effortless, but $\Rightarrow$ is grueling).
2 answers
You are accessing this answer with a direct link, so it's being shown above all other answers regardless of its score. You can return to the normal view.
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.
0 comment threads
Here's a good one: Every set is well-orderable iff the Axiom of Choice holds.
It is quite challenging to prove that the Axiom of Choice implies that every set is well-orderable. Smullyan and Fitting build up to it in a focused but leisurely manner over the course of 3 chapters in their "Set Theory and the Continuum Problem" (2010, rev. ed.) During the course of this, they establish a number of theorems about classes inductive sets, superinductive sets, progressing functions, slowly progressing functions, constructs they call $g$-towers and slow $g$-towers, and culminate with a straightforward proof which defines a slowly progressing function $g$ based on applying a choice function to the complement of the sequence of images of that function.
However, if every set is well-orderable, the axiom of choice follows trivially. Indeed, let $S$ have a well-ordering. Then for every non-empty subset of a set $S$, the choice function on that subset is its smallest element under that well-ordering.
0 comment threads
2 comment threads