Within If and Only If Proofs, why can the proof for one direction be easier than the other?

1k Views Asked by At

For $ P \iff Q$, my initial sentiment is that because P and Q are equivalent, the total of two proofs (one for each direction) should entail the equivalent level of "difficulty" or "exertion", as well as an analogous number of steps. Otherwise, they wouldn't be equivalent.
Yet, this is false and I can't perceive why?

Moreover, a priori, how would one divine/previse: $2.$ if one direction is truly easier than the other ?

$3.$ then which of the two is it, on the condition that $2$ is true?

5

There are 5 best solutions below

4
On

I do not "see" any "logical" reason why - in general - the two "directions" of the equivalence poof must have different "levels of difficulty"...

(i) how is "measured" the "level of difficulty" ?

(ii) we do not need necessarily divide the equivalence proof into two subproofs: one for each "direction"; nothing prevents us - in general - to work with a "chain of equivalences" (there is a proof systems, named Equational Logic that is based exactly on chains of equivalences [but see George Tourlakis, Mathematical Logic (2008), for a rigorous treatment].

2
On

Because you are proving two things which happen to be converses. Given two theorems, often one is harder than the other. This still is true when they are converses because being the converse of another statement doesn't give you anything special.

4
On

Obviously it is not necessary that two directions have the same level of difficulty; Like when one direction is a special case of the other.For example when we want to prove that a homomorphism is 1-1 we only need to prove at one point:0

0
On

I don't think there is a reasonable general answer to this very genuine phenomenon: that's just the way the (mathematical) world is.
In a related area, most of modern cryptography (and thus of the modern economy: think banking) relies on the fact that it is very easy to multiply two huge prime numbers $p, q$ but extremely difficult, given just their product $n=p.q$, to retrieve the two factors $p,q$.

0
On

Well, as you know, Fermat’s Last Theorem has been proven. Therefore you don’t lose any truth if you modify the statement “$1 + 1 = x$ if and only if $x = 2$” to “$1 + 1 = x$ if and only if ($x = 2$ and, yeah, Fermat’s Last Theorem is true)”. This doesn’t have to happen explicitly. You can easily add a lot of implicit statements to one side. This may be one reason why directions of equivalences are not equally easy to prove.

For any equivalence whose directions are equally easy to prove, there a many modifications breaking the symmetry of difficulty. So if you assume that equivalences of the former kind exist, mathematicians are apparently more interested in their asymmetric modifications, and it is hard to see what the “pure equivalences” behind them are.

But I don’t think it’s helpful to think of equivalences as modifications of pure equivalences (whose direcetions are equally easy to prove) because there’s probably no sensible way of determining whether an equivalence is pure or not (maybe the only pure equivalence is “true if and only if true”?) – I was just addressing your feeling that it should be something like that.