2
$\begingroup$

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?

$\endgroup$
3
  • 2
    $\begingroup$ It depends on how you manipulate $p \implies q$. If you start with $p \implies q$ and get to $p \implies p$, then that might not be a valid proof because you've shown $(p \implies q) \implies (p \implies p)$ which is not the same as $(p \implies p) \implies (p \implies q)$. However, if you use only logical equivalences to get from $p \implies q$ to $p \implies p$, then you've shown $(p \implies q) \iff (p \implies p)$ which proves that $p \implies q$ is true since it's logically equivalent to a true statement. $\endgroup$ Apr 17, 2016 at 12:10
  • $\begingroup$ @NobleMushtak Why not expand your comment into an answer, since it essentially answers OP's central question? $\endgroup$ Apr 17, 2016 at 12:25
  • $\begingroup$ @Travis I will, but it's going to take a while because I'm going to re-write the example proofs he gave. Hagen von Eitzen basically already re-wrote my comment. $\endgroup$ Apr 17, 2016 at 12:27

2 Answers 2

4
$\begingroup$

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

$\endgroup$
8
  • $\begingroup$ Also, this relates to the direct proof of the inequality because if you look at the proof, all of the steps are correct, but the proof is written backwards. It should've started with $2n > n$ and then ended up with $\frac{n}{n+1} > \frac{n}{n+2}$. $\endgroup$ Apr 17, 2016 at 12:20
  • $\begingroup$ @NobleMushtak Actually, the referenced proof of inequality is only an unrelated sequence of statements "$A_1$, $A_2$, $\ldots$, $A_n$" without any connectives. Had there been any (valid) connectives such as "$\iff$" or "which is equivalent to the following by multiplying both sides with the positive number $n+1$" or the like, it would have been a proof and not just a list of seemingly unrelated statements that do not differ structurally from "$\frac n{n+1}>\frac n{n+2}$, I love blueberry pie, $2n>n$" $\endgroup$ Apr 17, 2016 at 12:25
  • $\begingroup$ Well, if he had written the proof backwards and then written the reasoning behind all of his steps, his reasoning would've been correct. $\endgroup$ Apr 17, 2016 at 12:29
  • $\begingroup$ @NobleMushtak Indeed. "$A_1,A_2$" is much worse than "$A_2$ implies $A_1$", and the best would be "$A_2$ implies $A_1$ because ..." $\endgroup$ Apr 17, 2016 at 12:31
  • $\begingroup$ @HagenvonEitzen Okay so given $A_k \implies (A_i = A_j =A_n = A_k), $ would that constitute a proof? $\endgroup$ Apr 17, 2016 at 12:31
0
$\begingroup$

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.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .