Instructor: Brendon Rhoades
Instructor's Email: bprhoades (at) math.ucsd.edu
Instructor's Office: 7250 APM
Instructor's Office Hours: MWF 5:00-6:00pm or by appointment
TA: Sinan Aksoy
TA's Email: saksoy (at) ucsd.edu
TA's Office: APM 5412
TA's Office Hours: W 3:00-5:00 pm
Lecture Time: MWF 2:00-2:50 pm
Lecture Room: 104 PETER
Discussion Times: B01: W 6:00-6:50 pm, B02: W 7:00-7:50 pm
Discussion Room: CENTR 217A
Final Exam Time: 3:00-5:59pm, 3/17/2014

Syllabus: Please read carefully

Lectures:
1/6: Syllabus and administrivia. Class activity. Chapter 1. Propositions, predicates, and statements. Truth tables for the connectives "and", "or", and "not". The negation of "All UCSD students like Sun God."
1/8: Equivalence of statements using truth tables. Chapter 2. The connective "implies". Examples. Various ways of writing "P implies Q." The converse and the contrapositive. The definitions of "a divides b", "b is even" and "b is odd" for integers a and b. A proof that 101 is odd.
1/10: Chapter 3. The method of direct proof. The proof that for a, b positive real numbers, (a < b) implies (a^2 < b^2) (Axioms of Inequality). Proof by cases with a simple example.
1/13: Chapter 3. A more complicated example of proof by cases: if a is a real number other than zero, then a^2 is positive. An example of working backwards: prove that ab + ac + bc <= a^2 + b^2 + c^2 for all real numbers a, b, c. Chapter 4. A proof by contradiction that there do not exist integers m, n such that 6m + 8n = 33.
1/15: Chapter 4. A proof by contradiction that if d > 1 is an integer, then for any integer n either d does not divide n or d does not divide (n+1). A proof by working backwards that for any positive distinct reals x, y, we have (x/y) + (y/x) > 2. A proof by contradiction that if n is an integer and n^3 - 7n is odd, then n is odd. Proof by contrapositive.
1/17: Chapter 5. Proof by induction. A proof that 3 divides n^3 - n for all positive integers n. A warning that one must remember the base case in an inductive proof. Changing the index of the base case. A proof that m^3 <= 2^m for all integers m >= 10.
1/22: Chapter 5. The "strong" principle of induction. An example: the Binet formula for the Fibbonacci numbers.
1/24: Chapter 6. Sets. Ways to construct sets. Some "common" sets.
1/27: Chapter 6. Equality of sets. Union, intersection, subsets, and proper subsets. Disjoint sets. Complements. The empty set. Using truth tables to prove set equality.
1/29: Chapter 6. More on sets, Russell's Paradox. Chapter 7. Quantifiers ("for all, there exists"). Proving and disproving statements involving quantifiers.
1/31: Midterm 1.
2/2: Chapter 7. Mixing and matching quantifiers. The Cartesian Product of sets. Anonymous course feedback.
2/5: Chapter 8. Functional notation f: X ---> Y. Domain, codomain, image, graph, composition, identity function I_X on X. Functional equality. Restriction of domain.
2/7: Chapter 8. Associativity and non-commutativity of functional composition. Chapter 9. Injections, surjections, and bijections. Examples.
2/10: Chapter 9. Inverses and invertible functions. Theorem: A function is invertible if and only if it is bijective, in which case its inverse is unique.
2/12: Chapter 9. Given a function f: X to Y, we get induced functions (P(X) to P(Y)) and (P(Y) to P(X)). Chapter 10. Finite sets and cardinality. Theorem: The cardinality |X| of a finite set is well defined. Proof: Postponed. Basic counting theorems. |X x Y| = |X| |Y| and |X \cup Y| = |X| + |Y| - |X \cap Y|.
2/14: Chapter 11. A proof of the fact the cardinality |X| of a finite set X is well defined. If f: X ---> Y is an injection of finite sets, then |X| <= |Y|. Pigeonhole Principle: If f: X ---> Y is a function between finite sets and |X| > |Y|, then there exist distinct x, x' in X such that f(x) = f(x').
2/19: Chapter 11. Examples of the Pigeonhole Principle. Given any 5 points on a sphere, there is a closed hemisphere containing at least 4 of them. There are two people on Facebook with the same number of friends. Any subset X of a finite set Y is finite and |X| <= |Y|. If f: X ---> Y is a function and |X| < |Y|, then f is not a surjection. If f: X ---> Y is a function and |X| = |Y|, then f is a surjection iff f is an injection iff f is a bijection. Maximum and minimum elements of sets of real numbers. Any finite set of real numbers has a maximum element.
2/21: Chapter 12. Counting Fun(X,Y) and Inj(X,Y) for finite sets X and Y. Permutations of a set. The sets P_r(X). Binomial Coefficients. Counting the power set P(X) of a finite set X.
2/23: Chapter 12. The binomial coefficients. The Pascal recursion. Formula for binomial coefficients. The binomial theorem.
2/26: Chapter 14. Infinite sets. Denumerable sets. Countable sets. Uncountable sets. A set is infinite iff it is equipotent to a proper subset of itself. A Cartesian product of two denumerable sets is denumerable. A Cartesian product of finitely many denumerable sets is denumerable. A subset of a denumerable set is countable.
2/28: Midterm 2.
3/3: Chapter 14. The set of rational numbers is countable. A countable union of countable sets is countable. The real interval [0,1] is not countable: Cantor's diagonalization argument. For any set X, there is no bijection between X and the power set P(X).
3/5: Chapter 15. The Division Theorem and its proof. If an integer n is a perfect square, then n = 3k+1 or n = 3k for some integer k. If a is an integer, then a is divisible by 3 if and only if a^2 is divisible by 3.
3/7: Chapter 16. The greatest common divisor gcd(a,b). Using the Euclidean algorithm to find the gcd. gcd(a,b) is an integer linear combination of a and b.
3/10: Chapter 17. gcd(a,b) is the minimum positive integer linear combination of a and b. Chapter 22. Partitions of a set.
3/12: Chapter 22. Relations. The reflexive, symmetric, and transitive properties. (Non-)examples.
3/14: Review.

Homework:
Homework 1, due 1/10/2014.
Homework 2, due 1/17/2014.
Homework 3, due 1/24/2014.
Homework 4, due 2/7/2014.
Homework 5, due 2/14/2014.
Homework 6, due 2/24/2014.
Homework 7, due 3/7/2014.
Homework 8, due 3/14/2014.

Midterms:
Midterm 1 and Solutions.

Practice Midterm 2 and Solutions.
Midterm 2 and Solutions.

Practice Final Exam and Solutions.