Course Information

Lectures: MWF at 1:10pm in Young Hall 184.

Textbook: The Art of Proof by M. Beck and R. Geoghegan. The textbook should be accessible through the UC Davis Equitable Access Program. In addition, there is a version available in the authors' website.

Syllabus: The course syllabus contains the basic guidelines for the course.

Office Hours: Mondays 3:30-4:30pm and Wednesday 3:30-4:30pm (Casals) at MSB 3214. Always feel free to ask after class.

TA Moon's Office Hours are Mondays 1:00-2:00pm and Thursdays 4:00-5:00pm in MSB 2139. TA Gaston's Office Hours are Tuesdays 1:00-2:00pm and Wednesdays 10:00-11:00am in MSB 3139.

Recitations: For Section 1, Tuesday 3:10pm at Wellman Hall 3. For Section 2, Tuesday 4:10pm at Wellman Hall 7.

Important Dates: First Day (9/25), Veterdans Day (11/11), Thanksgiving (11/29), Last Day (12/6) and Final Exam (12/13).

Problem Sets: Weekly assignments are due on Fridays at the beginning of class, to be submitted through Gradescope.

Problem Sets

1. Problem Set 1: Due date 10/4.
   
   
2. Problem Set 2: Due date 10/11.
   
   
3. Problem Set 3: Due date 10/18.
   
   
4. Practice Problems I: Available 17/10, no due date.
   
   
5. Practice Problems II: Available 17/10, no due date.
   
   
6. Practice Midterm: Available 17/10, no due date.
   
   
7. Practice Midterm II: Available 17/10, no due date.
   
   
8. Problem Set 4: Due date 11/8.
   
   
9. Problem Set 5: Due date 11/15.
   
   
10. Problem Set 6: Due date 11/22.
    
    
11. Practice Problems (for 2nd Midterm): Available 11/14, no due date.
    
    
12. Practice 2nd Midterm: Available 11/19.
    
    
13. Practice 2nd Midterm II: Available 11/19.
    
    

Solutions

1. Solutions Problem Set 1.
   
   
2. Solutions Problem Set 2.
   
   
3. Solutions Problem Set 3.
   
   
4. Solutions Practice Problems I.
   
   
5. Solutions Practice Midterm I.
   
   
6. Solutions Practice Midterm II.
   
   
7. Solutions Problem Set 4.
   
   
8. Solutions Problem Set 5.
   
   
9. Practice Problems (for 2nd Midterm) with some solutions.
   
   

Math Diaries

1. Wednesday Sep 25: Introduction to MAT-108.
   Introduction to proofs. Examples of Mathematical Statements.
   The REP Principle. Anatomy of a Statement and Axioms.
   
   Textbook Reading (Sep 25): Chapter 1.1.
   
   
   
2. Friday Sep 27: Axioms and Properties for the Integers.
   
   The axiomatic definition of the integers.
   Properties deduced from axioms. Proof of Prop 1.6.
   Divisibility and Proof of Prop 1.16 as another instance.
   Discussion on axioms for the natural numbers.
   
   Textbook Reading (Sep 27): Chapters 1.2, 1.3, 1.4 and start of 2.1.
   
   
   
3. Monday Sep 30: Axioms for the Natural Numbers and Induction.
   
   The axiomatic definition of the integers. Discussion on the need for each axiom.
   Greater equal than (and less equal than): definition and properties.
   The induction axiom. The principle of induction.
   
   Textbook Reading (Sep 30): Chapter 2.1, 2.2 & 2.3.
   
   
   
4. Wednesday Oct 2: Induction in practice.
   
   Types of problems with induction: closed formulas, divisibility and inequalities.
   (More funky problems in problem set.) Proof that the sum of the first n number is n(n+1)/2.
   Induction proof of Proposition 2.18.(iii): a divisibility problem.
   Induction proof of the inequality n²<2ⁿ for n greater than 4.
   
   Textbook Reading (Oct 2): Chapter 2.1, 2.2 & 2.3.
   
   
   
