Negation introduction

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

Uses your system voice; voice and rate in settings.

Snapshot

≈ 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.

Sources cited in this revision

1 named source(s) extracted from the cited revision. A source with no author is shown by its publication; nothing is invented.