# Methods of Proof

This course introduces students to proof-writing essentials, bridging the gap between pure problem-solving and constructing formal mathematical arguments. Students will formalize their understanding of logic, sets, and functions while delving into new concepts such as congruence, relations, and cardinality.

This course serves as ideal preparation for students wishing to pursue undergraduate studies in formal mathematical disciplines, including Discrete Mathematics, Abstract Algebra, and Real Analysis.

The prerequisite for Methods of Proof is single-variable calculus, which would be satisfied by completion of either Calculus II, AP Calculus BC, or Mathematical Foundations III.

## Content

Students begin by mastering the basics of logic and logical operations, including statements, predicates, connectives, logical laws, logical equivalence, conditional and biconditional statements, quantifiers, inference, and formal and informal language. By solidifying their grasp of these logical fundamentals, students will have a secure underpinning that enables them to embark on their journey into proof-writing confidently.

A robust knowledge of set theory is another cornerstone of mathematical proof-writing. Students will extend and formalize their understanding of sets and learn to translate between logical and set operations. By the end of the course, students will appreciate how set theory provides a comprehensive toolkit for proving mathematical results.

After mastering these fundamentals, students will explore various proof-writing techniques, including direct proof, proof by cases, proof by contrapositive, proof by contradiction, disproof, and mathematical induction. The course emphasizes proving concepts related to parity, divisibility, congruence, sequences, functions, set identities, and relations. Students will have multiple opportunities to test and refine their proof construction and comprehension skills throughout the course and in varied contexts

This challenging yet engaging course helps students with strong mathematical foundations build a solid base for further progression into advanced undergraduate courses.

Upon successful completion of this course, students will have mastered the following:

### I. Logic

• Determining truth values of mathematical statements.
• Using the "and," "or," and "not" connectives in logical expressions and constructing truth tables for compound statements.
• Applying the associative, commutative, distributive, absorption, and idempotent laws to simplify logical expressions and understanding how truth tables are used to prove these laws.
• Determining whether two statements are logically equivalent.
• Proving De Morgan's laws using truth tables and applying these laws to simplify logical statements.
• Conditional and biconditional statements, their truth tables, and logical equivalences.
• Defining and identifying tautologies and contradictions.
• Forming a statement's converse, inverse, and contrapositive and understanding the relationship between them in terms of logical equivalences.
• Constructing truth sets of compound and conditional predicates.
• Describing necessary and sufficient conditions, and applying proper grammatical constructions to conditional and biconditional statements.
• Working with universal and existential quantifiers, including their negations, manipulating statements containing nested quantifiers, translating between formal and informal language, and prenex normal form.
• Understanding and applying the rules of logical inference.

### II. Set Theory

• Understanding set fundamentals, including equivalence, constructive and conditional definitions of sets, indexed sets, cardinality, power sets, partitions, union, intersection, difference, and the Cartesian product.
• Translating between logical and set operations.
• Proving that a set is a subset of another set.
• Understanding and applying elementary set identities and proving these identities using various techniques.
• Understanding and applying De Morgan's laws for sets and proving these laws using various methods.
• Proving the distributive properties of union, intersection, and Cartesian product using various methods.

### III. Mathematical Proof

• Constructing proofs of mathematical statements using direct proof, proof by cases, trivial and vacuous proofs, and disproving universal statements and implications.
• Proving mathematical statements using the contrapositive.
• Proving mathematical statements by contradiction.
• Proving biconditional statements.

### IV. Discrete Mathematics & Number Theory

• Using the divisibility properties of integers, including the division algorithm, to prove divisibility statements.
• Understanding and applying the Euclidean and extended Euclidean algorithms and BÃ©zout's identity.
• Solving linear Diophantine equations.
• Understanding and applying the principle of mathematical induction to prove statements regarding sums of finite series, inequalities, divisibility, first-order recurrence relations, and matrix identities.
• Understanding the principle of strong induction and using this to prove statements related to second-order recurrence relations.

### V. Sequences & Functions

• Understanding the formal definitions of a sequence's finite or infinite limit and solving related problems.
• Proving that a sequence converges to a finite or infinite limit.
• Understanding the definitions of injectivity, surjectivity, and bijectivity and determining whether a given function is injective, surjective, or bijective.
• Proving or disproving that a function is injective or surjective.
• Understanding the concept of equal cardinality for infinite sets and constructing bijections to show that two infinite sets have the same cardinality.
• Understanding and applying Cantor's diagonal argument, the Cantor-Bernstein-SchrÃ¶der theorem, and analyzing the power set of natural numbers.
• Proving Cantor's theorem, applying it to various situations, and describing the continuum hypothesis and its consequences.

