LECTURE: MATH 13, SPRING 2018, M-W-F: 3-3:50 @ MSTB 122
INSTRUCTOR: NAM TRANG
OFFICE HOURS: M 2-3, W 11:30-12:30 @ RH 410N
OFFICE HOURS (FINAL'S WEEK): M 12:30-3 @ RH 410N

--> DISCUSSION: T-Th: 3-3:50 @ MSTB 122
TA: Daniel Agress


COURSE SYLLABUS AND POLICIES     UCI Academic Honesty Policies     UCI Student Resources

COURSE LECTURE NOTES

SAMPLE MIDTERM

FINAL REVIEWS AND SAMPLE PROBLEMS


HOMEWORK ASSIGNMENTS:     HW1     HW2     HW3     HW4     HW5     HW6     HW7     HW8

SOLUTIONS TO SELECTED HOMEWORK PROBLEMS:     HW1     HW2     HW3     HW4     HW5     HW6     HW7     HW8

COURSE PROGRESS

Week 1
M: Defined theorem as a TRUE statement of the form "If A then B"; gave examples of theorems and proved "the sum of two even integers is even"; defined conjecture and gave examples; proved the conjecture "If n is odd then n^2-1 is divisible by 8" and disproved the conjecture "n^2 + n + 41 is prime for every non-negative n".
W: Define propositions, connectives (AND, OR, NOT, IF ... THEN ..., IF AND ONLY IF), truth tables, definitions of a theorem, proof. Went over examples of determining a truth value of a proposition given the truth values of its components. Defined contrapositive and converse of P->Q and showed contrapositive NOT Q -> NOT P is logically equivalent to P->Q
F: State and prove DeMorgan's laws, compute NEG (P -> Q), define tautology and contradiction, discussed proof methods: direct, proof by contrapositive, proof by contradiction, proof by induction. Gave an example of a direct proof: prove that if x, y are odd, then x.y is odd.

Week 2
M: Examples of proofs by contrapositive (prove "if x.y is odd, then x and y are odd"). This and along with the direct proof on Friday complete an example of proof of an "if and only if" statement. Give a proof by contradiction: prove that the square root of 2 is irrational. Introduce quantifiers and discuss rule for negating statements with quantifiers.
W: Quantifiers: definition, examples, how to negate statements with quantifiers, defined counter-example of statement of the form forall x P(x). Discussed how to turn a statement in English into a mathematical statement (beware of hidden quantifiers); discussed in details problem 4(a) of homework 1. Order of quantifiers: gave examples "forall x exists y (y>x)" has different meaning than "exists y forall x (y>x)".
F: Review quantifiers, give examples, negations, and proofs of statements with quantifiers. Example 1: all nonzero real numbers have multiplicative inverses (translate this to math form and compute its negation). Example 2: If n is not prime, then there is an integer a which divides n and is in the interval [2, sqrt(n)] (proof by contradiction). Example 3: give a direct proof of the statement "f(x) = x^2 is continuous at 0" (using the epsilon, delta definition of continuity).
Week 3
M: Division algorithm. Defined "a is congruent to b modulo m" and gave examples of these notions. Showed that for all integer n, n^2 is congruent to either 0 or 1 mod(m). Observed that for any positive m, if i and j are distinct numbers between 0 and m-1, then the classes [i] and [j] are disjoint; futhermore, each integer is in (exactly) a class [i] for some i between 0 and m-1.
W: Prove that a congruent to b (mod m) iff m divides (a-b). Modular arithmetic: if a congruent to b, c congruent to d (mod m) then a+c congruent to b+d (mod m), same for -, *; as a corollary, we get a^n congruent to b^n (mod m) for any natural number n. Example of using modular arithmetic to compute remainders (mod 2, mod 6). Define greatest common divisor.
F: Discuss the Euclidean algorithm for computing gcd of m and n and prove why it works. Discuss the relationship between Euclidean algorithm and the problem of finding integer points on a line ax+by = c: these points exist iff gcd(a,b) divides c. Discuss the formula that computes all such integer point solutions.
Week 4
M: Use the Euclidean algorithm to gcd(145,40) (cont.) and applied theorem from last time to find all integer solutions to 145x + 40y = 10; proved that there are infinitely many primes.
W: Discussed two ways of denoting a set: set builder notation and roster notation. Gave several examples of defining sets using these notations and converting from one notation to the other. Defined the sets kZ where k is an integer and Z is the set of integers.
F: Defined basic set-theoretic operations: complement, union, intersection, set difference and proved basic facts about these operations. Gave examples illustrating these facts.
Week 5
M: Defined ordered pairs and defined the powerset operation. Defined 2-ary relations and functions (its domain, codomain, range). Properties of a function: one-to-one, onto, and bijection. Gave examples of various functions.
W: Defined inverse and composition of functions. Went over problem 3(b) from the practice midterm. Defined cardinality and what it means for |A| <= |B|, |A|=|B|, |A|<|B|. Gave an examples of sets A strict subset of B but |A| = |B|.
F: Midterm
Week 6
M: Gave examples of factorial and Fibonacci sequence; defined the proof by induction method; proved (by induction) that 1 + 2 + ... + n = n(n+1)/2 for all n >= 1.
W: Induction (cont.): showed that 6 divides n(n+1)(2n+1) for all natural numbers n; showed n! > 2^n for all n>= 4. Defined strong induction; started proving (using strong induction) the n-th Fibonacci number F_n = 1/sqrt(5) ( ((1+sqrt(5))/2)^n - ((1-sqrt(5))/2)^n).
F: More examples of proof by strong induction.
Week 7
M: Defined what it means for a subset A of R to be well-ordered; gave examples of well-ordered sets (N, finite sets) and non-well-ordered sets (Z,Q,R, [a,b), (a,b) etc); use the well-order of N to prove the "Principle of Induction"; gave an example of the "method of proof by minimum counterexample" (showed every n >= 7 can be written as 2a + 3b for some a,b>0).
W: Showed by minimum counterexample that 12 divides n^4-n^2 for all natural numbers n. Recalled the definition of AxB, P(A), cardinality of finite sets, |A| <= |B|. Proved that if |A| = m, |B|=n then |AxB| = mn.
F: Showed that if A is a subset of B then P(A) is a subset of P(B) and showed (proof by induction) that if A is a finite set, then |P(A)| = 2^|A|; defined indexed collections of sets (as well as unions and intersections of such collections) and gave examples of computing these operations on various collections of sets of reals.
Week 8
M: Went over various examples of computing intersections/unions of indexed collections of sets; defined the Cantor set.
W: Cantor set (cont.): showed that Cantor set is infinite, ternary representation, showed every element of the Cantor set has a ternary representation 0.a_1a_2... where the a_i's are either 0 or 2.
F: Reviewed on functions, relations, inverse of a function, discussed reflextive, symmetric, transitive relations and gave examples

Week 9
M: Holiday. No class.
W: Equivalence relations: definition, examples; defined equivalence classes and the corresponding quotient
F: Showed that an equivalence class on A gives rise to a partition on A and conversely, if (A_i : i in I) is a partition of A, then the relation: a R b iff for some i, a,b belongs to A_i is an equivalence relation and the equivalence classes of R are exactly the A_i's.
Week 10

M: Define the ring structure Z_n = (Z/R, +_n, ._n) where R is the congruence (mod n) relation; [a]_R +_n [b]_R = [a+b]_R and similarly for ._n; showed that these definitions are well-defined.
W: Continued with equivalence relations. Worked through the example of E_3, where xE_3 y if x=y(mod 3): calculated the equivalence classes of E_3, defined +, . on E_3 equivalence classes and showed these operations are well-defined. Stated (but not proved) a theorem that gives a sufficient condition for which f:XxX -> X induces a function f^*:X/ExX/E -> X/E.
F: Review for final; went over main points of the review sheet posted on the class website.