MATH 220: Mathematical Proof, Section 202, Winter term II, 2019/2020.

Instructor: Julia Gordon
office: Math 217. Office hours: Tuesday 3:30-4:30pm and Friday 11am-12noon.
Common website .
In particular, here you can find the course outline, marking scheme, and policies.
Other Resources: Math Learning Centre. The schedule is available here .

Homework

All homework assignments will be posted on the Common website on Thursdays and due Thursday the following week. Individual extensions 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).
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 .
You are strongly encouraged to pre-read before each class.
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
Three most active participants get a 1% bonus at the end of the class!

Announcements:

Please take an informal Survey about the course (it helps me improve something for the second half).
The course has moved online! Please keep checking both this website and Canvas. And read the textbook.

Review materials for the midterm

A collection of problems from old midterms, etc.
Solutions Disclaimer: as this is a collection of problems from old exams, solutions are written by different instructors at different times; "I" does not always mean the same person, and there may be references to things that happened in the class that year (and not now). Hopefully they give you enough information to see how to solve the problems and avoid most popular mistakes. Ignore the notes about marking that are occasionally present. The references to the notes on quantifiers,etc. are to the two notes that are linked below.

Blank worksheets from our classes:
- Worksheet 1 (Logic)
- Worksheet 2 (Conditional statements)
- Worksheet 3 (Biconditional statments)
- Worksheet 4 (Contrapositive)
- Worksheet 5 (Quantifiers)
- Worksheet 6 (Negating quantified statements)
- Worksheet 7 (More quantifiers)
- Worksheet 8 (Proof or disproof?)
- Worksheet 9 (Induction)
- Worksheet 10 (Sets 1)
- Worksheet 11 (Sets 2)
- Worksheet 12 (Sets 3; Relations)
- Worksheet 13 (Congruence of integers; Functions)
- Worksheet 14 (injective and surjective functions; composition of functions; pigeonhole principle)
- Worksheet 15 (Review Functions - range, injectivity, surjectivity.)
- Worksheet 16 (Inverse Functions; images and preimages)
  Solutions to Worksheet16.
- Worksheet 17 (Rational and irrational numbers; proof by contradiction).
  Worksheet 17 solutions
- Worksheet 18 (Cardinality -I)
  Worksheet 18 solutions (Note that only the first two problems were discussed; the rest are becoming part of Worksheet 19).
- Worksheet 19 Cardinality-II: countable sets.
- Worksheet20: cardinality (with partial solutions). Lecture notes (with the rest of the solutions).
- Review worksheet 1 : putting together quantifiers, indexed collections of sets, limits, functions, images and preimages. Please do this if you feel uncomfortable with any of these concepts!
- A couple harder problems on the proof by contradcition

Some notes in case you are confused by the quantifiers (or other topics):
- A Note on "such that" and related issues
- A note on double quantifiers (This note uses the set Q -- this is the set of rational numbers, that is, numbers of the form a/b, where a and b are both integers).
- A note about the correct usage of "subset" and "element of" notation.
- A note about infinite unions/intersections (and the relation with quantified sentences)

The Pre-reading assignments and lecture notes:

