1
$\begingroup$

This question may have a duplicate but I didn't find one.

Given a proof by contradiction of a statement like $p \land q \implies r$. Which means (as i understand it):

$p \land q \land \lnot r$ is false.

(1) Is it right that for the proof to be valid one should verify p∧q is true?

ADDED: (2) Is it right that for the proof to be sound one should verify $p \land q$ doesn’t lead to a contradiction?

$\endgroup$
3
$\begingroup$

No, not necessarily. For a proof to be sound, then indeed, we need for $p\land q$ to be true.

But validity depends only on the form of an argument, not the semantic content of the argument. An argument or proof is valid provided the conclusion is logically implied by the premises. Indeed, we can have valid argument forms in which one or more premises is false.

If my apple is blue, then pigs can fly.

My apple is blue.

Therefore, pigs can fly.

This is a valid argument but it certainly is not sound: It is valid by modus ponens. All arguments of the form $$\begin{align} P \rightarrow Q \\ \\ P \\ \hline \\ \therefore Q\end{align}$$

are valid, just by virtue of the structure or form of the argument.

Of course, mathematical proofs usually only become interesting when they are sound: when the premises are true, and the conclusion(s) logically follow(s) from the premises. So indeed, we take great care to ensure that the premises are true, which would ensure us that the premises of an argument, by themselves, are not responsible for any contradiction reached when assuming the negation of the desired conclusion!

$\endgroup$
  • $\begingroup$ A sound argument/proof is one that is valid and one in which the premises are all true. A valid argument is one that is valid by virtue of the logical structure, and has nothing to do with the content of argument, only its form. $\endgroup$ – Namaste Dec 2 '13 at 16:41
  • $\begingroup$ Thanks! I understand the distinction in the terminology now. The question came to my head when I was writing a proof by contradiction for a statement. I thought: "how do i really know the contradiction implies what I think it implies? Maybe it implies that there's a contradiction in the assumptions". This complication doesn't occur when you simply prove it straightly. Of course there can still be a contradiction but the proof will still be sound. Am i right? $\endgroup$ – Saal Hardali Dec 2 '13 at 17:19
  • 1
    $\begingroup$ Yes, any contradiction reached would signal that the "assumption for the sake of contradiction" must be false, since in a sound argument, we have that the original premises are true. If one used strictly valid rules of inference, then, we establish exactly what we set out to establish: that the "assumption" must be false. See also my last paragraph. $\endgroup$ – Namaste Dec 2 '13 at 17:23
  • $\begingroup$ @amWhy: Nice feedback and all +1 $\endgroup$ – Amzoti Dec 3 '13 at 0:53
0
$\begingroup$

It is wrong. What you are describing in your last line, is the modus ponens, where from $A \to B$ and $A$ one deduces $B$. But the truth of $A$ has nothing to do with the truth of the implication $A \to B$, in fact this is completely true:

If $1$ is $0$, then $1$ is $1$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.