Math 109 Spring 2006
|| Lecture Time
|| Lecture Place
|Prof. Daniel Rogalski
|| F 12-1pm, M 2-3pm
|| MWF 11-11:50am
|| WLH 2207
Teaching Assistant 1:
|| Section Times
|| Section Place
| John Farina
|| AP&M 5018
|| M 1-2pm
|| M 6-6:50pm
|| HSS 2321
Teaching Assistant 2:
|| Section Times
|| Section Place
| Oded Yacobi
|| AP&M 2301
|| 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 #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