*Math 187 Section 1: Discrete and Foundational Mathematics I.*

* *

**Instructor:** Andrés Caicedo.

**Contact Information:** See here.

**Time:** MTuWF 9:40-10:30 am.

**Place:** Mathematics/Geosciences building, Room 120.

**Office Hours: **MF 10:40-11:30 am.

**Text:** Scheinerman, *Mathematics: A Discrete Introduction, *Thomson (2006).

** **

**Contents:** From the Course Descriptions in the Department’s site:

An introduction to the language and methods of reasoning used throughout mathematics and computer science, and to selected topics in discrete mathematics. Propositional and predicate logic; elementary set theory; introduction to proof techniques including mathematical induction; functions and relations; and basic principles of elementary number theory, combinatorial enumeration, and graph theory.

There are two components to this course. First, you will learn some topics in discrete mathematics (for example, counting techniques, a bit of graph theory, and number theory). Just as important, in this course you will learn how to *read* (and hopefully, understand) mathematical arguments, and how to *write* mathematical proofs. Ideally, at the end of the course you will be able to produce a few proofs of your own.

We will cover different topics from the textbook, with varying degrees of emphasis. We may cover additional topics not in the textbook. Appropriate references will be given in that case; if needed, notes will be posted on this blog. This page will be frequently updated with detailed week-to-week descriptions, including homework assignments.

**Detailed week to week description:**

- January 19-22. Introduction. We begin by covering material from Chapter 1, with additional examples.
*Homework problems:*From the textbook, exercises 2.1, 2.2., 2.6, 2.7, 2.8, 2.9, 3.1, 3.2, 3.6, 3.7, 3.8. - January 25-29. Definitions, proofs.
*Homework problems:*From the textbook, exercises 4.1, 4.5, 4.7, 4.13. - February 1-5. Counterexamples (section 5), sets (section 9).
*Homework problems:*From the textbook, exercises 5.4, 5.6, 5.9, Chapter 1 self-test 10, 11, 15, 18, 9.1, 9.2, 9.5, 9.6, 9.10. - February 8-12. Sections 7, 9, 11.
*Homework problems:*From the textbook, exercises 7.4, 7.7, 7.9, 7.12, 7.14, 9.3, 11.1, 11.3, 11.5, 11.17. Recall that the first midterm is next week, on**Wednesday**, February 17. This homework is due Wednesday. I will have office hours on Tuesday at 10:40-11:30. - February 16-19. Section 10.
*Homework problems:*From the textbook, exercises 10.1, 10.2, 10.3, 10.4, 10.6. - February 22-26. Section 13.
*Homework problems:*Self-referential test (let me know if you need a copy). - March 1-5. Section 14.
*Homework problems:*14.1, 14.2, 14.5, 14.8, 14.13, 15.1. Prove the very important property of equivalence relations: The collection of equivalence classes of an equivalence relation on a set forms a partition the set (into pairwise disjoint non-empty subsets). - March 8-12. Sections 20, 21.
*Homework problems:*20.1, 20.2, 20.3, 20.6, 20.7, 21.3, 21.4. - March 15-19. Sections 21, 34.
*Homework problems:*21.6, 21.7, 21.8, 34.1, 34.2. Recall that the second midterm is**Tuesday, March 23**. - March 22-26. Sections 35, 23.
*Homework problems:*34.9, 35.1, 35.2, 35.3, 35.8, 35.11, 35.12, 35.13, 35.14, 23.1, 23.9, 23.11, 23.12, 23.13, 23.14, 23.15. - April 5-9. Sections 24.
*Homework problems:*24.1, 24.2, 24.4, 24.7, 24.9. - April 12-16. Section 36.
*Homework Problems:*36.1, 36.2, 36.3, 36.5, 36.10. (In 36.1.e, the answer is 6, according to the definition given in lecture of the elements of as equivalence classes, but not according to the book’s version of things; see the comment by R. Yingling below.) - April 19-23. Section 46.
*Homework Problems:*46.1-8, 46.16, 46.18. - April 26-May 7. Sections 47 (especially exercise 47.10 on Ramsey theory) and 49 (on trees).

**Prerequisites:** Math 143, Math 147, or satisfactory placement score.

**Quizzes:** There will be weekly quizzes, on the last 20 minutes of Tuesday’s lecture (not on January 19). Each quiz will evaluate, roughly, the material covered the last week. You are * not *allowed to only show up about 20 minutes before the end of the lecture in order to take the quiz; if you show up only for the quiz, your score is 0. If you fail to take a quiz, it will be scored as 0. The lowest score will be dropped. Grading of a quiz or midterm depends on whether you have turned in the corresponding homework, see below.

