Classes
- What makes computers go?
- Introduction to Discrete Math (Kevin Bacon)
- Course Logistics
- Why discrete math?
- Defense of Analog Computing
- “Hard” Problems
- Propositions
- Booleans
- Operations on Booleans
- Defining Boolean (Continued)
- Revisiting Propositions
- Implies (Logical operator)
- Axioms, Inference Rules, Predicates
- Soundness
- Contrapositive
- Recap: Inference Rules and Soundness
- Contrapositive
- Introduction to Proof (Odd Square Theorem, Even Square Theorem)
Class 5: Proof by Contradiction
- Recap: Proof by Contrapositive
- Proof by Contradiction
Class 6: Continuing Contradictions
- Finishing the proof of the Odd-Not-Even Lemma
- Irrational Numbers
- Proof that the square root of 2 is irrational
- Continuing Irrational Numbers
- Defining divides and prime
- Euclid’s Lemma
Class 8: Concluding Contradictions
- Preparing for Test 1
- Proof by Contradiction Practice
- Least Positive Rational
- Studenting
- Proof Methods
- Practice Problems
- Defining Sets
- Operations on Sets
- Building Sets
- Sets in Python!
Class 12: Quantifiers and Sets
- Quantifiers
- Negating Propositions with Quantifiers
- Defining Set Operators
Class 14: Cardinality of Finite Sets
- Defining Set Cardinality
- Binary Relations
- Reviewing Binary Relations
- Connections between relation properties and set sizes
- Power sets
- Power sets
- Practice with binary relations and set properties
- Defining the natural numbers unnaturally
Class 17: From Sets to Everything (or at least 2+2)
- Natural numbers from sets
- Operations on the natural numbers: 2+2=4
- Ordering Sets
- Well Ordering
- Proofs using the Well Ordering Principle
Class 21: Proving Well Ordering
- Well Ordering
- Proofs using the Well Ordering Principle
- Revisiting the Well-Ordered Definition
- Are all ordered finite sets well ordered?
Class 23: ω, Z, ZF, ZFC, and Zero
- ω (omega)
- Z, ZF, ZFC and the General Well Ordering Theorem
- Is Zero a Natural Number?
- Story so Far and Where We are Going
- Induction Principle
- Proofs using the Induction Principle
Class 25: Proofs using the Induction Principle
- Gauss Sum
- Power set size
Class 26: Power of Induction Proofs
- Finishing the power set size proof
- Defining the takeaway game
- Proof that takeaway always finishes
Class 28: Stronger (?) Induction
- Proofs using stronger induction
- Winning the Takeaway game
Class 29: Induction and Well Ordering Principle
- Betable Numbers (by Well Ordering Principle and by Induction Principle)
- Review for Test 3
- Practice Problems
- Flavors of Induction
Class 31: Test 3
- Infinite Sets
- Cardinality of infinite sets
- Countable Sets
Class 33: Countably Infinite Sets
- Infinite and Countable Sets
- Review of Binary Relations
- All Finite Sets are Countable
- The Integers are Countably Infinite
Class 34: Beyond Countable Infinities
- \( \mathbb{N} \times \mathbb{N} \) and \( \mathbb{Q} \) are Countably Infinite
- Finite and Infinite Binary Strings
- Uncountably Infinite
- Potential and Actual Infinities
- English is a Disaster
- Definiting Infinite, Countable, Uncountable, Countably Infinite
- Proofs of Countability and Uncountability
Class 36: Proving Uncountability
- Explaining the Rest of the Semester
- Proofs of Uncountability
- Diagonalization Proofs
- Cantor’s Diagonalization Proof (1891)
Class 37: Power of Uncountability
- Review: Proving Uncountability
- Infinite Binary Strings (recap)
- \( \pow(\mathbb{N}) \)
- Python programs
- Real numbers
- Uncountability of the Real Numbers
- Cantor’s Theorem
- Proving Cantor’s Theorem
- Completing Proof of Cantor’s Theorem
- Review for Test 4