Intro to Proofs

Course Overview

This semester-long course in logic, proof techniques, and proof writing is intended to bridge the wide gulf that exists between what is expected of students in lower-division college mathematics (such as the calculus sequence) and upper-division mathematics (such as analysis, number theory, group theory, and topology). Students learn the basics of logic (connectives, truth-tables, logical equivalence, quantification) and about standard proof techniques (contradiction, contrapositive, bidirectional inclusion, induction, element-chasing) through pre-class assignments accessed via the LMS. Students are expected to read the textbook, watch associated videos, and answer reading comprehension questions prior to each live session. Live sessions are 90 minutes each and occur twice a week via video conferencing software. For about half of the class period students work in small groups and tackle challenging problems. The rest of the session is devoted to student presentations, whole group discussion, and answering student questions. Students are encouraged to discuss how they conceptualize each topic as well as their problem-solving strategies. Students develop their proof-writing skills through weekly homework assignments. Similar to the process in the humanities, written proofs are provided with detailed feedback and subject to revision. Students demonstrate their final mastery of the material (including the ability to decide which proof method is appropriate in a given situation) by their performance on two take-home midterms and a take-home final exam. These exams contain a mix of questions that probe the students’ understanding of concepts and questions that require students to write polished, well-organized proofs. Most of the exam questions are unique, written by the instructor and a few colleagues, and are designed such that their solutions cannot be easily searched.  All homework assignments and exams must be written using the mathematical typesetting program LaTeX, which is introduced in the beginning of the course.

Unit 1: Logic and Proof Writing (and some Philosophy!)

This unit develops the essential aspects of propositional and first order logic while establishing proof-writing fundamentals. The unit begins with logical connectives, truth tables, and logical equivalence. Students then put this logical framework to use in writing proofs of elementary number theoretic results. Students are introduced to a set of writing guidelines early on, and through a submission and revision process, great care is taken to ensure that students are consistently producing polished proofs before they reach their first. The unit wraps up with a deep dive into open sentences and quantification. Throughout this unit a significant portion of the 90-minute class session is devoted to grappling with the philosophical aspects of logic (examples include the correspondence theory of truth, the liar’s paradox, paradoxes of material implication, plural quantification, and St. Anselm’s argument for the existence of God).

Unit 2: Standard Methods of Proof

This unit is devoted to building fluency in both reading and writing proofs using the standard techniques of direct proof, proof by contradiction/contrapositive, and proof by cases. Students are required not only to be able to produce such proofs, but also to develop strategies for deciding when to try one proof technique over another. The unit concludes with students applying these techniques to establish the basics of the theory of modular arithmetic. The bulk of each 90-minute class session is split between group discussions exploring student strategies for attacking proofs and practice writing persuasive proofs.

Unit 3: Mathematical Induction

This unit takes a deep dive into various aspects of proof by induction. Students are required to be able to read and produce polished proofs using both regular and strong induction. A significant portion of in-class discussion covers related topics like the structure of the natural numbers, the axiom of induction, the limits of proof by induction, induction’s relationship to the sorites paradox, and proof by infinite descent. The unit concludes with applications to recursively defined functions, with a focus on the Fibonacci numbers. Students are given ample time to practice the more formulaic aspects of this proof technique and to explore the various equivalent ways of applying the technique.

Unit 4: Set Theory and Functions

Starting from the naive definition that a set is a well-defined collection of objects, students immediately begin working with the fundamental set operations of union, intersection, and complement using concrete examples. From here students use element-chasing proofs to establish for themselves much of the basic theorems of set theory (e.g., theorems regarding the algebra of set operations, or DeMorgan’s Laws for sets). When appropriate, students are expected to prove their results for generally indexed arbitrary families of sets, not merely finite or countable collections of sets. This foundation in set theory leads into the formal definition of a function and the concepts of injections, surjections, and bijections. Students then prove various results regarding how injections, surjections, and bijections interact with function composition and invertibility. At the end of the unit students return to set theory through readings and a philosophical discussion of Russell’s paradox. Students spend each live session working collaboratively on practice problems, asking questions, and presenting solutions to the entire class. The exception is the final class session of the unit, where the time is entirely devoted to student discussion of the various potential solutions to Russell’s paradox and the relationship between Russell’s paradox and the liar’s paradox.

Unit 5: Topics in Number Theory and Analysis

This final unit of the semester allows students to use the skills they developed throughout the semester to prove more interesting theorems in broader mathematics. Canonical examples of such theorems include the Fundamental Theorem of Arithmetic and Cantor’s Theorem of multiple infinities. Other results in number theory and analysis are explored based on student interest and time. This unit wraps up with a brief foray into dialetheism and paraconsistent logics, providing students the context to see that even classical logic is not without its controversy. As with previous units, students spend each live session working collaboratively on practice problems, asking questions, and presenting solutions to the entire class. In years where the timing works out, a guest speaker (a real-life dialetheist) is invited to the final live session to host a discussion of dialetheism and paraconsistent logic.