Disproving a statement by showing that its negation doesn't lead to a contradiction?

Question

Proof by contradiction (or the contradiction rule in logic) uses the first row of the following truth table to assert that if $¬p\Rightarrow{}\textbf{c}$ is true, then $p$ is true:

$p$	$¬p$	$\textbf{c}$	$¬p\Rightarrow{}\textbf{c}$	$(¬p\Rightarrow{}\textbf{c})\Rightarrow{}p$
T	F	F	T	T
F	T	F	F	T

(let $\textbf{c}$ and $\textbf{t}$ denote a contradiction and tautology respectively)

What I have not seen discussed anywhere is that the second row shows that when $¬p\Rightarrow{}\textbf{c}$ is false, $p$ is false. The potential validity of this argument is further hinted by the equivalence $(¬p\Rightarrow{}\textbf{c})\equiv(p\vee{}\textbf{c})\equiv{p}$, which means $(¬p\Rightarrow{}\textbf{c})\iff{p}$. Is it possible to use this argument form, that is, to show that $¬p\Rightarrow{}\textbf{c}$ is false and conclude that $p$ is false? (opposite of the proof by contradiction, which concludes $p$ is true.)

I feel that this argument form is not completely logical/practical, but I am not 100% why. My guess is that you would have to show $¬p$ does not lead to any contradictions, which is not practical as you would have to cover all (infinite) cases. Or you could show that $¬p$ leads to a tautology, but suddenly I'm not sure how any statement implies a tautology. Any help that would point me in the right direction is appreciated!

Answer 1

$$(¬p\Rightarrow{}\textbf{c})\equiv{p}$$

Also: $\quad(\lnot p{\kern.6em\not\kern-.6em\implies}\bot)\;\equiv\;(\lnot p\land\lnot \bot)\;\equiv\;(\lnot p\land\top)\;\equiv\;\lnot p.$

To conclude that $p$ is false,

is it possible to show that $(¬p\Rightarrow{}\textbf{c})$ is false?

This requires establishing that the antecedent $¬p$ is true (since a false antecedent automatically makes the implication true).

My guess is that you would have to show that $¬p$ does not lead to any contradictions

This also requires establishing that the antecedent $¬p$ is true (since a false antecedent can always lead to a contradiction).

But $¬p$ being true directly means that $p$ is false, without going through the above detours.

Or you could show that $¬p$ leads to a tautology

This does not entail that $p$ is false; for example: $¬(A\lor\lnot A)\implies\top.$

I feel that my argument is not completely logical

Summary: your proposal to disprove $p$ by showing that $\lnot p$ leads to no contradiction is not illogical—merely a circuitous way of disproving $p$ by proving $\lnot p.$

Answer 2

As a commenter has pointed out, $\lnot p$ is equivalent to $p \rightarrow \bot$. From this point of view, I would interpret "$\lnot p$ does not lead to a contradiction" as $\lnot (\lnot p \rightarrow \bot)$, which is simply $\lnot \lnot \lnot p$.

This form of triple negation can be simplified to a single negation, of course. The argument is similar to the other answer: if $\lnot \lnot \lnot p$, and we assume $p$, then in particular $\lnot \lnot p$, contradiction. Thus $\lnot p$.

This proof is valid even in intuitionistic logic, and it shows why it can be simplified to just assuming $p$ and finding a contradiction, which is one reason why this method of proof is not the most direct one.

---

But from your statement about "covering all (infinite cases)" I think you might have in mind a different interpretation of "$\lnot p$ does not lead to a contradiction". This could be interpreted as meaning

"$\lnot \lnot p$" is not provable (in a given system)

Or the (classically) equivalent

"$p$" is not provable

This does not necessarily imply that $\lnot p$ is provable. For example, in $ZF$ if you take $p$ to be the continuum hypothesis, then neither $p$ nor $\lnot p$ are provable.

If you want to arrive at this second version then you have to work outside the system, so while it's "impractical" it's the only way.