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.

- 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.

- 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.

- 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.

- 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. Proof by Contradiction

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 |