### VI. Congruence of Integers

• Understanding and applying the concept of modular congruence.
• Applying and proving the addition, multiplication, and division laws of modular arithmetic.
• Proving divisibility statements using modular congruence.
• Understanding the definitions of the additive and multiplicative inverses of a number modulo N, including the conditions that must be met for a multiplicative inverse to exist.
• Solving linear congruences, including cases with multiple solutions, and determining when a congruence has no solutions.
• Proving theorems related to the solutions of linear congruences.
• Applying the Chinese remainder theorem to solve systems of linear congruences.

### VII. Equivalence Relations

• Understanding the definition of relation and determining the domain and range of a relation.
• Representing relations graphically using graphs, adjacency matrices, and diagraphs.
• Performing operations on relations and analyzing n-ary and functional relations.
• Determining whether a relation is reflexive, symmetric, or transitive given various representations.
• Defining and analyzing equivalence relations and equivalence classes.
• Proving that a given relation is an equivalence relation.
• Understanding how equivalence classes are used to define the integers modulo N.
1.
Logic
31 topics
1.1. Statements
 1.1.1. Statements and Predicates 1.1.2. The "And" and "Or" Connectives 1.1.3. Truth Tables 1.1.4. The "Not" Connective 1.1.5. Logical Equivalence 1.1.6. Logical Associative and Commutative Laws 1.1.7. The Distributive Laws 1.1.8. The Absorption Laws 1.1.9. De Morgan's Laws for Logic
1.2. Implications and Biconditionals
 1.2.1. Conditional Statements 1.2.2. Logical Equivalence with Conditional Statements 1.2.3. Biconditional Statements 1.2.4. Tautologies and Contradictions 1.2.5. Converse, Inverse, and Contrapositive
1.3. Predicates
 1.3.1. Truth Sets of Predicates 1.3.2. The "And" and "Or" Connectives With Predicates 1.3.3. The "Not" Connective With Predicates 1.3.4. Simplifying Predicate Expressions Using De Morgan's Laws 1.3.5. Conditional Statements With Predicates 1.3.6. Necessary and Sufficient Conditions 1.3.7. Grammatical Constructions for Conditional Statements 1.3.8. Translating Between Logical and Set Operations
1.4. Quantifiers
 1.4.1. Universal and Existential Quantifiers 1.4.2. Negating Quantified Statements 1.4.3. Nested Quantifiers 1.4.4. Formal and Informal Language 1.4.5. Negating Statements With Nested Quantifiers 1.4.6. Prenex Normal Form
1.5. Logical Inference
 1.5.1. Implication Elimination and Denying the Consequent 1.5.2. Disjunctive Syllogism and Transitivity of Implication 1.5.3. Additional Rules of Logical Inference
2.
Set Theory
30 topics
2.6. Introduction to Set Theory
 2.6.1. Sets 2.6.2. Special Sets 2.6.3. Equivalent Sets 2.6.4. The Constructive Definition of a Set 2.6.5. The Conditional Definition of a Set 2.6.6. Describing Sets Using Set-Builder Notation 2.6.7. Describing Planar Regions Using Set-Builder Notation 2.6.8. Cardinality of Finite Sets 2.6.9. Infinite Sets 2.6.10. The Maximum and Minimum of a Set
2.7. Subsets
 2.7.1. Subsets 2.7.2. Power Sets 2.7.3. Partitions of Sets 2.7.4. Indicator Functions 2.7.5. Proving Subset Relations
2.8. Set Operations
 2.8.1. The Union of Sets 2.8.2. The Intersection of Sets 2.8.3. The Difference of Sets 2.8.4. Set Complements 2.8.5. The Cartesian Product 2.8.6. Visualizing Cartesian Products 2.8.7. Indexed Sets 2.8.8. Disjoint Sets
2.9. Properties of Set Operations
 2.9.1. Elementary Properties of Set Operations 2.9.2. Proving Elementary Properties of Set Operations 2.9.3. De Morgan's Laws for Sets 2.9.4. Proving De Morgan's Laws for Sets 2.9.5. Distributive Properties of Set Operations 2.9.6. Proving Distributive Properties of Union and Intersection 2.9.7. Proving Distributive Properties of the Cartesian Product
