[Math] Proofs Using Tautologies

logicproof-explanationproof-verificationproof-writingpropositional-calculus

Let's say I want to formally prove a statement of the form $$p \implies q$$
So I do a bit of work,some re-arranging and eventually I arrive at a statement of the form
$$p \implies p$$
which is a tautology, as this is true for all values of $p$, but also an obvious truth. Have I proved $p \implies q$?

Reaching "Obvious Truths"

Generally when doing proofs, reaching something that is obviously true" is not a proof. Like for example if you're proving that $\sqrt{2}$ is irrational, reaching $1 = 1$ has not proved anything. But in this case I've reached a tautology, does that make my original implication true?

To me this seems like a contradiction, because the tautology I've reached is an obvious truth, which is a big "no-no" in proof validation.

Furthermore does the convention that reaching something an "obvious truth" is not a mathematically rigorous way of completing a proof, extend to all proof techniques?

For example does reaching an "obvious truth" still not constitute a proof for the following proof techniques :

  1. Direct Proofs
  2. Indirect Proofs (Proofs by Contrapositive)
  3. Proof by Contradiction
  4. Proof by Mathematical Induction
  5. Vacuous Proofs
  6. Trivial Proofs
  7. Proof by Cases

Last question, in the example I've given above seems I've started off with trying to Directly prove $p \implies q$, but when I've reached $p \implies p$, it's now a Trivial Proof, which would the above proof example I've given fall under? Direct Proof or Trivial Proof?

Some background context if needed :

I've asked this question in response to a previous questions I've asked, on the $\epsilon – \delta$ definition of a limit, where I try to prove a statement of the form $p \implies q$ by reducing it to the form $p \implies p$, and I argue that it is not mathematically rigorous, as I've reached an obvious truth, however another user argues that I have formally proven what I set out to prove as I reached a tautology, by manipulating the original implication : https://math.stackexchange.com/a/1745657/266135

Another extremely relevant question on reaching "obvious truths" : Is this direct proof of an inequality wrong?

Best Answer

"Reaching an obvious truth" (such as $p\to p$ ro $1=1$) is a valif method of proof if the steps used in reaching this obvious truth are equivalence transforms. That is, if your argument goes like

$A_1$ is equivalent to $A_2$, which is equivalent to $A_3$, $\ldots$, which is equivalent to $A_n$, which is a tautology

then you have proved $A_1$. However, you must be careful that not a single "is equivalent" step turns out to be only an "implies" step. On the other hand, we do not even need equivalence, we only need one direction - the backward one. Therefore it is often better to write up a proof in the other direction:

We have the tautology $A_n$. This implies $A_{n-1}$. $\ldots$ This implies $A_3$. This implies $A_2$. This implies $A_1$, as desired.

The "from $A_1$ to $A_n$" method may be best suited for discovering a proof, but "from $A_n$ to $A_1$" (which may then be a direct proof) is best suited for presenting a proof (and at the same time to discover gaps in the proof because it becomes easier to spot steps that fail to be equivalences).

Related Question