Math 2001: Fall 2016

Questions

Do you have a question or comment about the course? The answer might be in the course policies. If your question isn't answered in the course policies, please send me an email.

Office hours

My office is Room 204 in the Math Department. My office hours often change, so I maintain a calendar showing the times I will be available. I am often in my office outside of those hours, and I'll be happy to answer questions if you drop by outside of office hours, provided I am not busy with something else. I am also happy to make an appointment if my office hours are not convenient for you.

Syllabus

Before the semester begins...

Goals: become familiar with the course policies

Reading: course policies

Due Monday, August 22: Please fill out this survey. This is not graded, but it is required!

Part 1: Mathematical statements

Goals: make precise mathematical statements; start learning to read mathematics

Reading: Book of proof, з2.1Ч2.4 (pp. 33-46), з2.7. There are occasional mentions of sets in the reading; for the most part, you can ignore these right now, but you may find it possible to understand some of them if you reinterpret x ∈ ℤ to mean "x is an integer" and x ∈ ℕ to mean "x is a positive integer".

Recommended exercises (important exercises in bold): з2.1, #1-3, 7, 9, 11-13; з2.2, 1-5, 6, 7, 8, 14; з2.3, 1-13; з2.4, 1-5. The exercises in з2.3 and з2.4 are particularly important. They ask you to rephrase mathematical statements, which will be a fundamental skill when we need to find the right form of a statement to prove.

Activity, Monday, August 22: Exploration 1

Suggestions for successful communication. These are broad techniques that you can try to apply in discussions, in lecture, when reader, when writing, or in any other situation where you need to communicate mathematically (and maybe also non-mathematically).

Due Wednesday, August 24: Pick a game or sport that you enjoy and carefully explain its rules. Your explanation should be a page or less in length. The goal is not to explain every rule, especially in a complicated game, but to explain yourself precisely. You may not use the name of the game or any terminology that gives away what the game is!

Activity, Wednesday, August 24: Exploration 2

LaTeX workshop: Friday, August 26, in a special location, ECES 107. You may bring a laptop if you would prefer to use it instead of the computers in the lab. Here is the document we will work with: [pdf] [tex] [overleaf]

Due Monday, August 29: In class on Wednesday, you received one of your classmates' descriptions of a game. Please read what your classmate wrote and comment on it. Look for places where the game procedure is unclear. Are there any situations where the rules do not explain what to do? Are there any situations where the rules tell you to do two (or more) different things? Describe any such situations as clearly as you can. Suggestion: If you want to refer to a specific place on your classmate's paper, make a small symbol at that place on their paper, and then use that symbol when referring to that place in your comments.

Quiz: Wednesday, August 31, in the last 10 minutes of class.

Independent submission suggestions:

Diagram some of the sentences from exercises in Chapter 2, зз 2.1-2.3, and especially з2.9.
Diagram some of the sentences from the sample proof in Exploration 4 or from the proofs you are submitting for Wednesday.
Chapter 4 contains many mathematical sentences in its theorems and proofs. Try diagramming some of these.
Make up some mathematical statements of your own and diagram them.

Part 2: Direct proof

Goals: typeset mathematics using Latex; write direct proofs; identify assumed common knowledge

Reading: Book of proof, Chapter 4

Suggested exercises:

Chapter 4 (pp. 100-101), #1-7,10,11,18,19 are good exercises in setting up direct proofs. Figure out how to phrase these statements in the form "∀ x, P(x) ⇒ Q(x)" and use direct proof. Remember that x ∈ ℤ means "x is an integer." Can you find a way to use Exercises 4 and 5 to give a quick proof of 3? Can you use Exercise 6 and a proposition from the chapter to do Exercise 10 quickly?
You should get some practice setting up proofs by cases (Exercises 14-17), but once you get the idea, you don't gain much more by setting up more proofs by cases. Just do one or two of these exercises.
Exercises 8, 9, and 26 are good, and I recommend them, but they may require some clever ideas in addition to proofwriting skills.
I strongly recommend Exercises 20 and 27. These should not be the first exercises you try, because they are challenging, but I encourage you to work up to them. You will need to find a good formulation of these statements as implications to prove them.

Activity: Exploration 4

Due Wednesday, September 7: Complete the exercises on the second page of Exploration 4 [pdf] [tex] [overleaf]

Activity: Exploration 6

A quiz is likely on Monday, September 12. Expect to be asked to diagram sentences, set up direct proofs, and identify assumptions in mathematical writing.

Due Wednesday, September 14:

Make a list of fundamental properties of, operations on, and relationships between integers. Your list should have about 10 to 20 entries. To find ideas, try looking for facts about the integers that we use without proof in class and in the textbook.
Do one of Exercises 2, 4, 6, 12, 18 from Chapter 4 (p. 100) of Book of proof. Write a clear and careful proof and make sure to indicate which facts about the integers from your list you used in your proof.

Part 3: Induction

Goals: write proofs using induction

Reading: Book of proof, Chapter 10

Suggested exercises: In order to get practice with the form of induction proofs, you should do exercises like Chapter 10, #1-7, 15, 20, 34 (#8 is similar, but uses facts about the factorial that may not be familiar). These require you to prove formulas, which can sometimes be easier than proving more complex mathematical statements. Once you are comfortable with the form of induction proofs, you should do some of Chapter 10, #9-13, 16, 19, 22. Problems #25-28, 30 will ask you to use a recursive definition in your induction; this is a new skill to develop, so make sure to do at least one of these (#29 is similar, but requires you to know about binomial coefficients). I recommend taking a look at #30—you may find the formula surprising. Problems #32 and 33 are important because they use induction to prove things that are not easily expressed using formulas; please attempt these!

