# How is proof by contradiction connected to propositional calculus?

$$\begin{array}{|c c|c|} P & \neg P & (\neg P \rightarrow \bot)\\ % Use & to separate the columns \hline % Put a horizontal line between the table header and the rest. \text{T} & \text{F} & \text{T}\\ \text{F} & \text{T} & \text{F}\\ \end{array}$$

In this truth table, we see that $$(\neg P \rightarrow \bot)$$ is equivalent to $$P$$. The line where $$\neg P$$ is $$\text{true}$$ is the last row and there $$(\neg P \rightarrow \bot)$$ is $$\text{false}$$.

In a proof by contradiction we assume that $$\neg P$$ is $$\text{true}$$ and show that this leads to a contradiction. Is this captured in the above truth table? How is the truth table connected to proof by contradiction?

The problem I have is that in a proof by contradiction we start by assuming $$\neg P$$ is $$\text{true}$$ and this leads to a contradiction. But I do not see how this is captured in the truth table?

EDIT: Alternatively we could l look at $$P\rightarrow Q$$ and we get the truth table:

$$\begin{array}{|c c|c|c|c|} P & Q & (P \rightarrow Q)&(P\wedge \neg Q)&(P\wedge \neg Q)\rightarrow \bot\\ % Use & to separate the columns \hline % Put a horizontal line between the table header and the rest. \text{T} & \text{T} & \text{T}&\text{F}&\text{T}\\ \text{T} & \text{F} & \text{F}&\text{T}&\text{F}\\ \text{F} & \text{T} & \text{T}&\text{F}&\text{T}\\ \text{F} & \text{F} & \text{T}&\text{F}&\text{T}\\ \end{array}$$

• Proof by contradiction is: "from $\lnot P \to \bot$ derive $P$". Commented Feb 27, 2023 at 13:22
• Commented Feb 27, 2023 at 13:24
• I always thought a proof by contradiction was trying to prove $P\to Q$ by giving a direct proof of $(P\land \lnot Q)\to \bot$. Commented Feb 27, 2023 at 13:29
• @Arthur I edited my post to add what you wrote. Commented Feb 27, 2023 at 13:55

$$\begin{array}{|c c|c|} P & \neg P & (\neg P \rightarrow \bot)\\ % Use & to separate the columns \hline % Put a horizontal line between the table header and the rest. T & F & T\\ F & T & F\\ \end{array}$$

In this truth table, we see that $$(\neg P \rightarrow \bot)$$ is equivalent to P.

The structure of a proof by contradiction is $$(\neg P \rightarrow \bot) \;\text{ logically implying }\;P$$ (no biconditional or equivalence is involved in this skeleton), which is captured by the fact that every row of your truth table with a '$$T$$' in column 3 also has a '$$T$$' in the column 1. The contradiction in column 3 is derived when we mathematically obtain two statements such that one is a negation of the other.

in a proof by contradiction we start by assuming $$\neg P$$ is true and this leads to a contradiction. But I do not see how this is captured in the truth table?

The truth table captures only the logic of proof by contradiction; the meat of the proof (the details of deriving the contradiction) relies on some language and axioms of mathematics that a truth table, being a propositional-logic tool, does not attempt to capture; for example, $$P$$ might stand for $$\forall x\;\big(\phi(x)\to\psi(x)\big).$$

EDIT corresponding to the OP's edit

$$P\rightarrow Q$$

$$\begin{array}{|c c|c|c|c|} P & Q & (P \rightarrow Q)&(P\wedge \neg Q)&(P\wedge \neg Q)\rightarrow \bot\\ % Use & to separate the columns \hline % Put a horizontal line between the table header and the rest. T & T & T&F&T\\ T & F & F&T&F\\ F & T & T&F&T\\ F & F & T&F&T\\ \end{array}$$

This truth table is merely a special case of the above: here, $$(P{\implies} Q)$$ is being proven by contradiction, by supposing $$P$$ and assuming $$\lnot Q;$$ its structure is captured by the fact that every row with a '$$T$$' in the 5th column also has a '$$T$$' in the 3rd column.

However, this special case does not fully represent the mathematics proof, unlike the above general case where $$P$$ can symbolise any mathematical statement. Here, $$P\to Q$$ symbolises merely the predicate (for example) $$\phi(x)\to\psi(x),$$ so there's an additional step (Universal Introduction, usually tacit, but where you might explicitly note that you are generalising the result for a representative/arbitrary variable $$a$$ to every variable $$x$$) to finally derive the intended mathematical statement (for example) $$\forall x\;\big(\phi(x)\to\psi(x)\big).$$