## Math 2001: Discrete Mathematics Spring 2014

Last revised: February 14, 2014 at 6:43pm

 Instructor Jonathan Wise Office Math 204 Office hours T 10-11am, W 1-2pm, Th 3-4pm (or by appointment) e-mail jonathan.wise@math.colorado.edu Phone (303) 492 3018 Course website math.colorado.edu/~jonathan.wise/math2001 Classroom FLMG 103 Class time MWF, 10–11am Textbook Scheinerman, Mathematics: A discrete introduction, 3rd Edition Midterm 1 Thursday, February 13, KOBL 220, 7-8:30pm Midterm 2 Thursday, March 20, KOBL 220, 7-8:30pm Final exam Saturday, May 3, FLMG 103, 4:30–7pm

### 1 What is Math 2001?

This course has two broad goals: The first is to teach you the subject, discrete mathematics, and we will return to this in a moment. The second goal may be more important: It is to teach you to think and communicate mathematically.

What does it mean to think and communicate mathematically? It doesn’t have anything to do with being able to read equations or picture the quadratic formula when you close your eyes. Above all, thinking mathematically means thinking precisely. Communicating mathematiclly means making clear statements and justifying them with irrefutable logic.

The sort of thinking you will be expected to do in this class may feel very different from the sort you have done in math classes before this one. The sudden change in perspective may be jarring. Please be prepared for it! Don’t expect to be able to solve each problem by applying a procedure from that week’s lecture; may problems will require that you discover the method yourself, and it may take time to get used to doing this. Remember that presenting your solutions well—the communication aspect of the course—is as important as finding them in the first place; set time aside for preparing your presentation. More suggestions along these lines are in Section 3.

The particular topic with which we will be developing our mathematical thinking is called “Discrete Mathematics”. The name is meant to distinguish the subject from more “continuous” subjects, like calculus—or “Real Analysis”, as it is called when taught in a mathematically rigorous way in this class’s sister, Math 3001. In fact, this course will consist of a brief introduction to a number of “non-continuous” mathematical topics:

1.
logic (the formalization of mathematical reasoning),
2.
combinatorics (the theory of counting),
3.
set theory (the study of collections of mathematical objects, and the foundation for almost all contemporary mathematics),
4.
probability (analysis of the relative likelihood of different events in repeated experiments), and
5.
number theory (the study of numbers and their properties).

We will cover the fundamental facts from these subjects that are used throughout mathematics. I hope that you will also get enough of a taste of these topics to find some exciting and continue studying them in other classes.

### 2 Textbook

The textbook for the course is

Edward Scheinerman, Mathematics: A discrete introduction, 3rd Edition. Brooks/Cole. ISBN-10: 0-8400-4942-0. ISBN-13: 978-0-8400-4942-1.

You can also use the second edition at your own risk. I have not been able to find a substantial difference between the second edition and the third except in the exercises and the numbering of the sections. If you plan to use the second edition, you should make sure to get access to the table of contents and exercises from the third edition.1

### 3 How to do well in this course

Math 2001 will probably be unlike math classes you have taken before. You will not be tested on your ability to learn and apply procedures and you will only be examined minimally on your capacity to perform calculations. Rather, you will be expected to absorb and understand mathematical concepts, as well as to develop relationships between them independently. You will be evaluated not only on the quality of your ideas, but also on your ability to explain them clearly.

In addition to the suggestions below, you can find some useful homework strategies here:

The following math study suggestions are also very good:

#### Persistence

You should expect to spend some time being stuck on a problem before you solve it. You should expect your first—or your first several—attempts to solve it to fail. This isn’t wasted time or energy: each misstep improves your understanding and helps to prepare you for the next problem.

#### Do the reading

When you read mathematics, you should have a pen (or pencil) in your hand and a notebook beside your textbook. When you encounter a statement that you do not fully understand, work through it in your notebook until you do.

#### Understand what you don’t understand

Finding a solution to a mathematical problem can be difficult. But it is much easier to tell if a solution is correct. Being able to tell if your—or someone else’s—solution is correct is a basic skill you will need to succeed in this course.

If you can’t tell if your solution to a problem is correct, it is very likely you haven’t understood the concepts the problem is testing. Stop working on the problem and spend some time studying the concepts it is examining.

You should learn to create examples to test your own understanding. Can you apply a concept in a novel situation? If not, you haven’t understood the concept yet.

#### Learn the ideas, not the procedures

What does it mean to study concepts? It means learning the relationships between mathematical ideas and the reasons those relationships hold. It also means gaining an intuitive understanding of those mathematical ideas so that you can predict new relationships and prove or disprove your predictions.

In other math classes, you may have learned algorithms that give answers to certain kinds of problems in a systematic way. For example, we all learned algorithms for multiplying and dividing natural numbers in elementary school. In this class, we will be more interested in questions like why these algorithms work.2

Studying mathematical concepts is an active process. You have to struggle with them, push them and prod them, until you get a sense of their shape and meaning. Try substituting values for the variables and see what the statement means in a special case. Try to find a counterexample to see why the hypotheses are necessary.

Many more suggestions can be found here:

#### Have fun