Activity for Monday, September 19: Exploration 8 [pdf] [tex] [overleaf]

Due Friday, September 23: Complete Question 5 of Exploration 8. Working in groups is strongly encouraged.

Due Monday, September 26: Complete Question 6 of Exploration 8. Working in groups is strongly encouraged.

Activity: Spherical graphs [pdf] [tex] [overleaf]

Reading for Wednesday, October 12: Make sure to read the discussions of strong induction and proof by smallest counterexample in §10.1 and §10.2 of Book of Proof.

Due Friday, October 14: Prove that if a spherical graph has V vertices, E edges, and F faces then V - E + F = 2.

Activity: The game of Nim

Activity: Euclid's algorithm

Due someday: Using Latex, write a paper that includes (i) an explanation of the rules of the game of Nim, (ii) a careful statement of who will win the game under optimal play, in terms of the initial number of tokens in the heap, (iii) an explanation of the winning strategy.

Due someday: Revise your paper about Nim, this time including (iv) a convincing explanation of why the winning strategy actually is a winning strategy.

Part 4: Sets

Goals: become comfortable with the language of sets (including functions and relations); use sets to express mathematical ideas; write proofs about sets; use sets to prove statements about other mathematical objects

Reading for Monday, October 31: Book of proof, Chapters 1 and 8. You need to read all of both chapters, but focus at first on the concepts and operations (equality of sets, subset, union, intersection, difference, well ordering) introducted in §§1.1, 1.3, 1.5, and 1.9 and proofs involving those concepts in §§8.1—8.3.

Suggested homework for Monday, November 7: complete Exploration 20. Expect a quiz soon with a similar format.

Suggested exercises (as of Friday, November 4) for practice with set operations: You should be able to do all of the exercises in §§1.1, 1.3, although you don't need to do all of these exercises. Do enough to feel confident about doing the others. In §1.5, you should be able to do 1, 2, 7, and 8.

Activity for Monday, November 7: Exploration 18

Suggested homework for Friday, November 11: Practice writing proofs about sets. I strongly suggest doing §8, #1-5, 19-20, 26-28 (problems #26-28 are closely related to Exploration 18). Some of these can be tricky to do completely, but the most important part is to set up the proofs and figure out exactly what you would have to do to write a complete proof. Please also practice writing formal proofs about sets by doing a selection of 6, 8-9, 12-15, 21-22 (we did #6 in class on November 7). On these problems in particular, try to make your proofs as formally complete as possible, showing every step of the reasoning and referencing the relevant definitions.

Reading for Monday, November 14: Book of proof, Chapter 12. The text makes referece to relations, so you may wish to refer back to the beginning of Chapter 11, especially Definition 11.1. You don't need to read all of Chapter 11, yet.

Due Friday, November 18: Prove the following statement:

Theorem: If a and b are integers with greatest common divisor d, the sets {ax + by : x,y ∈ ℤ} and { n ∈ ℤ : d|n} coincide.

Suggested exercises from §12.1 for Monday, November 28: You should be able to do all of the exercises in §12.1; it is very helpful to think carefully about what needs to be done in #9—12. Problem #11 uses the notation ℤ₅, which we have not introduced in class. You may replace ℤ₅ with the set {0,1,2,3,4} for this problem.

Suggested exercises from §12.2 for Monday, November 28: It is essential to be able to do problems like #1—10 in §12.2. Problem #10 is particularly interesting and it (or a problem like it) may be discussed in class. Problems #11—13 and #18 are a little more challenging, but problems like these are likely on the final exam, so I encourage you to practice with them now.

Reading for Monday, November 28: Book of proof, §1.2, §1.3, §12.4—12.5 (pp. 208—214). Some of this this has been assigned earlier, but we have not used these topics much in class yet. We will make use of these ideas for the rest of the semester, though.

Suggested exercises from §12.4 and §12.5: The exercises in these sections are mostly practice with definitions and setting up proofs about functions. You should understand what needs to be done in all of these exercises, even if you get stuck on some of them. The textbook does not have many conceptual exercises in these sections, so make sure also to practice with problems that come from class. I suggest thinking about Problem 8 from §12.5, though (note that X means ℤ - X in this exercise).

Suggested exercises from §12.5:

Reading for Wednesday, November 30: Book of proof, §11.1—11.2 (pp. 175—183)

Due Monday, December 5: Solve the question in Exploration 23 [pdf] [tex] [overleaf]. Note: this will be accepted late.

Due Friday, December 9: Either revise your proof of the following statement:

Theorem. If a and b are integers with greatest common divisor d, the sets {ax + by : x,y ∈ ℤ} and { n ∈ ℤ : d|n} coincide.

or prove the theorem below:

Definition. For each integer n, let ℤ/nℤ be the set of equivalence classes of the equivalence relation R = { (x,y) ∈ ℤ × ℤ : n|x - y}.

Theorem. Suppose that n is an integer. The functions a : ℤ/nℤ × ℤ/nℤ → ℤ/nℤ and m : ℤ/nℤ × ℤ/nℤ → ℤ/nℤ defined by a([x],[y]) = [x + y] and m([x],[y]) = [xy] are well-defined.

Extra question (not required): We usually write [x][y] instead of m([x],[y]) and call it multiplication modulo n. For which values of n ∈ ℤ is it possible to divide modulo n? That is, for which n ∈ ℤ is it possible to solve the equation [x][y] = [1] for every [x] ∈ ℤ / n ℤ except [x] = [0]?