ConceptMathematics
Proof by contradiction
A proof technique where one assumes the negation of the statement to be proven and derives a logical contradiction.
Know first
Named as a prerequisite by the lectures that define this. The number is how many say so. A grey one has no page yet.
Opens up
Concepts that name this one as a prerequisite.
Lecturers
11Each in their own terms, from the easiest level.
Vicky Neale
A proof technique that assumes the negation of a statement and shows that this assumption leads to a logical contradiction.Emily Riehl
A proof strategy where you assume the opposite of what you want to show, find a contradiction, and conclude the original statement must be true.Bernhard Boser & Gireeja Ranade
A proof strategy where you assume the negation of what you want to prove to show it leads to a contradiction.Casey Rodriguez
A proof technique where one assumes the negation of the statement to be proven and derives a false statement to show the assumption is impossible.Francis Su
A proof technique where one assumes the negation of the statement to be proven and derives a contradiction.Tom Leighton
An indirect proof method where one assumes the opposite of what is to be proved and derives a falsehood or contradiction.Ankur Moitra
A proof technique where we assume the negation of what we want to prove and derive a contradiction.Michael Sipser
A proof technique where you assume the opposite of what you want to prove and show that this assumption leads to a logical impossibility.Brian Yu
A technique of proving a statement by assuming its negation and showing that it leads to a contradiction.Marten van Dijk
A proof technique where we assume the negation of the statement to be proved and show that it leads to a contradiction, thereby proving the original statement.Alan Guth
A logical technique where one assumes the negation of a statement and shows that it leads to a logical impossibility.
Lectures that assume it
9- Cantor Diagonalization and Metric Spaces
- Series
- Undecidability
- Countable and Uncountable Sets
- Storage Allocation and Garbage Collection
- Structure and Randomness in the Prime Numbers
- Time Complexity and Universal Turing Machines
- Fermat's Last Theorem: Abelian and Non-Abelian Approaches
- Synchronous Distributed Algorithms: Symmetry-Breaking and Shortest-Paths Spanning Trees
Connections
42The lectures that define it or assume it, and the concepts next to it.
Concepts9
- Logical implication
- Contradiction
- Negation
- Logical negation
- Cantor's diagonal argument
- Cantor's diagonalization argument
Show 3 moreShow fewer
Lectures33
- Constructing Statements and Proofs
- Sets, Set Operations and Mathematical Induction
- Mathematical Induction
- Matching Problems
- Harvard CS50’s Artificial Intelligence with Python – Full University Course
- Natural Numbers and Induction
Show 27 moreShow fewer
- The Characterization of the Real Numbers
- The Squeeze Theorem and Operations Involving Convergent Sequences
- Properties of Q
- Principle of Induction
- Compactness and the Heine-Borel Theorem
- Huffman Coding
- A Solution to the Stable Marriage Problem
- Regular Pumping Lemma, Conversion of FA to Regular Expressions
- CF Pumping Lemma, Turing Machines
- Binary Relations, Partitions & Equivalence Relations
- Operational Amplifiers and Negative Feedback
- Graph Theory III
- Introduction to Circuit Elements and KCL/KVL
- Pigeonhole Principle
- Functions, Injections, Surjections, Bijections & Inverses
- Introduction to Non-Euclidean Spaces
- Linear Independence, Span, and Null Spaces
- Nodal Analysis and Resistive Networks
- Cantor Diagonalization and Metric Spaces
- Series
- Undecidability
- Countable and Uncountable Sets
- Storage Allocation and Garbage Collection
- Structure and Randomness in the Prime Numbers
- Time Complexity and Universal Turing Machines
- Fermat's Last Theorem: Abelian and Non-Abelian Approaches
- Synchronous Distributed Algorithms: Symmetry-Breaking and Shortest-Paths Spanning Trees