Instructor: Brendon Rhoades
Instructor's Email: bprhoades (at) math.ucsd.edu
Instructor's Office: 7250 APM

Lecture Time: MWF 3:00-3:50 pm
Lecture Room: 109 PCYNH

TAs: Michelle Bodnar, Jonathan Conder, and Garrett Williams
TAs' Emails: mbodnar@ucsd.edu, jconder@ucsd.edu, g2willia@ucsd.edu
Discussion Times/Rooms:
Section C01 - M 5:00-5:50 pm - B412 APM
Section C02 - M 6:00-6:50 pm - B412 APM
Section C03 - M 7:00-7:50 pm - B412 APM
Section C04 - M 8:00-8:50 pm - B412 APM
Section C05 - M 4:00-4:50 pm - 120 PCYNH

TAs' Office Hours:
M. Bodnar: M, W 1:00-3:00 pm 6436 APM
J. Conder: Tu, F 4:00-5:00 pm 6132 APM
G. Williams: M, W 10:00-11:00 am, W 2:00-3:00 pm 2313 APM

Final Exam Time: 3:00-5:59pm, 6/8/2016
Final Exam Room: TBA

Syllabus: Please read carefully.

Lectures:

3/28: Administrivia. Section 1.1. Propositions, free variables, predicates, and statements. Examples and non-examples. Section 1.2. The logical connectives "and", "or", "not". The ambiguity of "or" in English. Issues involving "not". Truth tables. Section 2.1. The logical connective "implies". Examples.
3/30: Section 2.1. Logical equivalence. Implications involving predicates. Other ways of saying "implies". Section 2.2. Mathematical definitions. Proof that 15 is odd.
4/1: Section 3.1. Axioms for <. The method of direct proof. Application: If a < b for a, b positive, then a^2 < b^2. Proof by cases. Application: If a is a nonzero real number, then a^2 > 0. Section 3.2. Working backwards. Application: If a < b, then 4ab < (a+b)^2. Section 4.1. Proof by contradiction. Application: There do not exist integers m, n so that 12m + 10n = 303.
4/4: Section 4.2. Proving implications by contradiction. Section 4.3. Proof by contrapositive. Section 5.1. Proof by induction. For any positive integer n, 3 divides n^3 - n.
4/6: Section 5.2. Changing the inductive base case: proof that for any integer m at least 10, we have m^3 <= 2^m. The necessity of base cases: "proof" that 4n+1 is even for all positive integers n. Section 5.3. The inductive definition of the Fibonacci sequence. Section 5.4. The "strong" induction principle. Statement of Binet's Forumla and some of its consequences.
4/8: Section 5.4. Proof of Binet's Formula using strong induction. Section 6.1. Introduction to sets. Ways to write sets. Equality of sets.
4/11: Section 6.1. Subsets and proper subsets. Section 6.2. Intersection, union, difference of sets. The empty set. Disjoint sets. Complements of sets. The power set. Arithmetic of sets.
4/13: Section 7.1. The Universal Quantifier. Section 7.2. The Existential Quantifier. Section 7.3. Proving and disproving statements involving quantifiers. Chaining quantifiers. The definition of a limit.
4/15: Negation of a statement involving a limit. The Cartesian product of sets. Chapter 8. Functions between sets. Domains and codomains.
4/18: Prof. Rhoades is in Fargo. Prof. Rogalski will lecture from Chapter 8.
4/20: Midterm 1.
4/22: Chapter 8. The image and graph of a function. Chapter 9. Injections, surjections, and bijections. (Non-)Examples.
4/25: Chapter 9. Inverses and invertible functions. (Non-)Examples. Inverses are unique when they exist. A function is invertible if and only if it is bijective. Induced functions between power sets.
4/27: More on induced functions between power sets. Chapter 10. The meaning of |X| = n. The Principle of Inclusion Exclusion. |X x Y| = |X||Y| for finite sets X, Y.
4/29: The cardinality of a finite set is well-defined. Chapter 11. The pigeonhole principle. Applications.
5/2: Chapter 11. Functions between finite sets. The maximum and minimum of a set of real numbers. The greatest common divisor gcd(a,b). Chapter 12. If |X| = m and |Y| = n, the number of functions from X to Y is n^m. Fun(X,Y). The number of injections from X to Y is n(n-1)(n-2)...(n-m+1).
5/4: Chapter 12. Binomial coefficients. Formula for the binomial coefficient (n choose k). Pascal Recursion.
5/6: Chapter 12. The Binomial Theorem. Chapter 14. Equipotent sets. Denumerable sets. Countable sets. Uncountable sets. Examples. If X is countable and Y is a subset of X, then Y is countable.
5/9: Chapter 14. A finite product of countable sets is countable. A countable union of countable sets is countable. Example: The rational numbers Q is countable. Example: The real interval [0,1] is uncountable. Cantor diagonalization.
5/11: Chapter 14. The notation |X| <= |Y| and |X| < |Y|. Statement of the Cantor-Schroeder-Bernstein Theorem. For any set X, we have |X| < |P(X)|.
5/13: Chapter 22. Equivalence relations ~ on a set X. Examples and non-examples. The equivalence class [x] of an element x in a set X with an equivalence relation ~.
5/15: Chapter 22. Partitions of a set. Bell numbers. Set partitions and equivalence relations are the same thing.
5/18: Midterm 2.
5/20: Chapter 22. Rational numbers. Functions defined on rational numbers. Addition and multiplication of rational numbers and their well-definedness. Transfering properties of + and x on Z to Q.
5/23: Chapter 15. The Division Theorem. The Well-Ordering Axiom. Proof of the Division Theorem using Well-Ordering. Application of the Division Theorem: For any integer n, 3|n if and only if 3|n^2.
5/25: Chapter 15. If n is a perfect square, then n = 3q or 3q+1 for some integer q. Chapter 16. Greatest common divisors. Introduction to the Euclidean Algorithm.
5/30: Chapter 17. More on the Euclidean algorithm. If a,b are positive integers, then gcd(a,b) is the smallest positive Z-linear combination of a,b. Coprime integers. a,b are coprime if and only if ma + nb = 1 for some integers m, n.
6/1: Prime numbers. The Fundamental Theorem of Arithmetic: Every positive integer can be written uniquely as a product of primes (up to reordering). Examples. Proof of the FTA. Key Lemma: If a | bc and gcd(a,c) = 1, then a | b. Proof (using the FTA) that the square root of 2 is irrational.
6/3: Review.

Homework:

Homework 1, due 4/6/2016. (Alert! Problem 7 on this homework was altered on 3/29. Please do the current version.)
Homework 2, due 4/15/2016.
Homework 3, due 4/29/2016.
Homework 4, due 5/6/2016.
Homework 5, due 5/13/2016.
Homework 6, due 6/1/2016.



Midterms:
Practice Midterm 1.

Midterm 1.

Practice Midterm 2.

Midterm 2.

Practice Final Exam.