Introduction to Proofs
A first course in reading and writing mathematical proofs: what a proof is and why mathematicians prove things, propositional logic and truth tables, quantifiers and their negation, direct proof, proof by contrapositive and by contradiction including the irrationality of the square root of 2 and the infinitude of the primes, proof by cases and counterexamples, mathematical induction, strong induction and the well-ordering principle with prime factorization and the division algorithm, sets and set operations, injective, surjective and bijective functions with composition and inverses, relations, equivalence relations and partitions, and a capstone on cardinality, countability and Cantor's diagonal argument, with runnable Python examples throughout.
MATH-228 Year 2 3 credits 12 lessons · 4 h 41 min ▶ Video lessons coming soon
Offered by HSM University · Mathematics & Statistics
What you'll learn
- Explain what a mathematical proof is, distinguish definitions, axioms, theorems, lemmas, corollaries and conjectures, and recognize why checking examples is not a proof.
- Translate statements between English and propositional logic, build truth tables, and use logical equivalences such as De Morgan's laws and the contrapositive to simplify and rewrite statements.
- Read, write and negate statements with nested universal and existential quantifiers, and explain why the order of quantifiers matters.
- Write clear direct proofs of statements about integers, divisibility, parity and inequalities, starting from definitions and using correct mathematical prose.
- Prove statements by contrapositive and by contradiction, including the irrationality of the square root of 2 and the infinitude of the primes, and choose the right method for a given statement.
- Organize proofs by exhaustive cases, use the absolute value and remainders as case splits, and disprove universal statements with well-chosen counterexamples.
- Prove formulas, inequalities and divisibility results by mathematical induction, identifying the base case, inductive hypothesis and inductive step precisely.
- Use strong induction and the well-ordering principle to prove existence of prime factorizations, the division algorithm and results about recursively defined sequences.
- Work with sets, subsets, power sets and Cartesian products, prove set equalities by double inclusion, and apply set identities including De Morgan's laws for sets.
- Prove that functions are injective, surjective or bijective, compose functions, construct inverses, and work with images and preimages of sets.
- Determine whether a relation is reflexive, symmetric, antisymmetric or transitive, prove that a relation is an equivalence relation, and pass between equivalence relations and partitions.
- Compare the cardinalities of sets using bijections, prove that the integers and rationals are countable, and use Cantor's diagonal argument to prove that the real numbers and power sets are uncountable.
Course content
12 lessons · 4 h 41 min total · final exam
- 1 What a proof is and why mathematicians prove things 23 min · quiz
- 2 Propositional logic and truth tables 23 min · quiz
- 3 Quantifiers and negation 25 min · quiz
- 4 Direct proof 21 min · quiz
- 5 Proof by contrapositive and contradiction 24 min · quiz
- 6 Proof by cases and counterexamples 23 min · quiz
- 7 Mathematical induction 20 min · quiz
- 8 Strong induction and well-ordering 21 min · quiz
- 9 Sets and set operations 24 min · quiz
- 10 Functions: injective, surjective and bijective 25 min · quiz
- 11 Relations, equivalence relations and partitions 25 min · quiz
- 12 Capstone: cardinality, countability and Cantor's diagonal argument 27 min · quiz
- E Final exam 20 questions
Requirements
Recommended background. You can start any course at any time.
Description
A first course in reading and writing mathematical proofs: what a proof is and why mathematicians prove things, propositional logic and truth tables, quantifiers and their negation, direct proof, proof by contrapositive and by contradiction including the irrationality of the square root of 2 and the infinitude of the primes, proof by cases and counterexamples, mathematical induction, strong induction and the well-ordering principle with prime factorization and the division algorithm, sets and set operations, injective, surjective and bijective functions with composition and inverses, relations, equivalence relations and partitions, and a capstone on cardinality, countability and Cantor's diagonal argument, with runnable Python examples throughout.
Part of the Science stream, typically taken in year 2.