Methods of Proof

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.

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.