MATH 220: Mathematical Proof, Section 105, Winter term I, 2016/2017.

Instructor: Julia Gordon
office: Math 217. Office hours: Mondays 10:30-11:30am and Fridays 12:30-1:30pm.
Common website .
In particular, here you can find the course outline, marking scheme, and policies.
Other Resources: Drop-in tutorials begin during the second week of term. The schedule is available here .

Homework and quizzes

A new list of optional fun problems (not to hand in)
All homework assignments will be posted on the Common website and collected on Fridays. The hard deadline on homeork is 5pm on Friday; extensions beyond that are not possible.
Collaboration on homework: You are allowed to discuss homework with other students, but you have to first think about it yourself, and then write it alone in your own words. If you discussed homework solutions with someone, please acknowledge this on your submitted work, that is, put "discussed with Jane Smith" next to your name (and Jane Smith then has to put the similar acknowledgment of collaboration with you on her work). Please also see the notes on academic integrity .
You are strongly encouraged (and will receive 1 points bonus at the end f the term if you do it) to type all your homework solutions using LaTeX. Here are some LaTeX resources .
In Section 105, you need to pre-read before each class. There will be a short quiz on the pre-reading almost every class. These quizzes (and other occasional group activities) are worth 2% of the mark in total. This is a very small number, but the point is that if you do the pre-reading and participate in the class actively, you will do much better on exams and will get a lot more from this course. Reading assignments, supplements, etc. will be posted on this page regularly.
The sign-up link for Piazza forum . Please sign up for Piazza as soon as possible, and do ask and answer questions here! Our class link
Five most active participants get a 1% bonus at the end of the class!

Announcements:

Office hours after the end of class, and review:

