Department of Mathematics University of San FranciscoMathematics 300Introduction to Formal MethodsSpring 2007MWF 11:35–12:40, HR 509Professor: Peter PachecoOffice: Harney 540Phone: 422-6630Email: user: peter, domain: math.usfca.eduOffice Hours: MWF 1:30-2:30 pm, and by appointment.Prerequisites: Math 110, Calculus and Analytic Geometry II, or permission of instructor.Text: Peter Fletcher and C. Wayne Patty, Foundations of Higher Mathematics, 3rd ed., Brooks/Cole,1996.Class Website: http://math.usfca.edu/peter/math300Class Mailing List: You should subscribe to the class mailing list, since important announcementsare posted to it — e.g., homework assignments and changes to assignments.To subscribe, go to the website https://math.usfca.edu/mailman/listinfo/math300 andtype in your preferred email address. You’ll be sent a confirmation email by the list. In order tocomplete the subscription, you must reply to this email.After subscribing, you can post messages by sending email to user math300 in domain math.usfca.edu.Coursework and Grades: I will base your final grade on 11 homework assignments, 3 midterms,and a final exam, weighted as follows.Homework 11 @ 2% 22%Midterms 3 @ 16% 48%Final Exam 30%Total 100%I will assign grades on a straight scale. Roughly, 90-100% is an A, 80-89% is a B, 65-79% is aC, 55-64% is a D, and 0-54% is an F.Homework: Most days I’ll assign homework, and the homework assigned on one day will bedue at the beginning of the following class. In general, the homework assigned on Wednesday,Friday, and Monday and collected on Friday, Monday, and Wednesday, respectively, will countas a single assignment. See the following course outline for details. In all, there will be 13homework assignments, but your two lowest homework scores will be dropped. Late homeworkwill not be acc epted.Midterms: The midterms will be given in class on Friday, February 23, Wednesday, April4, and Friday, May 4. They are closed book, closed notes.Final Exam: The final exam is comprehensive. It will be given on1Wednesday, May 16 at noon.It is also closed book, closed notes.Participation: It’s also possible to get extra credit by participating in class. I’ll award 1point of extra credit (up to a maximum of 5 points) for each “good” question that you ask oranswer. I’ll be the sole judge of whether a question or answer is good or not, but in generala good answer requires more than routine calculation, and a good question helps clarify thematerial for the rest of the class. If I tell you that you’ve received a point, please remind meafter class.Attendance and Lateness: There is no attendance requirement. However, if you miss a classyou will still be responsible for all the material covered. Being late to class is unacceptable. Youmay have one unexcused late arrival. Subsequent late arrivals may affect your grade.Academic Honesty: I encourage you to discuss homework with your classmates. However, youmust write up your homework completely on your own. Any collaboration beyond discuss ion ofhomework is unacceptable. In particular copying another person’s work is unacceptable. Studentswho violate these rules will receive an F in the course. Repeat violators may be subject to moresevere penalties.Learning Outcomes: In this course students will learn aspects of basic logic, set theory, math-ematical proof. In particular, after completing this course, the student will be familiar with thefollowing topics.1. Truth tables, logic, and quantifiers.2. Methods of mathematical proof.3. Definitions and theorems in basic set theory.4. Proof using mathematical induction.5. Relations, equivalence relations, and partial orders.6. Functions.7. Finite and infinite sets.2Tentative Course OutlineWeek Material1/22–1/26 Preliminaries. Logic: propositions, expressions.1/29–2/2 Quantifiers, methods of proof.Homework 1: problems assigned prior to 1/31.2/5–2/9 Proof by contradiction, element chasing.Homework 2: problems assigned 1/31 through 2/5.2/12–2/16 Sets, set operations, indexed families.Homework 3: problems assigned 2/7 through 2/12 .2/19–2/23 Axiomatic set theory, mathematical induction.Homework 4: problems assigned 2/14 through 2/16 .Midterm 1, Friday, 2/23.2/26–3/2 More on induction, recursion.Homework 5: problems assigned 2/21 through 2/26.3/5–3/9 The division a lgorithm and basic number theory.Homework 6: problems assigned 2/28 through 3/5.3/19–3/23 Relations, graphs, equivalence relations.Homework 7: problems assigned 3/7 through 3/19.3/26–3/30 Partitions, congruence, composition, orders.Homework 8: problems assigned 3/21 through 3/26.4/2–4/6 Functions and relations, permutations.Midterm 2, Wednesday, 4/4.4/9–4/13 Functions and partitions, real-valued functions.Homework 9: problems assigned 3/28 through 4/9.4/16–4/20 Image, inverse image, functions and indexed families.Homework 10: problems assigned 4/11 through 4/16.4/23–4/27 Finite and infinite sets, Schroeder-Bernstein theorem.Homework 11: problems assigned 4/18 through 4/23.4/30–5/4 Well-ordering, axiom of choice.Homework 12: problems assigned 4/25 through 4/30.Midterm 3, Friday, 5/4.5/7–5/10 Countable and uncountable sets.Homework 12: problems assigned 5/2 through