What is the proof for the reductio as an inferential step?

Question

(I was recommended by Philosophy Stack Exchange to present the following question on the Mathematics Stack Exchange)

In deductive logic, we may make the following step:

( {Γ,P}⊢Q & {Γ,P}⊢¬Q ) ⇒ {Γ}⊢¬P

I've been trying to find examples of a proof that this inference follows, but I've struggled with my search. If anyone could point me in the right direction, or show me the proof, it would be much appreciated.

I would be particularly interested in a proof that doesn't use a deduction theorem to prove that a reductio as a logically permissible inferential step.

Answer 1

You can prove this using the definition of logical consequence. That is, we have that $P$ is a logical consequence of $\Gamma$ if and only every truth-assignment that sets all statements in $\Gamma$ to true, also sets $P$ to true. We write this as $\Gamma \vDash P$.

So, assuming your proof system is sound:

$$\text{if } \Gamma \vdash P \text{ then } \Gamma \vDash P$$

and complete

$$\text{if } \Gamma \vDash P \text{ then } \Gamma \vdash P$$

this problem amounts to showing that:

$$\text{if } \Gamma, P \vDash Q \text{ and } \Gamma, P \vDash \neg Q \text{ then } \Gamma \vDash \neg P$$

which we can prove as follows:

Take any truth-assignment $h$ that sets all statements in $\Gamma$ to true. If $h$ sets $P$ to true, then given $\Gamma, P \vDash Q$, $h$ will set $Q$ to true. But given $\Gamma, P \vDash \neg Q$, $h$ will set $Q$ to false. That is a contradiction (a truth-assignment will assign exactly one value to any statement), and so $h$ cannot set $P$ to true. So, $h$ willl set $P$ to false, and hence $\neg P$ to true. Hence, we have $\Gamma \vDash \neg P$