LPS 105A/205A: Set Theory and Mathematical Reasoning

There are two main goals for this class:

• Develop some skills of mathematical proof (both written and verbal)
• Learn some basic set theory (both informal and formal)

You will learn both of these things by doing them.

Every week, you will write up the proof of one result we have gone over in class, and turn in the written version on Gradescope. I will give many choices each week of which result to write up - I encourage you to choose one that will provide an appropriate challenge for you, whether that’s getting precise on concisely writing up a simple proof, or managing the organization of a more complex proof.

Roughly half of the class time on every day after the first will consist of student presentations of mathematical results. Everyone should sign up to do one of these presentations in Part I and one of these presentations in Part II. I’ll be happy to meet with you in the days leading up to your presentations to ensure that you’ve figured out how your result works, and give some feedback on effectively presenting it.

Your final grade will primarily be based on completing all of these written and in-class proofs, with only slight modifications for quality.

Part I: Informal set theory

• Week 0 (9/25): Sets as meanings of words
• Week 1 (9/30, 10/2): Sets and numbers
• Week 2 (10/7, 10/9): Well-orderings, countable vs uncountable infinities
• Week 3 (10/14, 10/16): Many countable infinities
• Week 4 (10/21, 10/23): The real numbers, and the power set of the natural numbers
• Week 5 (10/28, 10/30): The Axiom of Choice, the paradoxes

Part II: Formal axiomatic set theory

• Week 6 (11/4, 11/6): The formal language, and the “small” axioms
• Week 7 (11/11, 11/13): NO CLASS (Tuesday is Veteran’s Day, Thursday I am traveling for a conference)
• Week 8 (11/18, 11/20): Power set, foundation, separation, and replacement
• Week 9 (11/25, Thanksgiving): Binary relations, well-orderings, and the axiom of infinity
• Week 10 (12/2, 12/4): Recursive and combinatorial definitions for arithmetic

Videos about proof by induction

• Khan Academy — straightforward video showing how to prove that the sum of the first n natural numbers is n(n+1)/2
• Kimberly Brehm — slightly longer video beginning with the general theory of mathematical induction (and why it works for integers, but not rationals or reals), then using it to prove that the sum of the first n odd numbers is n², plus her video on strong induction
• Trefor Bazett — the same result as the Khan Academy one, with a general “ladder” metaphor, plus his video on strong induction
• Zach Star, “What does mathematical induction really look like?” — shows visually how induction works for various geometric examples, including the Towers of Hanoi and dominoes
• EH, “Introduction to strong induction” — a helpful example proof where strong induction is essential
• AfterMath, “Induction, weak and strong” — one video covering both concepts

Proofs without words

• Examples from Arindam Khan, on Quora
• Robin Miller, “On Proofs Without Words” (2012) — what it takes for a diagram to constitute a proof without words

On the nature of proof

• Keith Weber and Fenner Tanswell, “Instructions and recipes in mathematical proofs” (2022) — points out that mathematical proofs, like recipes for cooking, are usually written in the imperative mood, telling the reader what to do, see, or notice
• Fenner Tanswell and Matthew Inglis, “The Language of Proofs” (2023) — a more detailed study of the specific verbs used in mathematics, particularly “let”, “consider”, “assume”, “denote”, “note”, “define”, “suppose”, “recall”, “write”, “take”, “choose”, “fix”, and “observe”
• Kenny Easwaran, “Probabilistic Proofs and Transferability” (2009) — argues that the point of a mathematical proof is not to get the reader to trust the author, but to give the reader a way to produce their own knowledge of the result
• Kenny Easwaran, “Rebutting and Undercutting in Mathematics” (2015) — argues that although published mathematical proofs are not infallible, they are expected to reach a level of detail at which a counterexample would show which step went wrong
• Yehuda Rav, “Why Do We Prove Theorems?” (1999) — a classic paper arguing that the point of proofs is not just to provide knowledge of the result but to develop methods and techniques for other applications
• Lewis Carroll, “What the Tortoise Said to Achilles” (1895) — a classic paper making the case that what matters for understanding a proof is not knowledge of the statement of an argument, but an ability to follow it

• Trefor Bazett’s discrete maths videos
• Antonio Montalbán’s set theory class videos
• José Ferreirós, “The Early Development of Set Theory”, Stanford Encyclopedia of Philosophy