Methods of Logical Reasoning
Two principal methods of mathematical proof — reductio ad absurdum and induction — together with the elementary theory of finite cardinality and counting.
Start Learning
Learning Objectives
On completing this unit, the student will be able to:
- Reconstruct the logical schema of a proof by contradiction in terms of negation, implication, and the principle of non-contradiction.
- Construct and critique proofs by reductio ad absurdum, including classical examples such as the irrationality of √2 and the infinitude of primes.
- State the principle of mathematical induction and explain why it is sound.
- Construct proofs by induction, formulating the base case and the inductive hypothesis explicitly and using the hypothesis correctly in the inductive step.
- Define the cardinality of a finite set and compute the cardinality of unions, intersections, differences, and complements.
- State and apply the inclusion–exclusion principle for two and three sets.
- Apply the sum rule and the product rule to count the number of outcomes in finite combinatorial situations.
About This Course Unit
The final unit of the course turns from the language of mathematics to its method. We study two general schemes of proof. Reductio ad absurdum exploits the apparatus of negation and implication: to prove a proposition, assume its negation and derive a contradiction. Mathematical induction, tailored to universal claims about the natural numbers, rests on a single foundational principle and proceeds in two steps — base case and inductive step. As a first substantial application of the formalism developed in earlier units, the unit then studies the cardinality of finite sets, deriving the inclusion–exclusion principle from the set operations introduced in Unit 2. The course concludes with the sum and product rules, the elementary counting principles that underlie all later work in combinatorics.