 How It Works
Courses
JOIN BETA

# Methods of Proof

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.

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