Math 2001 (Spring 2016)
Discrete Mathematics

There is an assignment due on Wednesday, 4/27.

Goals in this course

By the end of this semester, we will be able to...
  1. communicate mathematics effectively.
  2. speak fluently in the language of sets.
  3. recognize, understand, and apply methods of mathematical reasoning.
  4. approach new mathematics independently.
Please let me know about your goals for the course.

Textbook

The textbook for the course is

Book of proof, 2nd edition, by Richard Hammack

This book is available online for free. You can also purchase a hard copy: [Amazon] [Barnes and Noble] [CU Book Store]

Office hours

Office: Math 204
Phone: (303) 492-3018
e-mail: jonathan.wise@colorado.edu
Office hours: calendar

Assignments

I will assign problems regularly, but they will not be collected and will not be graded. However, working problems outside of class is absolutely essential to succeeding in this class. Sometimes in-class discussion, as well as quiz and exam problems, will be drawn from the homework problems I suggest, but for the most part you will have to supply the motivation to do homework.

For Wednesday, 4/27:

Working individually, submit a proof of the following statement:

Define An for all integers n ≥ 0 by the following process: A0 = 2; A1 = 5; for n ≥ 2, let An = 5 An-1 - 6 An-2. Prove that An = 2n + 3n for all integers n ≥ 0.

For Monday, 4/25:

Here is a statement you might like to try to prove by induction. You don't have to turn this in, but I'm happy to give you comments on your proof if you would like:

For every integer n there is an integer k such that n = 3k or n = 3k + 1 or n = 3k + 2.

If x, y, and m are integers then x2 + y2 ≠ 3m + 2.

This week, we will be working on Chapter 12. Please begin by reading §§12.1, 12.2, and 12.4. We will also discuss §§12.3 and 12.5 later in the week. Note that Definition 12.1 uses the concept of a relation, which we have not discussed in class; instead of "A function is a relation f ⊆ A × B..." you should read "A function is a subset f ⊆ A × B..."

The exercises in §12.1 are designed to make sure you understand the definition of a function, and the exercises in §12.4 are designed to make sure you understand the definition of composition. You should be able to do all of them. If you aren't sure how to do them, it is a sign that you need to understand the definitions in §12.1 and §12.4 better. I suggest doing at least 3 or 4 of the problems in each of these sections. Problem 12.1.5 refers to relations, so you may want to skip it.

In §12.2.2, you will need to write some proofs. Problems 12.2.1—12.2.3 are important to understand. Problems 12.2.4—12.2.8 are similar to one another, so doing one or two of these is enough; I suggest doing 12.2.8. Problems 12.2.9, 12.2.10, 12.2.12, and 12.2.13 are fairly similar; doing one or two is enough. Problems 12.2.11 and 12.2.14 are valuable because they involve the language of set theory in a more essential way than some of the other problems. Problems 12.2.15—12.2.17 are counting problems; they are less important for understanding functions, but could be good review. Problem 12.2.18 is not essential to do, but might be enjoyable.

For Friday, 4/22:

Here are sample proofs that every natural number is even or odd, using proof by smallest counterexample, proof by strong induction, and proof by induction.

For Wednesday, 4/20:

Working in the same groups, prove one of the statements you submitted on Monday.

For Monday, 4/18:

Read Chapter 10 up to an including §10.1 and §10.2 (pp. 154-167).

The first 13 problems are the most basic examples of induction, and you should make sure you can do them. Of course, once you can do a couple of them confidently you don't need to do the rest. I suggest doing 10.2 and 10.10. (Can you find a quick way to do 10.10 using 10.9?)

Questions 10.14—10.16 and 10.19—10.24 get more challenging, but you should be able to do some. I'd suggest 10.20 (problems 10.1 and 10.3 might help) and 10.21.

Working either individually or in groups of at most two, find at least three ways of rephrasing the sentence below:

For every k ∈ ℤ, there are no integers x and y such that x2 + y2 = 4k + 3.

For Monday, 4/11:

