 How It Works
Courses
FAQ
JOIN BETA

# Methods of Proof

This course is currently under construction. The target release date for this course is October.
Build fluency with sets and logic, the most fundamental structures and operations in mathematics. Learn what a proof is and master a variety of techniques for proving mathematical statements.

## Content

### Sets and Relations

• Construct sets using set-builder notation and demonstrate fluency with set operations and terminology.
• Identify surjective, injective, and bijective functions.
• Compute the cardinality of a set and determine whether an infinite set is countable.
• Identify equivalence relations and reason about equivalence classes.

### Modular Arithmetic

• Define modular congruence in terms of equivalence classes.
• Perform arithmetic operations on residue classes.
• Use the extended euclidean algorithm to compute modular inverses and solve linear diophantine equations.

### Logic

• Translate between verbal and symbolic forms of mathematical statements.
• Determine whether two statements are equivalent by constructing and comparing truth tables.
• Understand that the contrapositive of a statement is logically equivalent to the original statement.
• Apply rules of logical inference including distribution, absorption, and De Morgan’s laws.
• Translate between logical operations and set operations.
• Understand the difference between necessary and sufficient conditions.
• Translate between formal and informal language using quantifiers.

### Proofs

• Construct direct proofs of statements involving numbers, sets, logical operations, relations, and functions.
• Disprove false statements by finding counterexamples.
• Prove statements using induction, including strong induction.
• Leverage indirect proof techniques, including proof by contradiction and proof by contrapositive, to reformulate a proof statement in a way that is easier to prove.
1.
Preliminaries
5 topics
1.1. Divisibility of Integers
 1.1.1. The Division Algorithm 1.1.2. The Euclidean Algorithm 1.1.3. The Extended Euclidean Algorithm 1.1.4. Properties of Divisibility 1.1.5. Linear Diophantine Equations
2.
Sets
19 topics
2.2. Sets
 2.2.1. Introduction to Sets 2.2.2. Special Sets 2.2.3. Set-Builder Notation 2.2.4. Equivalent Sets 2.2.5. Cardinality of Sets 2.2.6. Subsets 2.2.7. Power Sets
2.3. Set Operations
 2.3.1. The Complement of a Set 2.3.2. The Union of Sets 2.3.3. The Intersection of Sets 2.3.4. The Difference of Sets 2.3.5. De Morgan's Laws for Sets 2.3.6. The Cartesian Product 2.3.7. Properties of Union, Intersection, and Direct Product 2.3.8. Disjoint Sets 2.3.9. Partitions of Sets 2.3.10. Indexed Sets 2.3.11. Indicator Functions 2.3.12. Translating Between Logical Operations and Set Operations
3.
Logic
27 topics
3.4. Compound Statements
 3.4.1. Mathematical Statements 3.4.2. The "And" and "Or" Connectives 3.4.3. The "Not" Connective 3.4.4. Logical Equivalence 3.4.5. Associative and Commutative Laws 3.4.6. Distributing Conjunctions and Disjunctions 3.4.7. The Absorption Laws 3.4.8. De Morgan's Laws for Logic
3.5. Implications
 3.5.1. Conditional Statements 3.5.2. Logical Equivalence with Conditional Statements 3.5.3. Converse, Inverse, and Contrapositive 3.5.4. Biconditional Statements 3.5.5. Tautologies and Contradictions
3.6. Predicates and Quantifiers
 3.6.1. Predicates 3.6.2. The "And" and "Or" Connectives With Predicates 3.6.3. The "Not" Connective With Predicates 3.6.4. Simplifying Expressions With Predicates Using De Morgan's Laws 3.6.5. Conditional and Biconditional Statements With Predicates 3.6.6. Universal and Existential Quantifiers 3.6.7. Negating Universal and Existential Statements 3.6.8. Nested Quantifiers 3.6.9. Formal and Informal Language 3.6.10. Negating Statements With Nested Quantifiers 3.6.11. Necessary and Sufficient Conditions
3.7. Logical Inference
 3.7.1. Implication Elimination and Denying the Consequent 3.7.2. Disjunctive Syllogism and Hypothetical Syllogism 3.7.3. Additional Rules of Logical Inference
4.
Functions
16 topics
4.8. Surjections, Injections and Bijections
 4.8.1. Sets and Functions 4.8.2. Surjections 4.8.3. Injections 4.8.4. Bijections 4.8.5. Into Functions
4.9. Sequences
 4.9.1. The Limit of a Null Sequence 4.9.2. Proving That a Sequence Converges to Zero 4.9.3. The Limit of a Sequence 4.9.4. Infinite Limits of Sequences
4.10. Functions
 4.10.1. Proving Statements Involving Surjections 4.10.2. Proving Statements Involving Injections 4.10.3. Proving Statements Involving Bijections 4.10.4. Proving Statements Involving Function Composition 4.10.5. Proving Statements Involving Inverse Functions 4.10.6. Proving Statements Involving Operations on Sets 4.10.7. Composition of Surjections is Surjection
5.
Direct Proof
33 topics
5.11. Direct Proofs
 5.11.1. Introduction to Direct Proofs 5.11.2. Direct Proofs of Parity 5.11.3. Sum of Even Integer and Odd Integer is Odd 5.11.4. Direct Proofs of Divisibility 5.11.5. Direct Proofs of Prime Properties 5.11.6. Direct Proofs of Real Number Statements 5.11.7. Direct Proofs of Modular Congruence 5.11.8. Direct Proofs of Inequalities 5.11.9. Direct Proofs of Set Equalities 5.11.10. Direct Proofs Involving Set Complements and Differences 5.11.11. Direct Proofs Involving Cartesian Products 5.11.12. Proving De Morgan's Laws 5.11.13. Proving the Existence of an Element in a Set