Math is fun. If you aren’t having fun, you aren’t doing it right. I mean this quite seriously. If you aren’t enjoying yourself, you should come talk to me.

### 4 Course goals

I have divided our goals for this course into primary and secondary goals. The first group consists of basic skills that will be necessary to pass the course and the second group contains skills that are necessary to get an ‘A’. 3

The lists below are not a complete list of all topics that will be covered in the course; they are not a list of topics that will be covered on the final; mastering every item on the list will not guarantee you an ‘A’. You should not use these items as a study list. Rather, the following is a list of topics we will cover that you may be expected to know in future math classes, and the course will be designed to encourage you to assimilate these into your long term understanding.

#### Primary goals

Without mastering these skills, it won’t be possible to learn much in subsequent math courses, or even in this one. You will not pass the course if you do not master these skills!

1.
Distinguish between well-formed mathematical statements and nonsense.
2.
Parse the meaning of a mathematical statement and test its validity.
3.
Determine whether a mathematical object satisfies the requirements of a definition and explain your conclusion in complete sentences.
4.
Understand the meaning of mathematical quantification (“for all”, “there exists”) and the significance of the order of quantification.

#### Secondary goals

The following are fundamental ideas, skills, and techniques used throughout mathematics. It will not be possible to get an ‘A’ in the class without mastering all of these skills!

1.
Learn the standard notation and nomenclature of mathematics. This includes (but isn’t limited to) the following symbols:

and the phrases

for all, there exists, implies, we are reduced to showing, without loss of generality

as well as various synonyms. Be able to understand these symbols when you read them and be able to use them in your own writing.

2.
Master mathematical induction, in all of its forms. Be able to understand when it is used correctly and be able to use it correctly in your own proofs.
3.
Set theory:
(a)
Understand what a set is and how to determine whether two sets are the same. Don’t get confused about the empty set, the set containing the empty set, etc. Be comfortable with sets whose elements are abstract objects, not just numbers.
(b)
Know and be able to use the basic operations on sets: union, intersection, product, difference.
(c)
Know the definitions of relations, functions, equivalence relations, partial orders, total orders and how they are connected to one another. Be very comfortable with functions and the notions of injectivity, surjectivity, bijectivity.
4.
Combinatorics:
(a)
Be comfortable counting mathematical objects by producing a bijection of sets.
(b)
Understand binomial coefficients and factorial and know what they count. Be able to express the numbers of other objects using these quantities.
5.
Probability:
(a)
Understand the concept of independence and apply it to the calculation of probabilities. Do not fall for the gambler’s fallacy.
6.
Number theory:
(a)
Know the meaning of congruence modulo a modulus. Be able to compute in modular arithmetic, solve congruences, and prove properties of modular operations.
(b)
Be able to use the unique factorization into primes.

### 5 Evaluation

Your final grade will be based on homework assignments, in-class quizzes, two mid-term exams (held outside of class), and one final, according to the following table:

 HW 20% daily Quizzes 10% daily Best midterm 22% February 13 / March 20 Worst midterm 18% February 13 / March 20 Final 30% Saturday, 3 May, 4:30–7pm

In this calculation, your lowest seven homework and quiz scores will be dropped. Grades will not be curved to a standard distribution, unless exceptional circumstances require it. If you are interested to know how the final grades will be calculated, see the discussion in Section 5.4.

Warning: Problems on the exams are not guaranteed to be “like the problems on the homework”. Expect the exam problems to test the same ideas that the homework problems do, but in novel ways.

#### 5.1 Homework assignments

##### Submitting your assignment

Homework is assigned with every lecture and collected at the beginning of the subsequent lecture. Assignments may also be submitted by e-mail, provided that (i) they are in a single PDF file, less than 5 megabytes in size, (ii) they arrive in my inbox by the beginning of class, and (iii) the title of the e-mail begins with “[MATH2001] ASSIGNMENT n” (no quotes), where n should be replaced by the number of the assignment. Assignments submitted by e-mail will not be accepted unless they meet these criteria.

Homework assignments will be available online at least a week before they are due, but unforeseen circumstances (falling behind in lecture, for example) may sometimes force me to modify the assignments in the lecture immediately preceding the due date. Watch your e-mail, check the course website, and make sure you are working on the right assignment.

##### Preparing your assignment

The better half of mathematics is communication, and learning to communicate mathematical ideas effectively is an essential component of this course. Unless indicated otherwise in the assignment, your homework must be written in complete English sentences. Homework that is not written in complete sentences will not be graded and will receive a zero. If you have difficulty writing in English, you should contact me about this early in the semester.

Unless otherwise specified, all solutions must be justified. That is, you must give a mathematical argument or proof of the validity of any assertion you make. There will be some problems in this course whose solutions do not require justification, but these will be clearly marked as such.

You will be graded not only on the correctness of your answers, but also on their clarity. One simple way to improve the clarity of your writing is to type your solutions. While there are many ways to typeset mathematics on a computer, LATEX is almost universally preferred by mathematicians. You are not required to learn LATEX for this course, but I strongly encourage it. Not only will it improve the quality of your work, but you will find it a great asset should you decide to continue in mathematics or a related field.