5. Friday Oct 4: Proofs by contradiction.
   
   Proof by contradiction that an equation has no solutions.
   Existence of infinitely many primes (Euclid's proof).
   Showing that no rational number squares to 2.
   
   Textbook Reading (Oct 4): Chapter 2.1.
   
   This concludes Chapters 1 and 2 of the Textbook. The most important tool you have learnt this far are Proofs By Induction and Proofs By Contradiction.
   There are at least three types of situations in which induction can be applied: inequalities, divisibility problems and closed formulas for sums.
   
   
   1. Formulas and Inequalities depending on a natural number: Examples are Prop. 2.20, Prop. 2.24, Prop. 2.26, Prop. 2.27 and Problems 4 and 5 in Problem Set 2.
      We did more examples in class, such as the sum of the first n natural numbers.
      Some Real Life Examples are Problems 6 and 7 in Problem Set 2
      
      
   On Monday Oct 7, we will start Chapter 4 of the Textbook, in the topic of Recursion. (Chapter 3 in the textbook is only recommended reading.)
   
   
6. Monday Oct 7: Introduction to Recursion.
   
   Sequences. Discussion on next term versus closed formula.
   Examples of sequences. Linear Recursion. Sums and Products.
   Geometric sequences. Geometric Series. Proof of Proposition 4.13.
   
   Textbook Reading (Oct 7): Sections 4.1 and 4.2.
   
   
   
7. Wednesday Oct 9: Binomial Theorem and Factorials.
   
   Definition of Factorial and its Combinatorial Interpretation.
   Definition of Binomial Coefficients and its Combinatorics.
   Combinatorial Interpretation of a Binomial Coefficient.
   Corollary 4.20. The Binomial Theorem (Theorem 4.21).
   
   Textbook Reading (Oct 9): Section 4.4.
   
   
   
8. Friday Oct 11: Closed Formula For Linear Recursions.
   
   Linear recursions. Examples and Non-Example.
   Characteristic polynomial. Recipe for degree 2 linear recursions.
   Proof of Proposition 4.29: Closed Formula for Fibonacci Numbers.
   
   Textbook Reading (Oct 11): Section 4.6.
   
   
   
9. Monday Oct 14: Equivalence Relations.
   
   Equivalence Relations: Definitions, Examples and Non-Examples.
   The Equivalence Relation "Modulo n". Relations mod 2, mod 3 and mod 5.
   Proof of Proposition 6.24: Modulo n is an equivalence relation.
   
   Textbook Reading (Oct 14): Sections 6.1, 6.2 and 6.3.
   
   
   
10. Wednesday Oct 16: Fermat's Little Theorem.
    
    Problems Solved by Modular Arithmetic. Sums and Products.
    Proposition 6.25: Arithmetic Operations Modulo n. Examples.
    Powers modulo p: Freshman's Dream Lemma (Prop. 6.34) and proof.
    Fermat's Little Theorem and Application to divisibility.
    
    Textbook Reading (Oct 16): Sections 6.3 and 6.4.
    
    
    
11. Friday Oct 18: Problem-solving with Modular Arithmetic.
    
    Problems with modular arithmetic. Last digit: modulo 10 arithmetic.
    Non-Existence of integral solutions of Diophantine Equations.
    Divisibility Problems under the light of modular arithmetic.
    
    Textbook Reading (Oct 18): Sections 6.3 and 6.4.
    
    
    
12. Monday Oct 21: Notions of Set Theory.
    
    Examples of Sets. Inclusions, Intersections and Unions.
    Equalities of Sets as double inclusions. Examples. Complements.
    De Morgan's Laws for Complements. Proof of Theorem 5.15.
    
    Textbook Reading (Oct 21): Sections 5.1 and 5.2.
    
    
13. Wednesday Oct 23: Review Midterm I.
    
    
14. Friday Oct 25: Midterm Exam I.
    
    

    ---

    
    
15. Monday Oct 28: The Real Numbers.
    
    Axioms for the real numbers (8.1-8.5). Positive Real Numbers.
    Theorem 8.42: Non-existence of smallest positive real. Lower and Upper bounds.
    Infimums and Supremums, and uniqueness (Prop. 8.45). The Completeness Axiom (8.52).
    
    Textbook Reading (Oct 28): Chapter 8.
    
    
16. Wednesday Oct 30: Bounds, supremum and infimum.
    
    Recipe to show that a given bound is a supremum. (Same of infimum.)
    Proposition showing that inf([a,b])=inf((a,b])=a. Theorem 10.1.
    Proposition 10.4: for any e positive, there is N such that 1/N < e.
    
    Textbook Reading (Oct 30): Section 10.1.
    
    
17. Friday Nov 1: Limits.
    
    Sequences of real numbers. Absolute value.
    Distance in the real line. Definition of limit (with epsilon).
    Proposition 10.13. Examples of limits.
    
    Textbook Reading (Nov 1): Section 10.2-10.4.
    
    
18. Monday Nov 4: Monotone Convergence Theorem.
    
    Proposition 10.14: Uniqueness of limits.
    Increasing and decreasing sequences. Bounded sequences.
    The Monotone Convergence Theorem. Proof and Examples.
    
    Textbook Reading (Nov 4): Section 10.4.
    
    
19. Wednesday Nov 6: Limits for Recursive Sequences.
    
    Recursive Sequences of real numbers. Two Explicit Examples.
    Showing convergence and computing limits. (See also Prop. 11.25)
    Square roots of positive real numbers as supremums.
    
    Textbook Reading (Nov 6): Sections 10.4 and 10.5.
    
    
20. Friday Nov 8: The Rational Numbers.
    
    Definition of the rational numbers. Examples and operations.
    Density of the rational numbers in the real line (Theorem 11.8).
    Irrational Numbers. Irrationality of the square root of 2.
    
    Textbook Reading (Nov 8): Chapter 11.
    
    
21. Monday Nov 11: Veteran's Day.
    
    
22. Wednesday Nov 13: Introduction to Cardinality.
    
    Properties of functions: Injections, Surjections and Bijections.
    Examples of functions between sets. The integers are countably infinite (Prop 13.13).
    
    Textbook Reading (Nov 13): Sections 9.1, 13.1 and 13.2.
    
    
23. Friday Nov 15: Countable and uncountable sets.
    
    Types of Cardinality: finite, countably infinite, uncountably infinite.
    Theorem 13.4 and the Pigeonhole Principle (Prop. 13.5).
    The rational numbers are countably infinite. (Theorem 13.14).
    
    Textbook Reading (Nov 15): Sections 13.1 and 13.2.
    
    
24. Monday Nov 18: The Power Set of a Set.
    
    Definition of the Power Set. Examples for finite sets.
    Cardinality of the Power Set is strictly increasing (Theorem 13.31).
    The real numbers are uncountable (Theorem 13.22).
    Infinite Hierarchy of Infinities. Cantor set.
    
    Textbook Reading (Nov 18): Section 13.3 and 13.4.
    
    
25. Wednesday Nov 20: Solving Practice Second Midterms.
    
    
26. Friday Nov 22: Review Second Midterm.
    
    
27. Monday Nov 25: Second Midterm Exam.
    
    
Bounds on sets. Supremums and infinumums.
Limits (ε definition). Monotone Convergence Theorem.
Injections, Surjections and Bijections.
Cardinality: countable and uncountable sets.