1
$\begingroup$

If we show that a claim is equivalent to a tautology (which is stronger than showing the claim implies a tautology), how come that isn't a valid method of proof?

  • 0
    What text or class did this come from?2012-11-04

3 Answers 3

6

Who says it isn't valid? In what context? For what purpose?

In some (actually most) mathematical contexts, for some (actually most) mathematical purposes, demonstrating that a formula is an instance of a tautology is a perfectly cromulent method of proving it.

Among the exceptions is if the context is a course in formal logic and the purpose is to gain or show familiarity with a particular formal proof system and how it works. In that (fairly narrow) circumstance, appealing to tautology obviously misses the point, at least until you have formally proved in general that every tautology has a proof in the proof system at hand.

  • 1
    +1 for apparently producing the first-ever instance of "cromulent" on this site.2012-11-04
3

If $T$ is a tautology, $(P\Rightarrow Q)\Leftrightarrow T$ is enough to prove $P\Rightarrow Q$, but it's overkill. All you need is $(P\Rightarrow Q)\Leftarrow T$. $(P\Rightarrow Q)\Rightarrow T$ is always true because $T$ is a tautology - it holds whether $P\Rightarrow Q$ is true or not, so it is a tautology in and of itself. On the other hand, $(P\Rightarrow Q)\Leftarrow T$ is only true when $P\Rightarrow Q$ is true, and in fact is equivalent to $P\Rightarrow Q$.

1

If you successfully show that a statement is equivalent to a tautology, you have proven that statement. However, while inarguably mathematically correct, such a proof may be considered stylistically unacceptable because of the redundancy inherent in making each step of the proof an equivalency rather than a simple forward-implication.

And for a proof by tautology, you NEED NEED NEED every step to be a full logical equivalency, otherwise you're just begging the question: $(p\to\mathrm{T})\not\to p$ because, by the definition of logical implication, $\mathrm{F}\to \mathrm{T}$. Assuming otherwise is the #1 cardinal sin in all of mathematics. If I kill everything I eat, that means I can swat flies without eating them, but I can't eat so much as a chicken dinner unless I was the one to wring the chicken's neck. If I eat everything I kill, then I can eat whatever I want, but I do have to eat the flies I swat.

Ordinary direct proofs, on the other hand, require only regular forward-implication, so to prove $p$, you don't absolutely need to work with logical equivalencies every step of the way as long as you're not trying to prove by tautology. And since every logical equivalency has both types of implication built into it, you can convert any proof by tautology into a direct proof by starting with the tautology and working backward until you arrive at your conclusion.

If this question was asked in the context of a course on proofwriting, it's possible that your professor just wanted a direct proof. There's nothing wrong with a proof by tautology; sometimes converting a proof by tautology into a direct proof just masks your thought processes and produces a proof that is mathematically correct but kind of bizarre. But one way or the other, sometimes professors just want a direct proof, especially if that's all they've taught you how to do just yet and want to see how well you can write direct proofs.