Math 109 Spring 2006

Instructors


Professor:


Name Office E-mail Phone Office Hours Lecture Time Lecture Place
Prof. Daniel Rogalski AP&M 5131 drogalsk@math.ucsd.edu 534-4421 F 12-1pm, M 2-3pm MWF 11-11:50am WLH 2207

Teaching Assistant 1:

Name Office E-mail Office Hours Section Times Section Place
John Farina AP&M 5018 jfarina@math.ucsd.edu M 1-2pm M 6-6:50pm HSS 2321

Teaching Assistant 2:

Name Office E-mail Office Hours Section Times Section Place
Oded Yacobi AP&M 2301 oyacobi@math.ucsd.edu Tu 11am-12pm M 7-7:50pm HSS 2321

General Course Information

Textbook: Foundations of Higher Mathematics, 3rd Edition, by Fletcher and Patty.

This course is intended to prepare you for the upper-division math courses required of math majors. In it, you will learn basic techniques of proof, along with some propositional logic and set theory. The basic theory will also be applied to interesting problems in number theory and combinatorics.

There will be 2 in-class midterms on Wed. 4/26/06 and Wed. 5/24/06, and a final exam on Mon 6/12/06 from 11:30am-2:30pm. No makeup exams will be given.

Homework assignments will be due weekly on Wednesdays in class. Late homework cannot be accepted.

The final grade will be determined as follows: Homework 25%, Midterms 25%, Final Exam 50%.

More detailed descriptions, including a tentative syllabus, may be found in the first day course handout here: Course syllabus
Check below for more up-to-date information about the schedule of homework and lectures.

Schedule of Lectures:

4/3/06. Introduction to Course. Propositions and truth tables. (1.1)
4/5/06. Expressions. Logical equivalence. Some number theory. Proved: if an integer n is odd, then n^2 is odd (direct proof). (1.2, 1.3, 1.4)
4/7/06. Quantifiers. Proved: an integer n is divisible by 9 if and only if the sum of the digits in n is divisible by 9 (direct proof). (1.3, 1.4)
4/10/06. Proofs by contrapositive and contradiction. 2^n is prime implies n is odd or n =2 (contrapositive). The square root of 2 is irrational (contradiction). Between any two rational numbers lie infinitely many other rational numbers (contradiction) (1.4)
4/12/06. Introduction to set theory. Sets, subsets, power set of a set. Intersection and union of sets. Simple identities about union and intersection. (2.1-2.2)
4/14/06. More set theory: Universe. Complement of a set. Number theory: The least-natural-number principle. Statement of the division algorithm. Using the division algorithm. (2.2, part of 3.2).
4/17/06. Proof of the division algorithm (3.2). More set theory: Indexed families and examples (2.3).
4/19/06. Proof by induction. Justification of proof by induction using the least-natural-number principle. First examples: Sum of the first n squares is equal to n(n+1)(2n+1)/6. 5^n - 2^n is a multiple of 3 for all natural numbers n. (3.1)
4/21/06. Variants of induction. Starting at a natural number different from 1. Proof that n^2 is less than or equal to 2^n for n at least 4. Strong induction. Proof that every natural number is a product of primes. Recursive definition. Definition of the Fibonacci numbers. (3.2-3.3)
4/24/06. Definition of gcd(a,b). An example of how to calculate it using the Euclidean algorithm. Proof that the Euclidean algorithm really does work to compute the gcd. (3.4)
4/26/06. EXAM I.
4/28/06. There exist integers x,y such that ax + by = gcd(a,b). Finding such x,y using the Euclidean algorithm. If p is prime and p divides ab, then p divides a or p divides b. (3.4, 3.5)
5/01/06. Proof of unique factorization into primes. Solving the equation ax + by = c in general. Applications to diophantine problems. (3.5)
5/03/06. Relations and equivalence relations. Equivalence classes. (4.1, 4.3)
5/05/06. Equivalence relations and partitions. (4.4)
5/08/06. Permutations and combinations. (6.1)
5/10/06. The Binomial theorem and Pascals triangle. (6.3)
5/12/06. The principle of exclusion and inclusion. (6.3)
5/15/06. Congruences. Basic properties. (4.5)
5/17/06. More on congruences. Fermat`s Little Theorem. Wilson`s Theorem. (4.5)
5/19/06. Functions, basic facts and terminology (5.1-5.2)
5/22/06. More on functions. Images and inverse Images. (5.6-5.7)
5/24/06. EXAM 2.
5/26/06. Recap of Exam. Introduction to cardinality of sets. (7.1)
5/31/06. Lemmas about countable sets. (7.4)
6/02/06. Q is countable. Examples of uncountable sets: the set of all N-indexed sequences of 0s and 1s is uncountable. R is uncountable. (7.4-7.5)
6/05/06. Introduction to Graph theory (6.4). The Konigsberg bridge problem. Finding walks in graphs which visit each edge exactly once.
6/07/06. More graph theory. Embedding graphs in the plane and the Euler formula.
6/09/06. Brief review of exam topics.
6/12/06. FINAL EXAM.

Homework Assignments and other handouts:

Homework #1, due 4/12/06

Homework #2, due 4/19/06
Homework Advice

Homework #3, due 4/28/06

Solutions to Exam #1 (includes exam)

Homework #4, due 5/03/06

Homework #5, due 5/10/06

Homework #6, due 5/17/06

Homework #7, due Friday 5/26/06

Solutions to Exam #2 (includes exam)

Homework #8, due Wednesday 6/7/06