This course is currently under construction.
The target release date for this course is **April**.

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
38 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 with Primes | |

1.1.5. | Linear Diophantine Equations |

1.2. Sets

1.2.1. | Introduction to Sets | |

1.2.2. | Special Sets | |

1.2.3. | Set-Builder Notation | |

1.2.4. | Equivalent Sets | |

1.2.5. | Cardinality of Sets | |

1.2.6. | Subsets | |

1.2.7. | Power Sets |

1.3. Set Operations

1.3.1. | The Complement of a Set | |

1.3.2. | The Union of Sets | |

1.3.3. | The Intersection of Sets | |

1.3.4. | The Difference of Sets | |

1.3.5. | De Morgan's Laws for Sets | |

1.3.6. | The Cartesian Product | |

1.3.7. | Disjoint Sets | |

1.3.8. | Partitions of Sets | |

1.3.9. | Indexed Sets | |

1.3.10. | Indicator Functions |

1.4. Surjections, Injections and Bijections

1.4.1. | Sets and Functions | |

1.4.2. | Surjections | |

1.4.3. | Injections | |

1.4.4. | Bijections | |

1.4.5. | Into Functions |

1.5. Congruences

1.5.1. | Modular Congruence | |

1.5.2. | The Addition and Subtraction Properties of Modular Arithmetic | |

1.5.3. | Residues | |

1.5.4. | The Multiplication Property of Modular Arithmetic | |

1.5.5. | The Division Property of Modular Arithmetic | |

1.5.6. | Solving Linear Congruences | |

1.5.7. | Solving Advanced Linear Congruences |

1.6. Equivalence Relations

1.6.1. | Relations | |

1.6.2. | Equivalence Relations on Scalars | |

1.6.3. | Residue Classes | |

1.6.4. | Equivalence Classes with Scalars |

2.

Logic
19 topics

2.7. Compound Statements

2.7.1. | Statements and Propositions | |

2.7.2. | Compound Statements | |

2.7.3. | Negations | |

2.7.4. | Logical Equivalence with Compound Statements | |

2.7.5. | Associative and Commutative Laws | |

2.7.6. | Distributing Conjunctions and Disjunctions | |

2.7.7. | The Absorption Laws | |

2.7.8. | De Morgan's Laws for Logic | |

2.7.9. | Translating Between Logical Operations and Set Operations |

2.8. Conditional Statements

2.8.1. | Conditional Statements | |

2.8.2. | Logical Equivalence with Conditional Statements | |

2.8.3. | Converse, Inverse, and Contrapositive | |

2.8.4. | Necessary and Sufficient Conditions | |

2.8.5. | Biconditional Statements | |

2.8.6. | Tautologies and Contradictions |

2.9. Logical Quantifiers

2.9.1. | Universal and Existential Quantifiers | |

2.9.2. | Formal and Informal Language | |

2.9.3. | Negations of Quantifiers | |

2.9.4. | Nested Quantifiers |

3.

Direct Proof
19 topics

3.10. Direct Proofs

3.10.1. | Introduction to Direct Proofs | |

3.10.2. | Direct Proofs of Parity | |

3.10.3. | Direct Proofs of Divisibility | |

3.10.4. | Direct Proofs of Real Number Statements | |

3.10.5. | Direct Proofs of Modular Congruence | |

3.10.6. | Direct Proofs of Inequalities | |

3.10.7. | Direct Proofs of Set Equalities | |

3.10.8. | Direct Proofs Involving Set Operations | |

3.10.9. | Direct Proofs Involving Cartesian Products | |

3.10.10. | Proving De Morgan's Laws | |

3.10.11. | Proving the Existence of an Element in a Set |

3.11. Trivial and Vacuous Proofs

3.11.1. | Trivial Proofs | |

3.11.2. | Vacuous Proofs |

3.12. Proof by Induction

3.12.1. | Introduction to Mathematical Induction | |

3.12.2. | Proving Inequalities Using Induction | |

3.12.3. | Proving Divisibility of Expressions by Induction | |

3.12.4. | Proving the Nth Term Formula of Recurrence Relations Using Induction | |

3.12.5. | Proving Matrix Identities Using Induction | |

3.12.6. | Proof by Strong Induction |

4.

Indirect Proof
27 topics

4.13. Proof by Counterexample

4.13.1. | Introduction to Proof by Counterexample | |

4.13.2. | Counterexamples Involving Parity | |

4.13.3. | Counterexamples Involving Divisibility | |

4.13.4. | Counterexamples of Real Number Statements | |

4.13.5. | Counterexamples Involving Modular Congruence | |

4.13.6. | Counterexamples Involving Inequalities | |

4.13.7. | Counterexamples Involving Set Equalities | |

4.13.8. | Counterexamples Involving Set Operations | |

4.13.9. | Counterexamples Involving Cartesian Products |

4.14. Proof by Contrapositive

4.14.1. | Introduction to Proof by Contrapositive | |

4.14.2. | Proving Parity by Contrapositive | |

4.14.3. | Proving Divisibility by Contrapositive | |

4.14.4. | Proving Real Number Statements by Contrapositive | |

4.14.5. | Proving Modular Congruence by Contrapositive | |

4.14.6. | Proving Inequalities by Contrapositive | |

4.14.7. | Proving Set Inequalities by Contrapositive | |

4.14.8. | Proving Statements Involving Set Operations by Contrapositive |

4.15. Proof by Contradiction

4.15.1. | Proof by Contradiction | |

4.15.2. | Proving Parity by Contradiction | |

4.15.3. | Proving Real Number Statements by Contradiction | |

4.15.4. | Proving Divisibility by Contradiction | |

4.15.5. | Proving Modular Congruence by Contradiction | |

4.15.6. | Proving Set Equalities by Contradiction | |

4.15.7. | Proving Statements Involving Set Operations by Contradiction | |

4.15.8. | Proving Inequalities by Contradiction | |

4.15.9. | Proving the Existence of Infinitely Many Primes by Contradiction | |

4.15.10. | Proving the Division Algorithm |

5.

Applications of Proof
16 topics

5.16. Functions

5.16.1. | Proving Statements Involving Surjections | |

5.16.2. | Proving Statements Involving Injections | |

5.16.3. | Proving Statements Involving Bijections | |

5.16.4. | Proving Statements Involving Function Composition | |

5.16.5. | Proving Statements Involving Inverse Functions | |

5.16.6. | Proving Statements Involving Operations on Sets |

5.17. Cardinality

5.17.1. | Cardinality of the Natural Numbers, Integers, and Rationals | |

5.17.2. | Cantor's Diagonal Argument | |

5.17.3. | The Sizes of Infinity | |

5.17.4. | The Continuum Hypothesis | |

5.17.5. | Russel's Paradox | |

5.17.6. | Cantor's Theorem |

5.18. Relations

5.18.1. | Proving Relations in Modular Arithmetic | |

5.18.2. | Proving Set Relations | |

5.18.3. | Proving Relations With Matrices | |

5.18.4. | Partial Order |