3.
Mathematical Proof
15 topics
3.10. Introduction to Mathematical Proof
 3.10.1. Direct Proof 3.10.2. Proving Parity 3.10.3. Proving Divisibility 3.10.4. Proof by Cases 3.10.5. Disproving Universal Statements 3.10.6. Disproving Implications 3.10.7. Trivial and Vacuous Proofs 3.10.8. Proving Biconditional Statements
3.11. Proof by Contrapositive and Contradiction
 3.11.1. Proof by Contrapositive 3.11.2. Proving Parity by Contrapositive 3.11.3. Proving Divisibility by Contrapositive 3.11.4. Proof by Contradiction 3.11.5. Proving Irrationality by Contradiction 3.11.6. Proving Properties of Irrationals by Contradiction 3.11.7. Proving Divisibility by Contradiction
4.
Discrete Mathematics & Number Theory
13 topics
4.12. Divisibility
 4.12.1. Parity 4.12.2. Integer Divisibility 4.12.3. The Division Algorithm 4.12.4. The Euclidian Algorithm 4.12.5. The Extended Euclidean Algorithm 4.12.6. Linear Diophantine Equations 4.12.7. Properties of Integer Divisibility 4.12.8. Properties of Prime Divisibility
4.13. Proof by Induction
 4.13.1. Mathematical Induction 4.13.2. Proving Inequalities Using Induction 4.13.3. Proving Divisibility Using Induction 4.13.4. Proving Matrix Identities Using Induction 4.13.5. Strong Induction and Recurrence Relations
5.
Sequences & Functions
20 topics
5.14. Sequences
 5.14.1. The Limit of a Null Sequence 5.14.2. Proving the Limit of a Null Sequence 5.14.3. Proving the Finite Limit of a Sequence 5.14.4. Infinite Limits of Sequences 5.14.5. Proving a Sequence Has an Infinite Limit
5.15. Functions
 5.15.1. Sets and Functions 5.15.2. Injections 5.15.3. Proving Injectivity 5.15.4. Surjections 5.15.5. Into Functions 5.15.6. Proving Surjectivity 5.15.7. Bijections 5.15.8. The Floor and Ceiling Functions
5.16. Cardinality
 5.16.1. Discrete Infinite Sets With Equal Cardinality 5.16.2. Continuous Infinite Sets With Equal Cardinality 5.16.3. Cardinality of the Natural Numbers, Integers, and Rationals 5.16.4. Cantor's Diagonal Argument 5.16.5. The Cantor-Bernstein-Schröder Theorem 5.16.6. The Cardinality of the Power Set of Natural Numbers 5.16.7. Cantor's Theorem
6.
Congruence of Integers
14 topics
6.17. Modular Congruence
 6.17.1. Modular Congruence 6.17.2. The Addition Property of Modular Arithmetic 6.17.3. Modular Residues 6.17.4. The Multiplication Properties of Modular Arithmetic 6.17.5. The Division Properties of Modular Arithmetic 6.17.6. Proving Properties of Modular Congruence 6.17.7. Proving Divisibility Using Congruence 6.17.8. Proving Congruence by Contrapositive
6.18. Linear Congruences
 6.18.1. Additive Inverses Modulo N 6.18.2. Multiplicative Inverses Modulo N 6.18.3. Solving Linear Congruences 6.18.4. Solving Advanced Linear Congruences 6.18.5. The Chinese Remainder Theorem 6.18.6. Proving Properties of Linear Congruences
7.
Equivalence Relations
15 topics
7.19. Relations
 7.19.1. Relations on Finite Sets 7.19.2. Relations on Infinite Sets 7.19.3. The Domain and Range of a Relation 7.19.4. Graphical Representations of Relations 7.19.5. Operations on Relations 7.19.6. N-ary Relations 7.19.7. Functional Relations
7.20. Equivalence Relations
 7.20.1. Reflexive and Irreflexive Relations 7.20.2. Symmetric and Antisymmetric Relations 7.20.3. Transitive Relations 7.20.4. Equivalence Relations 7.20.5. Proving a Relation Is an Equivalence Relation 7.20.6. Residue Classes 7.20.7. Equivalence Classes 7.20.8. The Integers Modulo N