January 7-9: Sets and logic.
We discussed: the notion of a set and being an element of a set. The empty set. Logical statements and beginnings of propositional calculus: we defined conjunction, disjunction, negation, and conditional statements. Read: Sections 1.1, 2.1, 2.2 (covered these sections on January 7, will continue discussing them on Thursday).
Notes from Lecture 1
Read for Thursday: 2.2, 2.3 and 1.3.
Notes for Thursday (Lecture 2) .
Tuesday Jan 14: Conditional statements. Start direct proof.
Pre-reading for Tuesday: Sections 2.3 and 4.1, 4.2, 4.3. We continued discussing conditional statements and started using them to make proofs! Please read sections 4.1-4.4. Defined the notion of divisibility for integers; discussed even and odd integers.
Notes for January 14 .
Thursday Jan 16: Finished Chapter 4 and went back to Chapter 2.
Reading for Thursday: 4.2-4.5 and 2.4, 2.5, 2.6.
Notes for Thursday
Tuesday January 21: Reading for Tuesday: 2.4, 2.5, 2.6 (covered last week); Contrapositive proof; congruence of integers -- sections 5.1, 5.2, 5.3.
Notes
Thursday January 23: Please read the rest of Chapter 2. The real content we will discuss is Sections 2.7, 2.8, 2.10. We will also continue talking about congruence of integers (section 5.2).
Notes
Tuesday January 28: (Pre-)reading: all of Chapter 2 (especially Sections 2.9-2.11)
Quantifiers; negating complicated logical statements.
Corrected worksheet . The lecture was centered on answering the questions from the worksheet.
Lecture notes . Please make sure you know how to solve all the questions except maybe for the last two. (We will discuss the last two questions next class). If you feel confused, you might find the supplementary note below helpful:
A note on the use of quantifiers, the expression "such that", and related questions (This discusses out worksheet questions in some more detail).
Thursday January 30: Continued discussing statements with multiple quantifiers, in particular, the notion of the function f(x) tending to infinity as x goes to infinity. Notes .
Tuesday February 4: Existence proof; disproof. (Pre-)reading: Sections 7.1-7.4 and Chapter 9. (Some of section 7.3 may look very hard; you can skip that if needed). We discussed Proposition 7.1 on p.126; then discussed the proof "The following are equivalent" type of statements. In the process, we reviewed operations with congruences of integers, in particular, how to use congruences efficiently to figure out remainders of large powers modulo a small integer.
Notes from the class .
You an also look at Notes on Euclidean algorithm , which supplement the discussion of Proposition 7.1 (this is completely optional, we did not discuss it in class and it's not on the exams).
Thursday February 6: Review (Proof and disproof: chapters 7 and 9). Start Induction (Chapter 10). Notes from class . We will discuss Section 10.1 next class; please read the start of Chapter 10 and Section 10.1.
Tuesday February 11: Mathematical induction, continued. We will eventually cover most of Chapter 10 except graphs. The graphs will not appear on exams.
Notes
Thursday February 13: Midterm (11-11:45). Then finished induction (with an example of string induction). Quickly discussed the definitions of: subset, intersection and union of sets, indexed collections of sets (Sections 1.3, 1.5, 1.8).
Notes
Tuesday February 25: More about sets: sections 1.3-1.8. Power sets. 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. Also will discuss the connection between set operations and logic (it is not emphasized in the book). Notes on the relation between sets and open sentences.
Supplement: A handout about "subset" vs. "an element of" -- please take a look if you are confused about the set notation and subsets. Finally, started talking about proofs involving sets. Sections 8.1-8.3. (we proved one of the DeMorgan laws for sets).
Notes from the class .
Thursday February 27: More on proofs involving sets. Finish Sections 8.1-8.3 and will do Section 1.2 (Catesian products of sets).
Notes form the class
Tuesday March 3 : Relations: Sections 11.1 -- 11.4; in particular, equivalence relations and partitions.
Notes from class
Thursday Marh 5: Finish Chapter 11: congruence of integers (Section 11.4); start Chapter 12: functions. (Sections 12.1-12.2)
Notes from class
Tuesday March 10: Functions (12.1). Domain, codomain and range.
Notes from class
Thursday March 12: Injective/surjective functions. Pigeonhole principle. Composition of functions. (Sections 12.2-12.4)
Notes from class
(Pre)reading for Tuesday: all of Chapter 12, especially 12.6.
Tuesday March 17: Continue with composition, injective, surjective, bijective functions. Inverse functions. Image and preimage of sets Sections 12.5 - 12.6.
Notes on images and preimages (based on notes by Prof. A. Rechnitzer ).
Thursday March 19: Images and preimages, continued. Finsihed Chapter 12, started Proof by contradiction (chapter 6): went through irrationality of the square root of 2. Did Worksheet 16 (see worksheets section above, where solutions are posted, too).
From here on this list is not going to be maintained; I will continue posting worksheets at the top of this page, but all information about the lectures has moved to Canvas! Please follow the Canvas website!