To prove a statement is to demonstrate its truth with complete certainty, and mathematics is unique among the sciences and arts in that its beliefs are proved rather than merely supported by evidence. This course will provide an introduction to proof and with it the fundamental nature of mathematical knowledge; whilst helping develop the ability to think rigorously and abstractly.

** Lecturer:** Jacob Davis ** Office:** Wean 7112 ** Email: **jacobd @ andrew **Phone: ** 973 2141

** Grader:** Brendan Sullivan ** Office:** Wean 7104 ** Email: **bwsulliv @ andrew

Office hours
| ||

Monday | 15:00 - 16:00 | Jacob |

Tuesday | 16:00 - 17:00 | Brendan |

Wednesday | 10:00 - 11:00 | Jacob |

Thursday | 11:00 - 12:00 | Brendan |

Friday | 12:00 - 13:00 | Jacob |

**Homework:** This course helps you to develop the ability to think at length about difficult problems, and homework is your primary source of practice; it is very important to start early and make repeated attempts at questions you find challenging. You are encouraged to work together on homework, but you should not make any permanent record of the discussion, and should then go home and write up your own solutions from memory. (So whiteboards are fine, but taking written notes or discussion over IM is not.) You must state on each homework everyone you have discussed the problems with; this will have no effect on your marks. Failure to record collaborators or copying from a record of a discussion will be considered cheating. And make sure that you are an active collaborator in discussions as anything less will be of little value to you.

There will be large homeworks due on Tuesdays and smaller homeworks due on Fridays, except when there is a test. Homework should be handed in at the start of the lecture on that day; work handed in late but before the solutions are published will receive half credit.

**Exams:** There will be in-class midterms on Friday 27th May and Friday 10th June. There will be a cumulative three hour final on Friday 24th June. Exams will consist mostly of problems, but will also ask you to reproduce some material from lectures so you should understand and memorise the theorems and proofs covered as part of your revision.

**Grading:** Homework will make up 30% of the final grade. The final will carry 35% of credit, the midterm in which you do best 20% and the remaining midterm 15%. The cut-offs will be 90% for an A, 80% for a B, 70% for a C and 60% for a D. These may be lowered but will not be increased.

It is published by Prentice-Hall and is available at the bookstore. |

Proof & Logic | 5 lectures | Chapters 1 & 2 | Introduction to proofs. Inequalities. Basic sets and functions, functions to the reals. Quantifiers and logical statements. Elementary proof techniques |

Induction | 3 lectures | Chapter 3 | Induction, strong induction |

Sets & Functions | 5 lectures | Chapter 4 (plus some extra) | Injections, surjections, bijections, inverses. Cardinality, Schroeder-Bernstein theorem, countable union of countable sets, Cantor diagonalisation, size of the reals, uncountable sets. |

Combinatorics | 5 lectures | Chapter 5 (first half) & Chapter 10 (first half) | Selections, binomial co-efficients, Binomial Theorem. Permutations. Pigeonhole principle, [Inclusion-Exclusion Principle] |

Probability | 3 lectures | Chapter 9 (first half) (plus some extra) | Probability spaces, probability based on combinatorics, conditional probability, Bayes theorem, [random variables and expectation] |

Divisibility & Modular arithmetic | 5 lectures | Chapters 6 & 7 | Divisibility, primes, Fundamental Theorem of Arithmetic, Euclidean algorithm. Relations, equivalence relations. Congruence, Chinese remainder theorem, [Fermat's little theorem] |

The number of lectures on each topic is only an estimate, and it is likely that some material will have to be cut; subjects in square brackets will be the first to go.