Mathematics 2001
Introduction to Discrete Mathematics
Fall 2015
A Venn Diagram
Course Description
- Official description:
Introduces the ideas of rigor and proof through an examination of basic set theory, quantification theory, elementary counting, discrete probability, and additional topics. Prereq., MATH 1300 or APPM 1350.
- My unofficial description:
This course covers the basic definitions of higher mathematics: sets, functions, and relations, and selected topics such as counting and graph theory. But the real focus is on mathematical literacy: the reading, and writing of mathematical definition and proof, and the indoctrination of the student into the culture of higher mathematics.
Course Particulars
-
See the syllabus for details.
- My office hours will be posted here when available. I am in office 308 in the math building.
Homework & Exams
- Tasks due Wednesday, August 26th:
- Read your syllabus.
- Find the textbook (Hammack, available online here) and read the Introduction.
- Read Section 1 up to the end of Section 1.1 of Hammack.
- Tasks due Friday, August 28th:
- View this two-minute video about sets and subsets.
- use the handout and this advice while re-reading Section 1.1 and reading Section 1.3 (we will come back to 1.2; there is only one small part where it matters to 1.3).
- Do some exercises from A,B,C for Section 1.1 (and a couple from D). They are all great exercises, so just start working through odd numbered ones (which have solutions in the back), until you can do them each in a minute or two (compare with the back). You can also do a few of the exercises of Section 1.3 now, particularly A and B.
- Tasks due Monday, August 31st:
- Read Section 1.2 of Hammack.
- Do a few problems from Section 1.2 (A and B).
- If you are not feeling solid on Sections 1.1 and 1.3, do some more problems there too.
- FYI: Monday we'll talk more about Cartesian products and also power sets (Section 1.4) if you feel like reading ahead.
- Tasks due Wednesday, September 2nd:
- Read Section 1.4, 1.5 and 1.6 of Hammack (they're all short).
- Do a few problems from Sec 1.4, A and B.
- Do a few problems from Sec 1.5. I think 1,3,5 are fine choices (answers in the back). Question 9 is a good one too.
- I suggest also Sec 1.6, problems 1 and 3.
- Notice Fact 1.4. It is possible to give a proof like the one we did in class today, using the basic counting principle I described. You might like to try this in preparation for class (where I will probably do it).
- Tasks due Friday, September 4th:
- Read Section 1.7 of Hammack (Venn Diagrams)
- Read Section 3 of Hammack up to the end of 3.1 (Counting Lists)
- Do some exercises for Section 1.7, as needed.
- Do exercises 1,3 from Section 3.1.
- Tasks due Monday, September 7th:
- Tasks due Wednesday, September 9th:
- This class will be the last chance to assess for the following topics, so please make sure you are prepared for them:
- Def: set, element, equality of sets, empty set, cardinality of set
- Def: set-builder notation and Z,N,R,Q, interval notation
- Def: ordered pair, n-tuple, Cartesian products and powers
- Def: subset, power set
- Read Section 3.2 of Hammack and do some exercises to familiarize yourself with it.
- Tasks due Friday, September 11th:
- Read Hammack, Chapter 4, until the end of 4.3. We will discuss this material in class and have our first proof-style assessment (instead of a short-answer question style quiz we've been doing). This chapter does depend a bit on notation from logic (Chapter 2), but you can look that up and we'll talk it over in class.
- Tasks due Monday, September 14th:
- Re-read Hammack Chapter 4, continuing on to finish the entire chapter.
- Try some of the proofs in Chapter 4 Exercises -- remember, there are solutions to odd numbers in the back! Try 1,3,5,7 at least. For each, carefully write it out like you did on the quiz, then compare to the proofs in the back and look carefully at the language of your proof and theirs. They don't have to be identical, but you should ponder the ways in which they differ and whether yours or the book's is better and why. Pay special attention to the language and the purpose it serves. Bring these practice proofs to class for in-class discussion.
- Tasks due Wednesday, September 16th:
- Try some more of the proofs in Chapter 4 Exercises. Remember that there are answers to odd ones in the back.
- Tasks due Friday, September 18th:
- In Wednesday's class we ran out of time to do the quiz. The quiz is here; please do it carefully at home (do it by yourself, please, not collaborating), and bring it to class to take it up all together.
- Tasks due Monday, September 21st:
- Read Chapter 8 up to the end of 8.3. This discusses proofs involving sets.
- Practice proofs! Do more of the example proofs from Chapter 4 and try some from Chapter 8. Work on them like you work on the quizzes: work hard to do it yourself. Then compare to the answers in the back (odd numbers). Hammack is FULL of example proof problems. Use them! Practicing with devotion is the only path.
- Tasks due Wednesday, September 23rd:
- Wednesday's quiz will be a chance to try a proof about sets. Re-read Chapter 8.1-8.3 and do exercises to prepare for the quiz.
- You should also do the worksheet problems from Monday's class; they are Hammack 8, 9 and 6. I will take these up at the beginning of next class, so if you have done them yourself, you will get much more benefit from doing that. You can also try the ones on the back (Section 2) -- copy of handout is here; I may have time to take up some of those too.
- Tasks due Friday, September 25th:
- You guys have been working hard on proofs, and maybe it's time for a change of pace! Please read Chapter 2 up to the end of Section 2.5.
- Tasks due Monday, September 28th:
- Please read Section 2.5 (repeat) and 2.6 of Hammack.
- Do exercises covering Sections 2.1--2.4 of Hammack (re-reading if necessary).
- Tasks due Wednesday, September 30th:
- Please read Chapter 3 up to the end of Section 3.2.
- Try a few Section 3.1 and 3.2 exercises.
- Tasks due Friday, October 2nd:
- Sorry, I never got around to assigning something because of my trip! :)
- Tasks due Monday, October 5th:
- Read Chapter 5 on Contrapositive proof and try some of your own. The quiz in class will be on a contrapositive proof.
- You might find this interesting. A quote: "We don't treat any other subject that way. I've never heard a student say, "I like 'Hamlet,' but I don't really belong in AP English -- that child who sits in the front row knows half the plays by heart, and he started reading Shakespeare when he was 7!" Basketball players don't quit just because one of their teammates outshines them. But I see promising young mathematicians quit every year because someone in their range of vision is "ahead" of them."
- Tasks due Wednesday, October 7th:
- ALERT: We will have the last quiz that will cover the following topics, i.e. last chance for these badges:
- union,intersection,difference
- universe, complement, Venn diagram
- cardinality of Cartesian product or power
- counting subsets
-
- Read Section 2.7 of Hammack
- Finish the front page of the worksheet from class, available here. You don't need to do the second page, but it is good practice if you like.
- Tasks due Friday, October 9th:
- Please read Chapter 2. You've read some of it before; it won't hurt to re-read it now. And some of the sections are new. Do exercises on any topic you are finding challenging.
- Tasks due Monday, October 12th:
- Please read/re-read Chapter 3 up to the end of 3.4. Do exercises on any aspect you find challenging.
- Tasks due Wednesday, October 14th:
- We will continue the worksheet on Wednesday and practice combinatorial proof, also with a quiz. So please work as far as Section 2, Problem 1 before you come to class Wednesday. The worksheet is available here.
- Tasks due Friday, October 16th:
- Ok, so the worksheet was still being useful on Wednesday and we put off the quiz again. Please come to class Friday having worked through as much of the worksheet as you can (at least Problem 4), and we will talk about it in class. The worksheet is available here, and solutions are available here.
- Tasks due Monday, October 19th:
- First, a note: I put a few scanned pages of a useful book on combinatorial proof up on D2L for you to use. It has many examples, although they are in a more terse format than we have been doing. You'll find it on the front page if you log in. It should fill some of the gap in our textbook on this.
- Second: We're going to move on back to more standard proof methods. Please read Chapter 6, up to the end of 6.1, about Proof by Contradiction, which we will talk about in class on Monday.
- Tasks due Wednesday, October 21st:
- Please read the rest of Chapter 6 for Wednesday.
- Tasks due Friday, October 23rd:
- I didn't tell you anything, sorry.
- Tasks due Monday, October 26th:
- Recall the proof about the sequence being increasing that we did in class. Try to rearrange the proof so it is not a proof by contradiction.
- Re-read Chapter 6 as needed, with exercises as needed.
- Read Chapter 7 up to the end of 7.2.
- Tasks due Wednesday, October 28th:
- Read Chapter 7.3 and 7.4.
- Do some exercises from Chapter 7.2.
- Tasks due Friday, October 30th:
- Do as many exercises from Chapter 7 as you like or need.
- Tasks due Monday, November 2nd:
- Finish the worksheet handed out in class, available here.
- Tasks due Wednesday, November 4th:
- Read Chapter 11 up to the end of 11.2
- Reading always means doing exercises as needed.
- We will finish the worksheet from Monday's class during class on Wednesday.
- Note: I will start up the badges quizzes again today. Review as necessary.
- Tasks due Friday, November 6th:
- I didn't get enough responses to the ANONYMOUS survey on D2L about how the class is going. It is easy, and it gives you a chance to say anything you want anonymously. Please log in to D2L and take it (link under NEWS on first page).
- Read 11.3 and 11.4.
- We will take up the badges quiz we just had.
- We will work on modular arithmetic and equivalence classes.
- There will be a badges quiz.
- Tasks due Monday, November 9th:
- Read 11.5.
- We will work on modular arithmetic and equivalence classes.
- There will be a badges quiz, LAST CHANCE for counting problems.
- Just an FYI: It's a good time in semester to know about SASC workshops.
- Tasks due Wednesday, November 11th:
- There will be no quiz today, so we have a bit more class time.
- Please finish reading and reviewing Chapter 11, including doing exercises.
- Tasks due Friday, November 13th:
- There will be a proof make-up quiz today. You can re-do ANY of the proof quizzes we've had so far to replace the corresponding grade. I will compile them into a single sheet, and you will choose one and write a good solution from scratch during the 10-minute window. The rules are:
- If you hand in a version of the proof not in your own words (e.g. my solution on the board or a solution found online, or your friend's solution), that is academic dishonesty, no matter how it happens (so don't memorize). So you must write in your own words. (I understand the limitation of this with regards to very formulaic proofs, but even so, no two student solutions ever agree by chance.)
- You may look at other people's correct solutions as part of your preparation, but it is to your benefit to follow these two rules: only seek help after you get stuck, and only enough to get you unstuck. You might also do this to compare to your own solution, but keep in mind if the proof differs, it doesn't necessarily mean yours was wrong! Also see the previous bullet point about academic honesty.
- Start reading Chapter 12 including 12.1 and 12.2.
- Tasks due Monday, November 16th:
- Badges Quiz Today. Today will be the LAST CHANCE for all logic-related topics.
- Read and do exercises from Chapter 12 up to the end of 12.2.
- Start reading 12.3 and 12.4.
- Tasks due Wednesday, November 18th:
- We will have a proofs quiz today. I will ask you to prove one (or part of one) of the following from your book:
- The Proposition from Example 11.8.
- Theorem 11.1.
- Suppose [a] and [b] are congruence classes, modulo n. Suppose a' is in [a] and b' is in [b]. Then [a'+b'] = [a + b]. (See Section 11.4.)
- Suppose [a] and [b] are congruence classes, modulo n. Suppose a' is in [a] and b' is in [b]. Then [a'b'] = [ab]. (See Section 11.4.)
- Do exercises from 12.4, and read 12.5.
- Tasks due Friday, November 20th:
- It's the Friday before break. We'll continue working in class on functions, but no quiz.
- Tasks due Monday, November 30th:
- Today we'll try to finish up functions, but may not finish pigeonhole principle.
- Please read all of Chapter 12 and do exercises as needed.
- There will be badges quiz with all the functions badges available.
- I have made some advice on the structure of the final exam available below.
- Tasks due Wednesday, December 2nd:
- Please come prepared to start induction by doing Section 1 of this worksheet, if you didn't do it on Friday before break. It's a game; you might want to get your roommate in on it and see if you can play it together and figure it out.
- It's been a long time since Friday before break; even if you were there, refresh your memory by figure it out the game again (see last point).
- Note: We will finish pigeonhole if needed today, then start induction.
- There will be a proof quiz. The task will be to prove that a function is injective and/or surjective.
- A particularly challenging example of this is to prove that a function with an inverse is bijective. I meant to do it in class but time is short, so I suggest you do it at home and then compare to my writeup. It is also good to study the proof that a composition of injective functions is injective, and a composition of surjective functions is surjective. Whenever you are reading a proof, stop after each sentence or equals sign and explain to yourself why that step was true.
- Tasks due Friday, December 4th:
- Just make sure you're caught up on everything listed for the previous class. I will give a badges quiz.
- Tasks due Monday, December 7th:
- There will be no quiz. Today we will practice induction.
- To be best prepared, you should read Chapter 10, up to the end of 10.1.
- Tasks due Wednesday, December 9th:
- Do some of the Exercises for Chapter 10. As usual, odd ones are best since you can compare to answers in the back. I suggest #5, #11, #19, #25 (look up what the Fibonacci sequence is), #33.
- Today there will be an induction quiz at the end of class.
- Tasks due Friday, December 11th:
- Today will be reserved for loose ends and review.
- Today will be the last badges quiz.
About the Final
My idea is to make the exam a lot like the quizzes, meaning both types. I may add some new types of short answer questions that combine knowledge from several different badges or require some synthesis.
I hate memorization, but you should absolutely be able to re-create (not regurgitate) a correct definition of things like injective and surjective. My view is that if you truly understand them, you are able to do this without memorization. I don't know if I'll ask you to write out the definitions -- I could -- but they will definitely be tested indirectly in such things as "prove blah is injective" or whatnot.
I've been asked about the relative importance of the various material. There's a sliding scale: I'll test the important concepts a lot, and I will test less important concepts less, but possibly some. You can judge importance by how much time and effort we've spent on various topics.
The reason I give definitions and propositions as tools in proof quizzes is to help you know what you can use without proof. You shouldn't assume they will be given.
My advice: at this point, focus on practising writing proofs, since this encompasses all other types of understanding.
Resources & Links
University Policies
