**Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?**

Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur GraphSearch.

Concept# Proof by contradiction

Résumé

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.

Source officielle

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.

MOOCs associés (22)

Concepts associés (33)

Cours associés (147)

Publications associées (3)

Algèbre Linéaire (Partie 1)

Un MOOC francophone d'algèbre linéaire accessible à tous, enseigné de manière rigoureuse et ne nécessitant aucun prérequis.

Algèbre Linéaire (Partie 1)

Un MOOC francophone d'algèbre linéaire accessible à tous, enseigné de manière rigoureuse et ne nécessitant aucun prérequis.

Algèbre Linéaire (Partie 2)

Un MOOC francophone d'algèbre linéaire accessible à tous, enseigné de manière rigoureuse et ne nécessitant aucun prérequis.

Démonstration (logique et mathématiques)

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.

Proof by contradiction

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.

Nombre irrationnel

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.

CS-101: Advanced information, computation, communication I

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

COM-406: Foundations of Data Science

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

MATH-432: Probability theory

The course is based on Durrett's text book
Probability: Theory and Examples.

It takes the measure theory approach to probability theory, wherein expectations are simply abstract integrals.

It takes the measure theory approach to probability theory, wherein expectations are simply abstract integrals.

Séances de cours associées (1 000)

Formes harmoniques et surfaces de RiemannMATH-680: Monstrous moonshine

Explore les formes harmoniques sur les surfaces de Riemann, couvrant l'unicité des solutions et l'identité bilinéaire de Riemann.

Rôle de la chaîne: Lipschitz SitMATH-502: Distribution and interpolation spaces

Couvre le rôle de chaîne de Theoreus pour les fonctions Lipschitz et ses applications pratiques.

Formes harmoniques : théorème principalMATH-410: Riemann surfaces

Explore les formes harmoniques sur les surfaces de Riemann et l'unicité des solutions aux équations harmoniques.

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 constructed a strict model of its loop space (Omega) over tildeX, that is a group. Moreover, the morphisms of topological groups (Omega) over tildeX -> G generate all the G-bundles over X up to equivalence. In this paper, we show that the relation between Milnor's loop space and the classifying space functor is, in a precise sense, an adjoint pair between based spaces and topological groups in a homotopical context. This proof leads to a classification of principal bundles over a fixed space, that is dual to the classification of bundles with a fixed group. Such a result clarifies the deep relation that exists between the theory of bundles, the classifying space construction and the loop space, which are very important in topological K-theory, group cohomology, and homotopy theory.

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 due to their role as precursors of a new "boundless" spatiality, a role first intuitively perceived by Le Corbusier or Mies van der Rohe and then theorized by Sigfried Giedion. We have attempted in this research a theoretical study of the Counter-constructions' position within the architectural field. That is to say bringing together their aspect of "spatial manifest" and the Dadaist persona of Theo van Doesburg; this alleged contradiction between the progressive and negative dimension of the Counter-constructions being the subject of this research. It is based on the following problematic: understanding what is at stake in the disjointing of the polychrome plane (as a textile surface) and the suppression of the architectural boundary under the guise of spatial continuity ("the breaking of the enclosure" mentioned by Theo van Doesburg and his interest in the notion of mathematical continuum through the theories of the fourth dimension: Henri Poincaré's Analysis situs). That amounts to studying the modalities connecting the notions of dressing and of continuum to a destructive drive, "throwing out" the inside of the house. The methodology turns towards psychoanalysis through the concepts of Verneinung [negation] (Freud) and Moi-peau [Skin-ego] (Anzieu).

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 represented by continuous arcs with the property that any two of them meet at most once, at endpoint or at a crossing. Let $G$ be a complete simple topological graph on $n$ vertices. The three edges induced by any triplet of vertices in $G$ form a simple closed curve. If this curve contains no vertex in its interior (exterior), then we say that the triplet forms an \emph{empty triangle}. In 1998, Harborth proved that $G$ has at least 2 empty triangles, and he conjectured that the number of empty triangles is at least $2n/3$. We settle Harborth's conjecture in the affirmative. 2. A \emph{monotone cylindrical} graph is a topological graph drawn on an open cylinder with an infinite vertical axis satisfying the condition that every vertical line intersects every edge at most once. It is called \emph{simple} if any pair of its edges have at most one point in common: an endpoint or a point at which they properly cross. We say that two edges are \emph{disjoint} if they do not intersect. We show that every simple complete monotone cylindrical graph on $n$ vertices contains $\Omega(n^{1-\epsilon})$ pairwise disjoint edges for any $\epsilon>0$. As a consequence, we show that every simple complete topological graph (drawn in the plane) with $n$ vertices contains $\Omega(n^{\frac 12-\epsilon})$ pairwise disjoint edges for any $\epsilon>0$. By extending some of the ideas here we are then able to get rid of the $\epsilon$ term in the exponent, showing that in fact we can always guarantee a set with $\Omega(n^{\frac 12})$ pairwise disjoint edges. This improves the previous lower bound of $\Omega(n^\frac 13)$ by Suk and independently by Fulek. We remark that our proof implies a polynomial time algorithm for finding this set of pairwise disjoint edges. 3. A {\em tangle} is a graph drawn in the plane such that its edges are represented by continuous arcs, and any two edges share precisely one point, which is either a common endpoint or an interior point at which the two edges are tangent to each other. These points of tangencies are assumed to be distinct. If we drop the last assumption, that is, more than two edges may touch one another at the same point, then the drawing is called a {\em degenerate tangle}. We settle a problem of Pach, Radoi\v ci'c, and T'oth \cite{TTpaper}, by showing that every degenerate tangle has at most as many edges as vertices. We also give a complete characterization of tangles. 4. We show that for a constant $t\in \NN$, every simple topological graph on $n$ vertices has $O(n)$ edges if the graph has no two sets of $t$ edges each such that every edge in one set is disjoint from all edges of the other set (i.e., the complement of the intersection graph of the edges is $K_{t,t}$-free). As an application, we settle the \emph{tangled-thrackle} conjecture formulated by Pach, Radoi\v{c}i'c, and T'oth: Every $n$-vertex graph drawn in the plane such that every pair of edges have precisely one point in common, where this point is either a common endpoint, a crossing, or a point of tangency, has at most $O(n)$ edges.