NEW: last-minute office hours Tuesday (the day of the exam), 11am-1pm.
Review session Friday December 16, 1-3pm, in GEOG 212
We will go over some problems (based on your requests) from old final exams, which can be found at Math Dept website (In these exams, ignore problems about limits of sequences, and problems about "graphs" (which inlcude problems about cities connected by roads/airlines, etc. from last year's Term 2).
Notes from the review session (with thanks to Caitlin!)

Review materials for the final exam

a selection of problems from old exams prepared by Elyse Yeager. long-answer problems from old exams (by topic) prepared by Elyse Yeager.
The old list of optional fun problems (not to hand in)

Solutions

A new list of fun problems (not to hand in). Solutions .

Some old midterms with solutions, for practice

An old midterm 1 with solutions

Midterm 1 from 2010 ; Solutions

Midterm 1 from 2012

Midterm 2 from last year with solutions . (has good problems about sets and functions).

Please see also the review materials for the midterm (below) and the notes posted at the corresponding lecture descriptions.

Review materials for the midterm

The detailed list of topics
A collection of practice problems from old midterms . Solutions
There will be a review workshop in class on Friday. The problmes we will discuss are here (this is the Problem set 6 which is not for handing in). The solutions are posted on the common website along with all the other homework solutions.

The Pre-reading assignments and lecture plans:

September 7-9: Sets. We have covered Sections 1.1, 1.3 and most of 1.4. A handout about "subset" vs. "an element of" -- please take a look if you are confused about the set notation and subsets.
Pre-reading for Monday Sept. 12: Sections 1.2 and 1.4
Monday September 12: Cartesian products; cardinality of the power set. Sections 1.2, 1.3-1.4, started 1.5. Mentioned Venn diagrams (1.7).
Pre-reading for Wednesday Sept. 14: Sections 1.5, 1.6, 1.7, 1.8
Wednesday September 14: Unions and intersections of sets, complement, Venn diagrams, indexed collections of sets. Will finish everything in Chapter 1 up to the end of 1.8 in the book. Please look at 1.9 and 1.10.
Friday September 16: The quiz and discussion were on 1.8 (indexed collections); covered 2.1 (statements; logic).
Pre-reading for Monday Sept. 19: Sections 2.1-2.3.
Monday September 19-Friday September 23: Logic -- all of Chapter 2.
A supplementary note on double quantifiers
Another note on the use of quantifiers, the expression 'such that", and related questions Check out the problems at the end of this handout!
Answers to the questions from Friday class
(Pre-)reading for Monday September 26: all of Chapter 2 (especially Sections 2.9-2.11), and Section 4.1
Monday September 26: Discussion and quiz on logic (including negating statements with double quantifiers), Start 4.1.
Wednesday September 28: Definition of divisibility; division with remainder. Even and odd numbers. Direct proof (Sections 4.1-4.2)
Friday September 30: The definitions of the greatest common divisor and the least common multiple. The division algorithm. We proved that every common divisior of a and b divides gcd(a,b). (Section 4.3)
Monday October 3: Congruence. The relationship between congruence and remainders. We learned how to figure out the last digit of any power of any number, using congruence (the example done in class was the last digit of 7^2016). (Sections 4.4-4.5 and 5.2). We started talking about contrapositive proof (Section 5.1). Home reading: the rest of Chapter 5.
Wednesday October 5: The contrapositive proof and proof by contradiction. Finished Chapter 5 and did two classic proofs by contradiction: that square root of two is irrational, and that there are infinitely many prime numbers (Sections 6.1-6.2).
Friday October 7: Finished Chapter 6 and did examples from 7.1.
Wednesday October 12: Sections 7.1-7.2.
Friday October 14: Review workshop. We will review and work on problems for Chapters 1-2 and 4-6. (See Probelm set 6 on the common website for the problems).
Monday October 17: Midterm.
Wednesday October 19: Section 7.3. Please pay special attention to Proposition 7.1 on p.126.
Notes on Euclidean algorithm (this is optional, we did not discuss it in class and it's not on the exams).
Friday October 21: Finished Chapter 7. Started 8.1
Monday October 24: Proofs involving sets. Sections 8.1-8.2. We discussed the connection between set operations and logic (it is not emphasized in the book).
Notes on the relation between sets and open sentences .
Wednesday October 26: More on proofs involving sets. Finished Section 8.3.
Friday October 28: Perfect numbers (Theorem 1 from Section 8.4; we will skip Theorem 2). Chapter 9: disproof.
Monday October 31: Induction. (Chapter 10). We discussed Section 10.1, but also a topic not quite covered in the book: how the pronciple of mathematical induction is equivalent to the well-ordering axiom of natural numbers.
Notes on well-ordering (by Prof. Chen).
Wednesday November 2: Mathematical induction, continued. Fibonacci numbers. We covered all of Chapter 10 except graphs. The graphs will not appear on exams.
Friday November 4: Induction, continued. Strong induction.
Monday November 7: Induction finished: proof of the Fundamental theorem of Arithmetic using strong induction. (Theorem 10.1 in Section 10.2). Stared Relations: Section 11.1
Wednesday November 9: Relations, continued. Sections 11.2 and 11.3: equivalence relations and partitions.
Friday November 10: Remembrance day.
Monday November 14: Finish Chapter 11: congruence of integers (Section 11.4); start Chapter 12: functions. (Sections 12.1-12.2)
Wednesday November 16: Functions (12.1). Domain, codomain and range. Injective and surjective functions (Section 12.2). There was a quiz on functions and relations.
Friday November 18: Injective/surjective functions, continued. Pigeonhole principle. Composition and inverse functions. (Sections 12.2-12.5)
(Pre)reading for Monday: all of Chapter 12, especially 12.6.
Monday November 21: Continued with composition, injective, surjective, bijective functions. Image and preimage of sets (12.6).
Notes on images and preimages
Wednesday November 23: Images and preimages, continued. Started chapter 13: cardinality of sets. The definition of "same cardinality".
Friday November 25: Cardinality of sets, sontinued. Defined countable and uncountable sets. Survey of Chapter 13. We discussed specifically: Section 13.1, Theorem 13.1 with proof. Stated that |R| is not equal to |N|, but will prove it next class. Proved that "being of the same cardinality" is an equivalence relation on the set of subsets of a given universal set U (see p.222) Discussed continnum hypothesis (see end of 13.4). Covered Section 13.2 up to Theorem 13.3 with proof.
Last week of class: We proved some of the remaining results about cardinality announced last week: in particular, that Q is countable, R is not. The product of finitely many countable sets is countable. Next class: will prove that taking power sets makes cardinality go up. We will cover *everything* in Sections 13.1-13.3, and some of Section 13.4 (for now you can skip the proof of Cantor-Schroeder-Bernstein theorem, but you need to understand its statement).
Workshop that we started working on. Solutions to the first two problems
We will continue working on the workshop at the last class on Friday.
The workshop with full solutions