For each quiz, I will provide you with a page with the question(s) printed. You may use this page to solve the questions. You need to bring any additional pieces of paper you may require. If a quiz will require more than 20 minutes, I will inform in advance, both in lecture and in this page.

*Notes from class, textbooks, and calculators, are allowed during exams and quizzes. Bring your own pen, pencil, eraser, etc.*

**Homework: **There is weekly homework, due Tuesdays at the beginning of lecture; you are welcome to turn in your homework early, but I will not accept homework past Tuesdays at 9:40 am. The homework covers the material from the previous week, and it is a good idea to work daily on the homework problems corresponding to the material covered that day. Typically, I will not grade the homework. You should use it as a guide for what material to focus on, and what kind of skills are required from you. It is a **very good** idea to do **all** of the assigned homework. During office hours, you are welcome to ask about problems from the assigned sets (or any other problems you find interesting). Frequently, some (but not necessarily all) of the problems from the quizzes will be fairly close, if not outright identical, to homework problems. Each week I will randomly select two or three problems from the due set. Your quiz or midterm will be scored 0 unless the homework you turned in includes all these problems.

Some weeks, I may assign problems that I consider particularly important or relevant to the topic being covered, and those will be graded. I will let you know in advance whether a specific homework set will be graded.

Following Otis Kenny‘s suggestion, your homework must follow the format developed by the mathematics department at Harvey Mudd College. You will find that format at this link. If you do not use this style, your quiz or midterm for that week’s homework will be graded as 0, and if that week’s homework was to be graded, yours will be graded 0 as well.

**Exams:** There will be 2 in-class exams and a comprehensive final exam.

- Exam 1: Wednesday, February 17.
- Exam 2: Tuesday, March 23.
- Final exam: Monday, May 10. 10:30 am-12:30 pm. This exam is cumulative.

Dates and times are non-negotiable. Failure to take a exam will be graded as a score of 0. There will be no make up for the final exam. For the in-class exams, a make up can be arranged if I am notified prior to the exam date and a valid reason is presented; keep in mind that make up exams will be more difficult than regular in-class exams.

You need to bring blue books to the exams.

**Grading:**

- Quizzes: 40%. (Each quiz weighs the same towards the final grade.)
- Exam 1: 20%.
- Exam 2: 20%.
- Final exam: 20%.

**[Updated, April 29, 2010:] **

**1.** There were 11 quizzes. Each quiz was graded out of 5 points (there were some extra credit points built in in some quizzes, so you may have scored higher than 5 sometimes). If you turned in the self-referential test, and your score was higher than your score in quiz 4, then this new score replaces what you obtained for quiz 4. Remove the 3 lowest scores, and add the other 8, for a number that represents **40%** of your total score.

However, if you turned in any extra credit problems (remember that the deadline is **Friday, May 7**, during lecture), they will be used to replace your lowest scores in the remaining 8 quizzes (before you add), and then, if there are still any additional points left, they will be added directly to your 40% score.

**2.** There were 2 midterms, each worth 20% of your total score. The highest of the two scores should be counted twice. This gives you another **40%** of your total score.

**3.** The remaining 20% is the score in the final exam.

Your grade is then determined by a linear scale:

- If your final score is 90 or higher, you receive an A.
- If it is 80 or higher, you receive at least a B.
- If it is 70 or higher, you receive at least a C.
- If it is 60 or higher, you receive a D.
- There will be a curve at the end (which may increase your grade, never decrease it), and plus and minus grades might be used for grades near the top or bottom of a grade range.

**Attendance:** Not required, but encouraged. Any material covered in lecture, or assigned as homework, may be used in quizzes and exams, even if it is not discussed in the textbook. I will use this website to post any additional information, and encourage you to use the comments feature, but (in general) I will not post here standard content covered in the textbook and in class. If you leave a comment, please use your **full name**, which will simplify my life filtering spam out.

Regarding 36.1e: In Def 36.1 (page 310), the author states that, for a+b (in Z_n), a and b must both be elements of Z_n. Since 12 is not an element of Z_10 (because 12 > n-1 = 9), I believe the author means that 12+4 (in Z_10) is undefined? (Then the same would be true for 36.1m)

Hmm… Yes, that’s it, you are right. Thanks!

But in lecture I defined in a way that all these sums make sense, by identifying and whenever , wich is really how should be understood. Sometimes the book’s conventions are bizarre… Anyway, following our convention the sum makes sense, and following the book’s it does not.