Course pages 2011–12

**Subsections**

##

Paper 2: Discrete Mathematics II

This course is not taken by NST or PPST students.

*Lecturer: Professor G. Winskel*

*No. of lectures:* 12

*Prerequisite course: Discrete Mathematics I*

*This course is a prerequisite for all theory courses as well as Security (Part IB and Part II), Artificial Intelligence (Part IB and Part II), Information Theory and Coding (Part II).*

### Aims

This course will develop the theory of sets and their uses in Computer Science.

### Lectures

**Sets and logic.**The basic set operations (union, intersection and complement) on subsets of a fixed set. The Boolean laws. Propositional logic and its models. Validity, entailment, and equivalence of propositions revisited. Structural induction illustrated on propositions. [2 lectures]**Relations and functions.**Product of sets. Relations, functions and partial functions. Composition and identity relations. Injective, surjective and bijective functions. Direct and inverse image of a set under a relation. Equivalence relations and partitions; modular arithmetic as an example. Directed graphs and partial orders. Size of sets (cardinality), especially countability. Cantor’s diagonal argument to show the reals are uncountable. [3 lectures]**Constructions on sets.**Russell’s paradox. Basic sets, comprehension, indexed sets, unions, intersections, products, disjoint unions, powersets. Characteristic functions. Sets of functions. Lambda notation for functions. Cantor’s diagonal argument to show power set strictly increases size. [2 lectures]**Introduction to inductive definitions.**Using rules to define sets; examples. Reasoning principles: rule induction and its instances; induction on derivations briefly. Simple applications, including transitive closure of a relation. [3 lectures]**Well-founded induction.**Well-founded relations and well-founded induction. Other induction principles as instances of well-founded induction. Product and lexicographic product of well-founded relations. Examples and applications, including to Euclid’s algorithm for HCF/GCD. Informal understanding of definition by well-founded recursion. [2 lectures]

### Objectives

On completing this part of the course, students should be able to

- understand and use the language of set theory; prove and disprove assertions using a variety of techniques;
- understand Boolean operations as operations on sets and formulate statements using Boolean logic;
- apply the principle of well-founded induction;
- define sets inductively using rules, and prove properties about them.

### Recommended reading

Comprehensive notes will be provided.

Devlin, K. (2003). *Sets, functions, and logic: an introduction to abstract mathematics*. Chapman and Hall/CRC Mathematics (3rd ed.).

Biggs, N.L. (1989). *Discrete mathematics*. Oxford University Press.

Mattson, H.F. Jr (1993). *Discrete mathematics*. Wiley.

Nissanke, N. (1999). *Introductory logic and sets for computer scientists*. Addison-Wesley.

Pólya, G. (1980). *How to solve it*. Penguin.