Read §§5.1, 6.1, 6.2. (Don't forget to read p. 111, even though it is not part of §6.1.) I suggest doing exercises 6.2, one of 6.3—6.4, 6.8, one of 6.10 or 6.11, 6.12 (I don't actually recommend doing proof by contradiction here), 6.14, 6.17, 6.18. (Problem 6.16 might be fun, but isn't particularly important.) The exercises in part 6.B are more difficult, but I suggest thinking at least about what you would need to do to prove these statements.

For Monday, 4/4:

Read §8.1—8.3. There are many good exercises in §8 (p. 145); please do a lot of them. Make sure to think carefully about what the statement is saying before you start trying to prove it. It is very important to show your work to others (like a classmate, tutor, or me) and discuss your proofs with them to make sure you have understood the statement to be proved and that you are expressing yourself clearly. It is normal at this stage not to feel entirely confident about what a proof should look like, or to be unsure about whether you have proved something. However, it is absolutely critical to recognize this kind of uncertainty now and discuss it with me immediately in order to prevent it from becoming a problem later.

I suggest doing Exercises 8.4 (this generalizes 8.1 and 8.3, which you may want to use as warmup), 8.5. Do a selection of Exercises 8.8—8.18, but once you feel confident with these, move on; they are a bit repetitive. Exercises 8.10 and 8.11 use the concept of a universal set, which we have not discussed, so feel free to skip it. I also suggest doing at least one of 8.19 and 8.20, at least one of 8.21 and 8.22, at least one of 8.26—8.28. The remaining exercises (8.29—8.31) aren't particularly important.

For Friday, 4/1:

Expect a quiz involving a proof.

You should also be doing practice problems from Chapter 4, in addition to the problems I gave in class. Problems 4.1—4.7, 4.10, 4.11, 4.17—4.19 should be of comparable difficulty to the problems I suggested. You will need to be able to do all of these easier problems. Problems 4.14—4.16 are good to consider, but they are similar, so there is no reason to do more than one of them; the book suggests doing these with a proof by cases, so you may want to wait until we have discussed that technique in class before attempting these. I don't suggest doing Problems 4.22, 4.23, 4.25. The remaining problems are a little more challenging, but please try them if you are comfortable with the other problems.

Make sure to think about what facts a reader needs to know to understand your proof!

For Friday, 3/18:

Either individually or in groups of 2, build an octahedron, dodecahedron, or icosahedron (using any materials you like) and compute the number of rotational symmetries of your construction. Write an explanation of why your calculation is correct.

For Wednesday, 3/16:

This week and the next we will be working on writing proofs. We will cover §§8.1—8.3 (which should at least partly feel like review), §4.3, and §5.1.

For Monday, 3/14:

There will be an hour-long quiz including questions from all areas we have discussed so far.

For Friday, 3/11:

We will continue discussing §§2.1—2.4 and §2.7.

For Wednesday, 3/9:

We will discuss §§2.1—2.4, 2.7.

For Friday, 3/4:

Please read §2.1 and §2.7. The important thing to get used to in §2.1 is the idea of a mathematical statement that depends on a variable. The exercises in §2.1 should be easy: if they are not, make sure you understand what a statement is, and talk to me if it is unclear. Do not, under any circumstances, do Exercise 2.1.15.

All of the exercises in §2.7 are reasonable, but I suggest doing #5—8 in particular. It is very important to do exercises that involve multiple quantifiers! You don't have to do every exercise in this section, but you should be able to do any of them.

For Wednesday, 3/2:

We will continue discussing §3.5; see below for exercise suggestions. A quiz is likely.

For Monday, 2/29:

Read §3.4 (this will actually be discussed on 2/26, but I forgot to make the assignment before class) and §3.5

Exercises 1—4 of §3.4 are good to make sure you understand what binomial coefficients are. Make sure you can do these easily. Exercises 5, 7, 9, and 11 are very similar; do one or two of them to make sure you can use the binomial theorem for more than just calculation. Exercise 6 might not be easy, but it is very important to understand: spend some time on it. Problems 8, 10, 12, and 13 are good practice with factorials; you should make sure you are able to do some of these, but it is okay if you are not able to solve all of them. Problem 14 is cute, and worth thinking about, but is not very important.

In §3.5, there are a lot of good counting problems, and it is good to practice with a handful of them. Do a few of 2—4 and 7—9. I recommend looking at Problems 5, since it might be a little more challenging, and 6, because it requires thinking about what makes inclusion-exclusion work. Problem 10 is a good one, but isn't particularly well suited (pardon the pun) to this section.

For Monday, 2/22:

Read §§3.2 and 3.3 of Hammack. See below for suggested exercises.

For Friday, 2/19:

Expect a quiz!

In the same groups as last time, answer the following question:

Question: If A and B are finite sets, what are the possibilities for |A ∩ B| in terms of |A| and |B|?

Your answer should be in the form of two theorems, with proofs. The theorems should look like this (you will have to figure out what the inequalities are):

Theorem 1. For any finite sets A and B, (some inequalities involving |A ∩ B|, |A|, and |B|) all hold.

Theorem 2. For any integers n, m, and l such that (some inequalities involving n, m, and l) all hold, there are sets A and B such that |A| = n and |B| = m and |A ∩ B| = l.

For Friday, 2/12:

Read Hammack, §3.3

In the same groups as last time, prove the following two statements:

Theorem 1. If A and B are finite sets then |A - B| ≥ 0 and |A - B| ≤ |A| and |A - B| ≥ |A| - |B|.

Theorem 2. If n, m, and l are integers such that l ≥ 0 and l ≤ n and l ≥ n - m then there are sets A and B such that |A| = n and |B| = m and |A - B| = l.

For Wednesday, 2/10:

Read Hammack, §3.2

Exercises #1, 2, 6, 9, and 10 are not particularly important for this class, although #9 is incredibly neat and important for other applications. It's really a calculus problem, though. Problem #6 is good practice in mathematical thinking. Problems #4—5 practice an important feature of the factorial that students often miss; make sure you understand these. Problems #3, 7, and 8 are all good counting problems, and you should do some of them.

For Monday, 2/8:

Read Hammack, §3.1 (we are skipping Chapter 2, at least for now)

The exercises in §3.1 are all great. Use some of problems #1—7 to get comfortable with these kinds of counting problems. I suggest looking #7d, 8, 9b: these might require a little more creativity. Problems #11 and 12 may be more challenging. In all of these problems, there are many ways to get a solution, so try to find more than one as a way to check your answer.

We will (finally) have a quiz covering new material from §1.8.

For Friday, 2/5:

Working in groups of 2 or 3, answer the following question:

If A is a set of size n and B is a set of size m, what are all possibilities for the size of A - B in terms of n and m?

Your answer should include a precise statement of the possibilities, a proof that your constraints on |A - B| are correct, and a proof that all numbers satisfying your constraints can occur as |A - B| for some sets A and B.

For Wednesday, 2/3:

Read Hammack, §1.7—1.8

The exercises in §1.7 are good practice to make sure you understand set operations, but they can be skipped if you find them easy. We will not discuss §1.7 in depth in class. Section §1.8 is very important; expect a quiz on it. All of the exercises in §1.8 are great practice. Exercise 10 is more challenging than the others; it's good practice, but less essential to be able to get it right now. Exercises 11—14 encourage the sort of thinking we want to do in this class, so make sure to try one or two of them.

For Wednesday, 1/27:

Read Hammack, §1.5

We didn't get to §1.5 in class on Monday, so we will discuss it on Wednesday. Take the opportunity to do a few more exercises, or go back to some of the more difficult exercises from earlier sections.

For Monday, 1/25:

Read Hammack, §1.5

In §1.5, you don't have to do every part of every exercise, but do enough to feel confident with all of the operations (union, intersection, difference); make sure to look at #3 and #4, since these mix multiple set operations. You should try one of Exercises #5-8, but they are all similar, so it isn't really necessary to do more than one. Exercises #9 and #10 are good; we will do a proof based on these ideas soon. Do not turn these in.

For Friday, 1/22:

Read Hammack, §1.3 and §1.4

It's very important to do some exercises here, in order to get used to using the set operations. In §1.4, warm up with #1-4, but be sure to do some of #5-12, since these involve multiple set operations and will help you practice. Make sure to do some of group B as well; #17-20 are trickier. Do not turn these in.

Submit a response to this poll.

For Wednesday, 1/20:

Read Hammack, §1.3; expect a quiz covering §1.1-3

Do some of the exercises from Part A of §1.3 to warm up to subsets; make sure to do at least one of #7 and #8, since these are trickier. All of the exercises from Parts B and C are worth thinking about, but make sure to do at least a couple from each group. #14, in particular, may be unintuitive. Do not turn these in.

Now is a good time to look back over some exercises from §1.1 and §1.2, since you may find those getting easier as your intuition about sets improves.

For Friday, 1/15:

Read Hammack, §1.2

Do some of the exercises from each part of §1.2. Make sure to try some of these trickier ones: A.1efgh, B.1efgh, 7, 8, 17, 18, 19, 20. Do not turn these in.

Working in groups of 2 or 3, submit a proof of the following statement:

If a, b, and c are any integers such that b is a multiple of a by an integer and c is a multiple of b by an integer then c is a multiple of a by an integer.

For Wednesday, 1/13:

Read Hammack, §1.1; there will be a quiz at the end of the lecture

Do a few exercises from each of the groups A, B, C, and D of §1.1; some of the later problems in parts A and D are a little more difficult. Do not turn these in.

Think about your goals for this class

Other materials

On Friday, April 8, we worked out the ideas of a proof, but didn't write the proof down formally. Here is a formal version of that proof.

On Monday, February 1, we wrote a draft proof [tex] [overleaf] of a statement about the possible sizes of unions of sets. On Wednesday, February 3, we improved it [tex] [overleaf] to make clear how the hypotheses of the theorem are used in the proof.

Assessment

The grading scheme is designed so that your final grade reflects the degree to which you have achieved the goals of the course. To that end, you will have two kinds of assessments over the course of the semester. There will be short answer questions and proof questions. The short answer questions are designed to test your understanding of specific mathematical concepts. In a proof question, you will be asked to write an explanation of why a particular statement is true. This will require you to combine aspects of your mathematical knoweldge and produce a readable and convincing argument.

Grading

Half of your final grade is based on writing, and half on understanding of mathematical concepts. The writing half is divided into reasoning and clarity in equal measure; the mathematical concepts are divided into a long list. All of these will be evaluated using a standards based system.

As the semester goes on, I will update a list of list of standards that will be assessed in the course. You will have multiple opportunities throughout the semester to demonstrate your mastery of each standard. Each time you attempt a standard, you will be given a score between 0 and 5 (with 5 reserved for truly exceptional work). At the end of the semester, I will average the highest half of your scores on each standard to compute your semester score in that standard, along with your scores on the final exam in that standard. Then I will average your semester scores in the different standards to get your final grade on mathematical concepts. The reasoning and clarity standards will each contribute 1/4 of your final grade; I anticipate that the remaining standards will count equally, but I may need to adjust this as the semester progresses.

Short questions will generally have a number of points between 0 and 4 available and be graded right or wrong; partial credit is possible but will be rare.

This page gives a rough guide to the significance of the numerical scores I will assign. However, I cannot promise this correspondence will be exact, since I may need to make adjustments as the semester goes on.

How to succeed in this course (and others)

Here are a few tips for making the most of this course:

Course policies

I will always be happy to excuse you from assignments or classes provided you have a reasonable excuse and you bring it to me in a timely way. If you have any concerns about the class, please let me know and I will do my best to allay them.

More specific information about accommodations for disabilities, religious observances, classroom behavior, discrimination and harassment, and the honor code is available from the university.