Namespaces
Variants
Actions

Difference between revisions of "Double negation, law of"

From Encyclopedia of Mathematics
Jump to: navigation, search
(Importing text file)
 
(Category:Special functions)
 
(One intermediate revision by one other user not shown)
Line 1: Line 1:
A logical principle according to which  "if it is untrue that A is untrue, A is true" . The law is also called the cancellation law of double negation. In a formalized logical language, the law is expressed as <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033910/d0339101.png" /> and usually appears in this form (or in the form of the corresponding [[Axiom scheme|axiom scheme]]) in the list of the logical axioms of a given formal theory. In traditional mathematics the law of double negation serves as the logical basis for the performance of so-called indirect proofs in consistent theories according to the following procedure: The assumption that the statement <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033910/d0339102.png" /> of a given mathematical theory is untrue leads to a contradiction in the theory; since the theory is consistent, this proves that  "not A"  is untrue, i.e. in accordance with the law of double negation, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033910/d0339103.png" /> is true. As a rule, the law of double negation is inapplicable in constructive considerations, which involve the requirement of algorithmic effectiveness of the foundations of mathematical statements. A typical example of such a case is any indirect proof of a statement <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033910/d0339104.png" /> of the form  "for any x there exists a y such that Bx, y is true" ; the last step, viz. the application of the law of double negation, cannot be carried out, since the constructive validity of the statement must entail the existence of an algorithm which, for any <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033910/d0339105.png" />, yields a construction of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033910/d0339106.png" /> such that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033910/d0339107.png" /> is true. However, an argument which involves the law of double negation does not lead to the construction of any algorithm, and no such algorithm may exist (see also [[Constructive selection principle|Constructive selection principle]]).
+
{{TEX|done}}
 +
A logical principle according to which  "if it is untrue that A is untrue, A is true" . The law is also called the cancellation law of double negation. In a formalized logical language, the law is expressed as $\neg\neg p\supset p$ and usually appears in this form (or in the form of the corresponding [[Axiom scheme|axiom scheme]]) in the list of the logical axioms of a given formal theory. In traditional mathematics the law of double negation serves as the logical basis for the performance of so-called indirect proofs in consistent theories according to the following procedure: The assumption that the statement $A$ of a given mathematical theory is untrue leads to a contradiction in the theory; since the theory is consistent, this proves that  "not A"  is untrue, i.e. in accordance with the law of double negation, $A$ is true. As a rule, the law of double negation is inapplicable in constructive considerations, which involve the requirement of algorithmic effectiveness of the foundations of mathematical statements. A typical example of such a case is any indirect proof of a statement $A$ of the form  "for any x there exists a y such that Bx, y is true" ; the last step, viz. the application of the law of double negation, cannot be carried out, since the constructive validity of the statement must entail the existence of an algorithm which, for any $x$, yields a construction of $y$ such that $B(x,y)$ is true. However, an argument which involves the law of double negation does not lead to the construction of any algorithm, and no such algorithm may exist (see also [[Constructive selection principle|Constructive selection principle]]).
  
 
The law of double negation is closely connected with the [[Law of the excluded middle|law of the excluded middle]] and is, in a certain sense, equivalent to it. Thus, in the intuitionistic propositional calculus, each of these two laws is deducible from the other.
 
The law of double negation is closely connected with the [[Law of the excluded middle|law of the excluded middle]] and is, in a certain sense, equivalent to it. Thus, in the intuitionistic propositional calculus, each of these two laws is deducible from the other.
Line 10: Line 11:
 
====Comments====
 
====Comments====
 
Indirect proofs are also called proofs by contradiction or proofs by reductio ad absurdum (cf. also [[Reductio ad absurdum|Reductio ad absurdum]]).
 
Indirect proofs are also called proofs by contradiction or proofs by reductio ad absurdum (cf. also [[Reductio ad absurdum|Reductio ad absurdum]]).
 +
 +
[[Category:Special functions]]

Latest revision as of 21:07, 1 November 2014

A logical principle according to which "if it is untrue that A is untrue, A is true" . The law is also called the cancellation law of double negation. In a formalized logical language, the law is expressed as $\neg\neg p\supset p$ and usually appears in this form (or in the form of the corresponding axiom scheme) in the list of the logical axioms of a given formal theory. In traditional mathematics the law of double negation serves as the logical basis for the performance of so-called indirect proofs in consistent theories according to the following procedure: The assumption that the statement $A$ of a given mathematical theory is untrue leads to a contradiction in the theory; since the theory is consistent, this proves that "not A" is untrue, i.e. in accordance with the law of double negation, $A$ is true. As a rule, the law of double negation is inapplicable in constructive considerations, which involve the requirement of algorithmic effectiveness of the foundations of mathematical statements. A typical example of such a case is any indirect proof of a statement $A$ of the form "for any x there exists a y such that Bx, y is true" ; the last step, viz. the application of the law of double negation, cannot be carried out, since the constructive validity of the statement must entail the existence of an algorithm which, for any $x$, yields a construction of $y$ such that $B(x,y)$ is true. However, an argument which involves the law of double negation does not lead to the construction of any algorithm, and no such algorithm may exist (see also Constructive selection principle).

The law of double negation is closely connected with the law of the excluded middle and is, in a certain sense, equivalent to it. Thus, in the intuitionistic propositional calculus, each of these two laws is deducible from the other.

References

[1] S.C. Kleene, "Introduction to metamathematics" , North-Holland (1951)


Comments

Indirect proofs are also called proofs by contradiction or proofs by reductio ad absurdum (cf. also Reductio ad absurdum).

How to Cite This Entry:
Double negation, law of. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Double_negation,_law_of&oldid=18636
This article was adapted from an original article by F.A. Kabakov (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article