(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.
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$