Proofs Using Tautologies

Question

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?

Answer 1

"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).

Answer 2

When you are exploring and discovering how to prove a statement, you want to explore by trying to reduce the conclusion to a statement from the hypothesis. That way, you can see how the conclusion is related to the hypothesis and from that connection, write your proof.

However, when you are writing your proof, you always start from the hypothesis to the conclusion. That just makes sense: You can not assume your conclusion and prove the hypothesis because that is just backwards. The $\epsilon-\delta$ article you read indeed had correct reasoning for why the limit was true and understood the meaning of the $\epsilon-\delta$ limit, but it didn't have an actual proof. It just kind of showed that the statement was true by showing the connection between the hypothesis and conclusion. It didn't actually prove how the hypothesis implies the conclusion, so it was not a real proof. However, given this connection, we can create our own direct proof:

For any $\epsilon > 0$. We can choose $\delta=\frac \epsilon 3$ such that if $0 < \lvert x-5\rvert < \delta$, then $\lvert f(x)-3 \rvert < \epsilon$. We will now prove this directly. We start with our hypothesis:

$$0 < \lvert x-5\rvert < \frac \epsilon 3$$

This is actually an AND statement: $0 < \lvert x-5\rvert$ and $\lvert x-5\rvert < \frac \epsilon 3$. However, we really don't need the first statement since $f(x)$ is still defined at $x=5$, so we can just use the second one.

$$\lvert x-5\rvert < \frac \epsilon 3$$

Multiply both sides by $3$.

$$\lvert 3x-15\rvert < \epsilon$$

$3x-15=3x-3-12=f(x)-3$, so substitute:

$$\lvert f(x)-12\rvert < \epsilon$$

Thus, we have shown that $0 < \lvert x-5\rvert < \frac \epsilon 3$ implies $\lvert f(x)-12\rvert < \epsilon$ for all $\epsilon > 0$, meaning we have proved the limit.

---

Notice, how we used the same equations and reasoning as the article, but we just wrote it backwards. We can do the same thing with the inequality proof:

We start with an obvious truth:

$$2 > 1$$

Since $n$ is positive, we can multiply both sides by $n$:

$$2n > n$$

Add both sides by $n^2$:

$$n^2+2n > n^2+n$$

Factor the left side and multiply the right-hand side by $1=\frac{n+2}{n+2}$:

$$n(n+2) > \frac{(n^2+n)(n+2)}{n+2}$$

Since $n$ is positive, so is $n+2$, so we can divide both sides by $n+2$:

$$n > \frac{n^2+n}{n+2}$$

Multiply the left-hand side by $1=\frac{n+1}{n+1}$ and factor the right-hand side:

$$\frac{n(n+1)}{n+1} > \frac{n(n+1)}{n+2}$$

Divide both sides by $n+1$:

$$\frac{n}{n+1} > \frac{n}{n+2}$$

Thus, we have shown $\frac{n}{n+1} > \frac{n}{n+2}$ using obvious statements, the hypothesis of $n > 0$, and the laws of manipulating inequalities, so it must be true.

Notice how I have the same inequalities as the first proof, but they're written in the opposite order and I have added my reasoning between each step. The first proof just shows that the statement is true by leading us to the connection, but the proof above is an actual, rigorous, direct proof.