MATH 220: Mathematical Proof, Section 201, Winter term II, 2015/2016.

Instructor: Julia Gordon.
Where and when : TTh 11-12:30, in MATX 1101.
My office: Math 217.
e-mail: gor at math dot ubc dot ca
Office hours: Due to a variable schedule of the other course I am teaching, the office hours will be different every week. Please see the "Announcements" section below; they will also be announced by e-mail at the beginning of each week. I am also somewhat available by appointment -- please e-mail well in advance though.
Text: Mathematical proofs, a transition to advanced mathematics, by G. Chartland, A. Polimeni, P. Zhang, Second or third edition.

The common website. The marking scheme, and all the course policies are found here.

Homework and quizzes

Homework 9 due Thursday March 31. Solutions .
Homework assignments other than Homework 9-10 are posted on common website.
You are strongly encouraged (and will receive a 2 points bonus at the end of the term if you do it) to type all your homework solutions using LaTeX. Here are some LaTeX resources .
Every other Thursday, the classes will be organized as workshops in which students in small groups will work problems. There will be a short quiz at the end.

Announcements:

Review session: Thursday (Note the correct day of the week!) April 21, 1-3pm, in MATH 100.
Office hours: April 21, 3-4pm, and April 22, 10am -- noon.
The office hours and review sessions of other professors will be posted on the common website as soon as they are known.

Some review materials for the final exam

The detailed list of topics .
A homework on graphs (from Prof. Khosravi's website). Solutions (Please note: the solution to the problem of the existence of an Euler tour in a graph all of whose vertices have even degree is different from the one we did in the last lecture. Our solution to be posted soon. Both are valid, of course; it is good if you understand both.)
Notes from the review session on March 9.
A collection of earlier handouts appears on the common website under "review for midterm 2" and "review for midterm 1"; more will be posted soon.

(Approximate) Course outline.

Here I will post short summaries of each class and other relevant to our secion notes, as we go along.

Tuesday, January 5: A few words about the course (please read the Preface and Chapter 0!); Introduction to sets; the notion of a subset. (sections 1.1 and 1.2). A handout about "subset" vs. "an element of" -- please take a look if you are confused about the set notation and subsets.
Thursday, January 7: Cardinality of the power set. You need to know only one proof (every element is either chosen into a subset or not). The more elaborate proof having to do with the number of subsets of cardinality k for every k is not required (but will be discussed in the workshop). Operations on sets; Venn diagrams: examples. An example of a proof of equality of sets. We covered Section 1.3 (with some extras), but please read everything till the end of Chapter 1!

Tuesday, January 11: Indexed collections of sets; Cartesian products. Sections 1.4-1.6.
Thursday, January 13: Workshop 1 and quiz.

Tuesday, January 19: Stared Chapter 2: Mathematical logic. We discussed the notion of statement, the truth tables, conjunction, disjunction and negation of statements. Also, defined equivalent statements as statements having the same truth tables. Discussed open sentences, and the connection between statements and sets. Discussed that DeMorgan's laws amount to the rules of negating conjunctions and disjunctions. This corresponds approximately to Sections 2.1 -- 2.3 and 2.8, 2.9. in the text; however, we have not yet discussed the implication. Will talk about it on Thursday.
Thursday, Jan. 21: Chapter 2, continued. Implication and biconditional. Quantifiers. Sections 2.4, 2.5, 2.6, 2.10.
Here is a note discussing the common mistakes related to the use of "such that" (we discussed this in class, too). It also has some tricky practice problems - please look at them and feel free to discuss in office hours! This is good preparation for the midterm.

Tuesday, Jan. 26: Quantifiers continued (Section 2.10). We also will discuss the use of quantifiers to define the unions and intersections of indexed collections of sets -- in particular, cover Section 1.4 more rigorously. A brief discussion of tautologies and contradictions (Section 2.7).
Here is a note about indexed collections of sets and quantifiers.
Here is a note discussing common mistakes made when reading/writing statements with more than one quantifier. Please read it and make sure you do not make these mistakes.
Thursday, Jan. 28: Workshop 2 (this is the workshop 2 problems and quiz with solutions).

Tuesday, Feb. 2: Proofs involving the integers. Congruence of integers. Sections to read: 3.2, 3.3, 3.4, 4.1, 4.2. We will continue with 4.1-4.2 and 4.3-4.4 on Thursday.
Thursday, February 4: Congruences of integers, continued. Proofs involving sets. Please read all of Chapter 4.

Tuesday, February 9: Counterexamples (Section 5.1); proof by contradiction (5.2-5.3)
Thursday, February 14: Workshop 3 and quiz (with solutions).

February 14-20: Break

Tuesday, February 23: Well-ordering of the positive integers. Induction. Sections 6.1-6.2
Thursday, February 25: Induction, continued: 6.2, 6.4. Also, defined the notion of a graph. Defined connected components of a graph, and used strong induction to prove that any (finite) graph is a disjoint union of connected components. There was a question left at the end of the lecture: prove that a graph cannot have an odd number of vertices of odd degree. Here are some notes on graphs that might be helpful (so far we covered only approximately sections 1 and 2.1 of these notes).

Tuesday, March 1: Graphs and induction, continued. These notes might be helpful.
Thursady, March 3: Workshop and quiz on induction and graphs.

Tuesday, March 8: 8.1, 9.1 - 9.4 Functions; domain and range.
Thursday, March 10: Continuing 9.2-9.4; Injective, surjective, bijective functions. The notions of image and pre-image (inverse image).

Tuesday, March 15: Composition of functions (Section 9.5); the inverse function (9.6); overview of Chapter 10 -- the notion of cardinality.
Thursday March 17 Cardinality; denumerable sets (Sections 10.1-10.2).

Tuesday, March 22: Cardinality, continued (please read 10.2 and 10.3)
Thursday, March 24: Cardinality, continued: we proved that the set of rational numbers is denumerable (up to some homework problems). Started discussing non-denumerable sets.

Tuesday, March 29: We finished the proof that the set of real numbers in non-denumerable. Workshop 5 on cardinality. Solutions .
April 5: Workshop 6.