##### Collaboration and assistance

You are allowed—and encouraged!—to discuss your assignments with anyone you like, including other students in the class, tutors, the internet, etc. However, this policy comes with two caveats: First, it is your responsibility to use only those means of assistance through which you learn, and second, you must cite any references you use clearly on your homework (including URLs, friends’ names, and books, with page numbers).

You are not allowed to let someone else do your homework for you (nor are you allowed to do someone else’s homework). What you submit on your homework must reflect your own understanding and only your own understanding. You must write your homework solutions independently, in your own words, using only your textbook and course notes as a reference. You may not consult another person’s assignment while preparing your solution and you may not consult notes you took while discussing the assignment with someone else.

This means that you can work on the problems with anyone you like, but you may not use anything from the discussion except your newly improved brain.

If you do meet with a tutor, make sure to educate him or her about this policy: not all tutors are cognizant of the rules of the courses they tutor for, and it is you, not they, who bear the responsibility of following the rules.

I do not want this policy to be misunderstood, so if you have find it in any way unclear, you should ask me about it. Do not assume that because a limited form of collaboration is allowed that all forms are allowed. The purpose is to allow you to improve your understanding through discussion. It is simply to help you get a better grade. Do not abuse this privilege.4

##### The Mathematics Resource Center (Help Lab)

The Mathematics Resource Center is a good place to meet other students and talk about math, including about Math 2001. There are graduate student tutors available to talk about many courses, but not about Math 2001.

#### 5.2 Quizzes

There will be daily reading quizzes.5 You are not expected to get a perfect score! The purpose of the quizzes is to help both you and me to discover what you understand and what you don’t understand. I will use this information to guide the discussion in class. If you get a perfect score on everything, we won’t get any useful information!

#### 5.3 Exams

The two midterm exams will be held on February 13 and March 20, from 7pm until 8:30pm. The final exam is on May 3. Greater weight will be given to the higher of your two midterm scores. Absence from any of the exams will be excused, and alternate accomodations made, only with a note from an appropriate authority specifically excusing you from the exam.

See Section 8 if you require special accomodations for exams.

#### 5.4 How the final grade distribution will be determined

On each exam problem, I will estimate the score on that problem that I would expect a typical ‘A’ student to get, the score I would expect a typical ‘B’ student to get, and the score I would expect a typical ‘C’ student to get. I will tabulate all of these scores, over the course of the semester, to arrive at the final numerical grades I would expect to deserve an ‘A’, ‘B’, or ‘C’. I will then compare your numerical score to this calculation and assign your grade accordingly.

### 6 Attendance

Attendance is not mandatory, but there are daily homework assignments and quizzes on the reading that you will miss if you do not attend. To compensate for justifiable absences, the lowest seven quizzes and homework assignments will be dropped. Any further absences, including a missed exam, will be excused only when accompanied with a note from a doctor or the Office of the Dean of Students. The note must specifically excuse your absence.

If you are ill and potentially contagious, you should not attend class. Your classmates—and I—will thank you.

I strongly discourage attending a different section of Math 2001 from the one you are enrolled in. The different sections are not coordinated and will not cover identical material.

### 7 Office hours and e-mail

At least for the first few weeks of the semester, my office hours will arranged by appointment only. This will give me a chance to find out what times are convenient for you and set my scheduled office hours accordingly.

If you wish to meet me privately, please let me know that when you ask to meet; otherwise I may schedule multiple meetings at the same time. I have a limited amount of time for meetings each week, so if you need to speak to me urgently, please contact me about it promptly.

When you contact me by e-mail, please help me not to miss your e-mail by including “[MATH2001]” at the beginning of the subject line.

### 8 Conflicts, rules, regulations, and special needs

If any conflicts or other issues come up, or you feel uncomfortable in class for any reason—academic or otherwise—please let me know. I will do what I can to resolve the issue. Some of the things that come up most frequently are conflicts due to religious observance, accommodations for disabilities, and requests to be addressed by a different name or pronoun. I hope you will feel comfortable coming to me if these or any other issues arise.

The earlier you come to me, the easier it will be for me to help. I won’t ask for specific information about your request unless it is necessary.

You can read more about the official university policies on these and related topics here:

Of course, those policies will be respected in this course. Please note that in order to provide special accommodations for a disability I will need to have a letter from disability services explaining what accommodations are appropriate. This letter may take time to procure, so please contact Disability Services early if you may qualify for special accommodations.

1Unfortunately, it appears that copyright law prohibits me from making copies of these for you.

2As a fun exercise, you can think about why the multiplication algorithm works. Hint: the distributive property. We will talk about the division algorithm when we get to the number theory component of the course.

3I have used the word “necessary” in its mathematical sense here. It is necessary to master the secondary goals to pass, but it is not sufficient. In other words, it will not be possible to pass without achieving all of the primary goals, but achieving the primary goals is not a guarantee that you will pass.

4Parts of the text of this section were adapted with permission from the section “Course Policy on Homework Help” of Katherine Stange’s syllabus for Math 4440 (pp. 3–4), available online:

5If the technology cooperates, the quizzes will be administered using clickers.