Negation introduction
Negation introduction is a rule of inference, or transformation rule, in the field of propositional calculus.
≈ 2 min read
Names in other languages
No names in other languages are held for this entry yet.
Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.
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 this implies the negated antecedent.
Formal notation
This can be written as: \Big((P \rightarrow Q) \land (P \rightarrow \neg Q)\Big) \rightarrow \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 \neg P identified as P\to\bot , the principle is as a special case of Frege's theorem, already in minimal logic. Another derivation makes use of A\to \neg B as the curried, equivalent form of \neg (A \land B) . Using this twice, the principle is seen equivalent to the negation of \big(P\land(P\to Q)\big)\land \neg(P\and Q) which, via modus ponens and rules for conjunctions, is itself equivalent to the valid noncontradiction principle for P\and Q . A classical derivation passing through the introduction of a disjunction may be given as follows:
See also
Reductio ad absurdum
Text derived from https://en.wikipedia.org/w/index.php?oldid=1378035197 under CC BY-SA 4.0; modifications have been made.