C O N C E P T S O F M A T H E M A T I C S - S U M M E R II 2 0 1 5

LECTURES: Monday, Tuesday, Wednesday, Thursday, Friday 9:00am-10:20am, in Porter Hall A18A

INSTRUCTOR: Solesne Bourguin, office hours Tuesday, Wednesday, Friday 11:30am-12:30pm, you also can email me (bourguin@math.cmu.edu)
to set up an appointment or just drop by (Wean Hall 8206).

GRADER: Nate Ince, office hours Tuesday, Friday 1:00pm-2:00pm in Wean Hall 6203.

COURSE DESCRIPTION:
The aim of the course is to introduce proof-based mathematics. In mathematics, saying that a statement is true means something very precise: there is an unambiguous argument, a proof, which explains why the statement is true. This course will focus on the study and writing of such proofs in various fundamental mathematical topics such as logic and set theory, combinatorics, number theory and probability theory, which are central to further mathematical practice and also crucial in computer science and engineering.

PREREQUISITES: There are no formal prerequisites. However, basic notions of algebra and arithmetic would be helpful.

TEXTBOOK: There is no required textbook for this class. Lecture notes written by Sebastien Vasey (download) can be used to complement to lectures in class. Here are some other optional resources:

- Martin Days, An introduction to proofs and the mathematical vernacular. Available online at http://www.math.vt.edu/people/day/ProofsBook/IPaMV.pdf.
- John P. D'Angelo and Douglas B. West, Mathematical thinking: problem-solving and proofs. 2nd ed., Prentice Hall, 2000.

GRADING: problem sets (30%), midterm (30%) and a final exam (40%).

HOMEWORK: The problem sets will be posted on this website. The homework will be collected at the beginning of class on the due dates. Make sure to put your last and first names on your paper as well as your andrew ID. Late homework will not be accepted. The homework schedule is included in the tentative schedule (see below).

PROBLEM SETS.

Problem set 1 (due on Monday, July 6th).

Problem set 2 (due on Thursday, July 9th).

Problem set 3 (due on Monday, July 13th).

Problem set 4 (due on Thursday, July 16th).

Problem set 5 (due on Monday, July 20th).

Problem set 6 (due on Thursday, July 23rd).

Problem set 7 (due on Monday, July 27th).

Problem set 8 (due on Thursday, July 30th).

Problem set 9 (due on Monday, August 3rd).

Problem set 10 (due on Thursday, August 6th).

ADDITIONAL MATERIAL.

Review session one (before midterm exam).

Niraj Khare's lecture slides (lecture of 07/22/2015).

Review session two (before final exam).

TENTATIVE SCHEDULE:

- Mon, Jun 29th: Introduction to the concept of proof. HW1 out.
- Tue, Jun 30th: Numbers and inequalities.
- Wed, Jul 1st: Numbers and inequalities.
- Thu, Jul 2nd: Basic logic: and, or, not, implies.
- Fri, Jul 3rd: Independence day: no class.
- Mon, Jul 6th: Basic logic: quantifiers. HW1 due, HW2 out.
- Tue, Jul 7th: Basic logic: elementary proof techniques.
- Wed, Jul 8th: Sets: basic operations and notations.
- Thu, Jul 9th: Induction. HW2 due, HW3 out.
- Fri, Jul 10th: Induction.
- Mon, Jul 13th: Strong induction and the well-ordering principle. HW3 due, HW4 out.
- Tue, Jul 14th: Relations and functions.
- Wed, Jul 15th: Cardinality of finite sets.
- Thu, Jul 16th: Cardinality of infinite sets. HW4 due, HW5 out.
- Fri, Jul 17th: Review session.
- Mon, Jul 20th: Midterm. HW5 due, HW6 out.
- Tue, Jul 21th: Combinatorics: counting.
- Wed, Jul 22th: Combinatorics: counting.
- Thu, Jul 23th: Combinatorics: counting. HW6 due, HW7 out.
- Fri, Jul 24th: Combinatorics: the pigeonhole principle.
- Mon, Jul 27th: Number theory: the fundamental theorem of arithmetic. HW7 due, HW8 out.
- Tue, Jul 28th: Number theory: the Euclidean algorithm.
- Wed, Jul 29th: Number theory: modular arithmetic.
- Thu, Jul 30th: Number theory: the Chinese remainder theorem, Fermat's little theorem. HW8 due, HW9 out.
- Fri, Jul 31th: Applications to cryptography.
- Mon, Aug 3rd: Probability theory. HW9 due, HW10 out.
- Tue, Aug 4th: Probability theory.
- Wed, Aug 5th: Probability theory.
- Thu, Aug 6th: Review session. HW10 due.
- Fri, Aug 7th: Final.