In logic, proof by contradiction is a form of proof that establishes the truth or the validity of a proposition, by showing that assuming the proposition to be false leads to a contradiction.
Although it is quite freely used in mathematical proofs, not every school of mathematical thought accepts this kind of nonconstructive proof as universally valid.
More broadly, proof by contradiction is any form of argument that establishes a statement by arriving at a contradiction, even when the initial assumption is not the negation of the statement to be proved. In this general sense, proof by contradiction is also known as indirect proof, proof by assuming the opposite,and reductio ad impossibile.
A mathematical proof employing proof by contradiction usually proceeds as follows:
The proposition to be proved is P.
We assume P to be false, i.e., we assume ¬P.
It is then shown that ¬P implies falsehood. This is typically accomplished by deriving two mutually contradictory assertions, Q and ¬Q, and appealing to the law of noncontradiction.
Since assuming P to be false leads to a contradiction, it is concluded that P is in fact true.
An important special case is the existence proof by contradiction: in order to demonstrate that an object with a given property exists, we derive a contradiction from the assumption that all objects satisfy the negation of the property.
The principle may be formally expressed as the propositional formula ¬¬P ⇒ P, equivalently (¬P ⇒ ⊥) ⇒ P, which reads: "If assuming P to be false implies falsehood, then P is true."
In natural deduction the principle takes the form of the rule of inference
which reads: "If is proved, then may be concluded."
In sequent calculus the principle is expressed by the sequent
which reads: "Hypotheses and entail the conclusion or ."
In classical logic the principle may be justified by the examination of the truth table of the proposition ¬¬P ⇒ P, which demonstrates it to be a tautology:
Another way to justify the principle is to derive it from the Law of the excluded middle, as follows.
Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.
vignette| : un des plus vieux fragments des Éléments d'Euclide qui montre une démonstration mathématique. En mathématiques et en logique, une démonstration est un ensemble structuré d'étapes correctes de raisonnement. Dans une démonstration, chaque étape est soit un axiome (un fait acquis), soit l'application d'une règle qui permet d'affirmer qu'une proposition, la conclusion, est une conséquence logique d'une ou plusieurs autres propositions, les prémisses de la règle.
Un nombre irrationnel est un nombre réel qui n'est pas rationnel, c'est-à-dire qu'il ne peut pas s'écrire sous la forme d'une fraction a/b, où a et b sont deux entiers relatifs (avec b non nul). Les nombres irrationnels peuvent être caractérisés de manière équivalente comme étant les nombres réels dont le développement décimal n'est pas périodique ou dont le développement en fraction continue est infini. On distingue, parmi les nombres irrationnels, deux sous-ensembles complémentaires : les nombres algébriques non rationnels et les nombres transcendants.
In logic, proof by contradiction is a form of proof that establishes the truth or the validity of a proposition, by showing that assuming the proposition to be false leads to a contradiction. Although it is quite freely used in mathematical proofs, not every school of mathematical thought accepts this kind of nonconstructive proof as universally valid. More broadly, proof by contradiction is any form of argument that establishes a statement by arriving at a contradiction, even when the initial assumption is not the negation of the statement to be proved.
Singular cohomology is defined by dualizing the singular chain complex for spaces. We will study its basic properties, see how it acquires a multiplicative structure and becomes a graded commutative a
Discrete mathematics is a discipline with applications to almost all areas of study. It provides a set of indispensable tools to computer science in particular. This course reviews (familiar) topics a
We discuss a set of topics that are important for the understanding of modern data science but that are typically not taught in an introductory ML course. In particular we discuss fundamental ideas an
This research work analyses Theo van Doesburg's Counter-constructions presented in Paris in 1923 at the "L'Effort Moderne" exhibition. These Counter-constructions stand as icons of the Modern Movement
Every principal G-bundle over X is classified up to equivalence by a homotopy class X -> BG, where BG is the classifying space of G. On the other hand, for every nice topological space X Milnor constr
This thesis is devoted to the understanding of topological graphs. We consider the following four problems: 1. A \emph{simple topological graph} is a graph drawn in the plane so that its edges are rep
EPFL2016
Explore les formes harmoniques sur les surfaces de Riemann, couvrant l'unicité des solutions et l'identité bilinéaire de Riemann.
Couvre le rôle de chaîne de Theoreus pour les fonctions Lipschitz et ses applications pratiques.
Explore les espaces de Sobolev dans les dimensions supérieures, en discutant des dérivés, des propriétés et des défis avec continuité.