5.12. Trivial and Vacuous Proofs
 5.12.1. Trivial Proofs 5.12.2. Vacuous Proofs
5.13. Proof by Induction
 5.13.1. Proving Sums of Series Using Mathematical Induction 5.13.2. Proving Inequalities Using Induction 5.13.3. Proving Divisibility of Expressions by Induction 5.13.4. Proving Matrix Identities Using Induction 5.13.5. Proving the Binomial Theorem 5.13.6. Proving the Complement of Intersections is Union of Complements 5.13.7. Proving the Complement of Unions is Intersection of Complements 5.13.8. Proving De Moivre's Theorem Using Induction 5.13.9. Proving the Sum of a Geometric Series Using Induction 5.13.10. Proving the Fermat's Little Theorem Using Induction 5.13.11. Proving the Cardinality of a Power Set
5.14. Proof by Strong Induction
 5.14.1. Strong Induction 5.14.2. Proving the Nth Term Formula of Recurrence Relations Using Induction 5.14.3. Proving the Fundamental Theorem of Arithmetic Using Induction 5.14.4. Proving the Closed Formula for the Fibonacci Numbers Using Induction 5.14.5. Proving the Sum of Fibonacci Numbers Using Induction 5.14.6. Proving the Sum of Odd Fibonacci Numbers Using Induction 5.14.7. Proving the Greatest Common Divisor of Two Fibonacci Numbers is Unity
6.
Indirect Proof
27 topics
6.15. Proof by Counterexample
 6.15.1. Introduction to Proof by Counterexample 6.15.2. Counterexamples Involving Parity 6.15.3. Counterexamples Involving Divisibility 6.15.4. Counterexamples of Real Number Statements 6.15.5. Counterexamples Involving Modular Congruence 6.15.6. Counterexamples Involving Inequalities 6.15.7. Counterexamples Involving Set Equalities 6.15.8. Counterexamples Involving Set Operations 6.15.9. Counterexamples Involving Cartesian Products
6.16. Proof by Contrapositive
 6.16.1. Introduction to Proof by Contrapositive 6.16.2. Proving Parity by Contrapositive 6.16.3. Proving Divisibility by Contrapositive 6.16.4. Proving Real Number Statements by Contrapositive 6.16.5. Proving Modular Congruence by Contrapositive 6.16.6. Proving Inequalities by Contrapositive 6.16.7. Proving Set Inequalities by Contrapositive 6.16.8. Proving Statements Involving Set Operations by Contrapositive
 6.17.1. Proof by Contradiction 6.17.2. Proving Parity by Contradiction 6.17.3. Proving Real Number Statements by Contradiction 6.17.4. Proving Divisibility by Contradiction 6.17.5. Proving Modular Congruence by Contradiction 6.17.6. Proving Set Equalities by Contradiction 6.17.7. Proving Statements Involving Set Operations by Contradiction 6.17.8. Proving Inequalities by Contradiction 6.17.9. Proving the Existence of Infinitely Many Primes by Contradiction 6.17.10. Proving the Division Algorithm
7.
Applications
22 topics
7.18. Cardinality
 7.18.1. Cardinality of the Natural Numbers, Integers, and Rationals 7.18.2. Cantor's Diagonal Argument 7.18.3. The Sizes of Infinity 7.18.4. The Continuum Hypothesis 7.18.5. Russel's Paradox 7.18.6. Cantor's Theorem 7.18.7. Sample Proof Topic
7.19. Modular Congruence
 7.19.1. Introduction to Modular Congruence 7.19.2. The Addition and Subtraction Properties of Modular Arithmetic 7.19.3. Residues 7.19.4. The Multiplication Property of Modular Arithmetic 7.19.5. The Division Property of Modular Arithmetic 7.19.6. Solving Linear Congruences 7.19.7. Solving Advanced Linear Congruences
7.20. Relations
 7.20.1. Proving Relations in Modular Arithmetic 7.20.2. Proving Set Relations 7.20.3. Proving Relations With Matrices 7.20.4. Partial Order
7.21. Equivalence Relations
 7.21.1. Relations 7.21.2. Equivalence Relations on Scalars 7.21.3. Residue Classes 7.21.4. Equivalence Classes with Scalars
8.
Other Proofs
16 topics
8.22. Sequences and Series
 8.22.1. Proving the Limit of a Null Sequence
8.23. Linear Algebra
 8.23.1. Scalar Triple Product Equals Determinant
8.24. Abstract Algebra
 8.24.1. Uniqueness of Inverses in a Group 8.24.2. Matrices with Positive Determinant form Multiplicative Group 8.24.3. Subgroup of Abelian Group is Normal 8.24.4. Generator of Cyclic Group Generates Quotient Group
8.25. Differential Equations
 8.25.1. Wronskian is Either Zero or Nonzero 8.25.2. Linear First-Order Differential Equation Has Unique Solution
8.26. Real Analysis
 8.26.1. The Product Rule for Derivatives 8.26.2. Unbounded Increasing Sequence Has Infinite Limit 8.26.3. (Rolle's Theorem) Differentiability, Continuity, and Equivalence at Endpoints Implies Stationary Point 8.26.4. Cauchy Sequence Converges if Subsequence Converges 8.26.5. Intersection of Infinitely Nested Intervals Contains Exactly One Number 8.26.6. (Bolzano-Weierstrass Theorem) Bounded Infinite Set of Real Numbers Has At Least One Limit Point
8.27. Complex Analysis
 8.27.1. Limit of Complex Function is Unique 8.27.2. Bounds for Complex Logarithm