Math Academy

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.

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

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

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

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

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

Methods of Proof

Outcomes

Content

Sets and Relations

Modular Arithmetic

Logic

Proofs