Negation introduction

Short description: Logical rule of inference

Negation introduction

Type	Rule of inference
Field	Propositional calculus
Statement	If a given antecedent implies both the consequent and its complement, then the antecedent is a contradiction.

Negation introduction is a rule of inference, or transformation rule, in the field of propositional calculus.

Negation introduction states that if a given antecedent implies both the consequent and its complement, then the antecedent is a contradiction.

Formal notation

This can be written as:

$((P\to Q)\wedge (P\to \mathrm{\neg }Q))\to \mathrm{\neg }P$

An example of its use would be an attempt to prove two contradictory statements from a single fact. For example, if a person were to state "Whenever I hear the phone ringing I am happy" and then state "Whenever I hear the phone ringing I am not happy", one can infer that the person never hears the phone ringing.

Many proofs by contradiction use negation introduction as reasoning scheme: to prove ¬P, assume for contradiction P, then derive from it two contradictory inferences Q and ¬Q. Since the latter contradiction renders P impossible, ¬P must hold.

Proof

With $\mathrm{\neg }P$ identified as $P\to \mathrm{\perp }$, the principle is as a special case of Frege's theorem, already in minimal logic.

Another derivation makes use of $A\to \mathrm{\neg }B$ as the curried, equivalent form of $\mathrm{\neg }(A\wedge B)$. Using this twice, the principle is seen equivalent to the negation of $(P\wedge (P\to Q))\wedge \mathrm{\neg }(P\wedge Q)$ which, via modus ponens and rules for conjunctions, is itself equivalent to the valid noncontradiction principle for $P\wedge Q$.

A classical derivation passing through the introduction of a disjunction may be given as follows:

Step	Proposition	Derivation
1	$(P\to Q)\wedge (P\to \mathrm{\neg }Q)$	Given
2	$(\mathrm{\neg }P\vee Q)\wedge (\mathrm{\neg }P\vee \mathrm{\neg }Q)$	Classical equivalence of the material implication
3	$\mathrm{\neg }P\vee (Q\wedge \mathrm{\neg }Q)$	Distributivity
4	$\mathrm{\neg }P\vee \mathrm{\perp }$	Law of noncontradiction for $Q$
5	$\mathrm{\neg }P$	Disjunctive syllogism (3,4)

See also

• Reductio ad absurdum