Mathematical proofs | Methods of proof | Theorems in propositional logic

Proof by contradiction

In logic and mathematics, 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. Proof by contradiction is also known as indirect proof, proof by assuming the opposite, and reductio ad impossibile. It is an example of the weaker logical refutation reductio ad absurdum. A mathematical proof employing proof by contradiction usually proceeds as follows: 1. * The proposition to be proved is P. 2. * We assume P to be false, i.e., we assume ¬P. 3. * 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. 4. * 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 the existence of an object satisfying a given property, we assume that no such object exists and derive 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. (Wikipedia).

Video thumbnail

Introduction to Proof by Contradiction: sqrt(2) is irrational

This video introduces the mathematical proof method of proof by contradiction and provides an example of a proof. mathispower4u.com

From playlist Symbolic Logic and Proofs (Discrete Math)

Video thumbnail

Writing Proofs | Proof by Contradiction Example 2

We prove a statement using the method of proof by contradiction.

From playlist Abstract Algebra

Video thumbnail

Proof by Contradiction: There are no integers x and y such that x^2 = 4y + 2

This video provides an example of proof by contradiction. mathispower4u.com

From playlist Symbolic Logic and Proofs (Discrete Math)

Video thumbnail

Proof by Contradiction: There are infinitely many primes

This video provides an example of proof by contradiction. mathispower4u.com

From playlist Symbolic Logic and Proofs (Discrete Math)

Video thumbnail

Proofs by contradiction -- Proofs

This lecture is on Introduction to Higher Mathematics (Proofs). For more see http://calculus123.com.

From playlist Proofs

Video thumbnail

Proof by Contradiction | Explanation + 5 Examples

In this video, I explain the basic idea of the proof by contradiction method. Then I show 5 examples of using proof by contradiction to prove some propositions. Thanks for watching! Comment below with questions, and make sure to keep flexin' those brain muscles! Facebook: https://www.f

From playlist Proofs

Video thumbnail

13. Ch. 4, Sections 4.8 & 4.9. Introduction to Logic, Philosophy 10, UC San Diego - BSLIF

Video lecture corresponding to _Basic Sentential Logic and Informal Fallacies_, Chapter 4, Sections 4.8 & 4.9. This is for the class Introduction to Logic, Philosophy 10, UC San Diego.

From playlist UC San Diego: PHIL 10 - Introduction to Logic | CosmoLearning.org Philosophy

Video thumbnail

Topology Without Tears - Video 4c - Writing Proofs in Mathematics

This is part (c) of the fourth video in a series of videos which supplement my online book "Topology Without Tears" which is available free of charge at www.topologywithouttears.net Video 4 focusses on the extremely important topic of writing proofs. This video is about Proof by Contradict

From playlist Topology Without Tears

Video thumbnail

Natural Deductive Logic: DERIVABLE RULES (MT, HS, DS, DeM)

In this video on #Logic we do the proofs for modus tollens (MT), hypothetical syllogism (HS), disjunctive syllogism (DS) and one of the DeMorgan's Laws (DeM) so that we can use them as shortcuts in further proofs. 0:00 [Modus Tollens (MT)] 1:23 [Hypothetical Syllogism (HS)] 3:25 [Disjunct

From playlist Logic in Philosophy and Mathematics

Video thumbnail

proof by contradiction and more -- Proof Writing 11

⭐Support the channel⭐ Patreon: https://www.patreon.com/michaelpennmath Merch: https://teespring.com/stores/michael-penn-math My amazon shop: https://www.amazon.com/shop/michaelpenn 🟢 Discord: https://discord.gg/Ta6PTGtKBm ⭐my other channels⭐ Main Channel: https://www.youtube.

From playlist Proof Writing

Video thumbnail

How not to Use Proof by Contradiction

Sometimes a proof is actually simpler than we might think... Animated using Manim. Intro: 00:00 Largest counting number: 00:30 Infinite primes: 02:32 Cantor's diagonal argument: 07:25 Conclusions: 11:09

From playlist Summer of Math Exposition 2 videos

Video thumbnail

Four Exercises in Natural Deductive Proofs: DERIVABLE RULES (DeM, Contra, Impl)

In this video on #Logic we do the proofs the DeMorgan's Laws (DeM), Contrapositive Law (Contra), and Implication (Impl) so that we can use them as shortcuts in further proofs. 0:00 [Intro] 0:37 [DeMorgan's #3 (DeM)] 4:10 [DeMorgan's #4 (DeM) - TOUGH] 11:32 [Contraposition (Contra)] 13:11

From playlist Logic in Philosophy and Mathematics

Video thumbnail

Proof by Counter Example: Prove a Converse is False

This video provides an example of a proof by counter example. mathispower4u.com

From playlist Symbolic Logic and Proofs (Discrete Math)

Video thumbnail

Proof: The Square Root of 2 is Irrational

This is one of the first proofs I did in my intro to proofs class. It's very beginner friendly, and it's a great example of how powerful the proof by contradiction technique is. Enjoy :) Facebook: https://www.facebook.com/braingainzofficial Instagram: https://www.instagram.com/braingai

From playlist Proofs

Video thumbnail

Natural Deductive Proofs: THEOREMS - Logic

In this video on #Logic, we learn what theorems are in natural deductive proofs and prove four of them. 0:00 [What are theorems?] 0:59 [Proof #1: If P then P] 2:38 [Proof #2: P and not P] 4:33 [Proof #3: if P then not not P] 6:38 [Proof #4: P or not P] 9:27 [Theorem Introduction] If you

From playlist Logic in Philosophy and Mathematics

Video thumbnail

Proof by Contradiction | Method & First Example

Proof by Contradiction is one of the most important proof methods. It is an indirect proof technique that works like this: You want to show a statement P is true. First assume the P is actually false. Then manipulate until you get a contradiction like 0=1. This means your assumption that P

From playlist Discrete Math (Full Course: Sets, Logic, Proofs, Probability, Graph Theory, etc)

Video thumbnail

BM3. Formal Proofs

Basic Methods: We define theorems and describe how to formally construct a proof. We note further rules of inference and show how the logical equivalence of reductio ad absurdum allows proof by contradiction.

From playlist Math Major Basics

Related pages

Natural deduction | Zero of a function | G. H. Hardy | Reductio ad absurdum | Tautology (logic) | Principle of explosion | Proof by infinite descent | Hilbert's Nullstellensatz | Polynomial | Square root of 2 | Modus tollens | David Hilbert | Mathematical proof | Propositional formula | Proof by exhaustion | Sequent calculus | Brouwer–Heyting–Kolmogorov interpretation | Contradiction | Euclid's Elements | Mathematics | Truth table | Proposition | Turing machine | Halting problem | Validity (logic) | Complex number | Intuitionistic logic | Q.E.D. | Rule of inference | Law of noncontradiction | Law of excluded middle | Russell's paradox | Classical logic | Euclid's theorem | Algorithm | Philosophy of mathematics