Math 2.0

General and overarching topics Concept

Proof by contradiction

Builds on Mathematical proofNegationDouble negation law

Summary

A proof by contradiction proves a proposition pp in two steps. It assumes ¬p\neg p, and it gets a contradiction from this assumption, that is, a statement qq together with ¬q\neg q. Then ¬p\neg p is false, so pp is true by the double negation law.

Remarks

Another name is reductio ad absurdum. A classical example: 2\sqrt{2} is irrational. Assume 2=a/b\sqrt{2} = a/b in lowest terms. Then aa and bb are both even, which is a contradiction. The last step uses classical logic. A proof of ¬p\neg p from a contradiction with pp is valid also in intuitionistic logic.

Reading path

To understand this page from the ground up, read these 14 pages in order. The foundations come first.

Show the path as a graph
Proposition, concept, no evidence levelPropositionconceptConjunction, definition, no evidence levelConjunctiondefinitionDisjunction, definition, no evidence levelDisjunctiondefinitionImplication, definition, no evidence levelImplicationdefinitionNegation, definition, no evidence levelNegationdefinitionBiconditional, definition, no evidence levelBiconditionaldefinitionTruth table, concept, no evidence levelTruth tableconceptModus ponens, concept, no evidence levelModus ponensconceptPropositional logic, concept, no evidence levelPropositional logicconceptMathematical proof, concept, no evidence levelMathematical proofconceptTautology, definition, no evidence levelTautologydefinitionLogical equivalence, definition, no evidence levelLogical equivalencedefinitionDouble negation law, statement, no evidence levelDouble negation lawstatementProof by contradiction, concept, no evidence levelProof by contradictionconcept
Each page uses the pages above it. The colour of the bar on a box shows how strong the evidence is, and the box also gives it as text. The list has the same pages.
  • no evidence level
  1. Proposition concept
  2. Conjunction definition
  3. Disjunction definition
  4. Implication definition
  5. Negation definition
  6. Biconditional definition
  7. Truth table concept
  8. Modus ponens concept
  9. Propositional logic concept
  10. Mathematical proof concept
  11. Tautology definition
  12. Logical equivalence definition
  13. Double negation law statement
  14. Proof by contradiction concept

Where this leads

28 pages build on this one.

Further reading

  1. Web https://en.wikipedia.org/wiki/Reductio_ad_absurdum, lead section
About this page
Tag0J0XBKG64S
URIm2://0J0XBKG64S
Aliasesreductio-ad-absurdum, indirect-proof
Kindconcept
WritingW1 stated
MSC00A35
SpecializesMathematical proof
Part ofProof methods
UsesMathematical proof, Negation, Double negation law
Same as

Markdown · JSON · Edit on GitHub

What this page needs for W2

  • edge defines in: at least one definition (0 of 1)
  • edge instance_of in: at least two examples (0 of 2)
  • edge not_instance_of in: at least one non-example (0 of 1)

The writing levels say how complete the text of a page is. They do not measure its truth.

What links here

Used by