## Instructor:

## Semester:

- 2012 Autumn/Monsoon (Aug - Dec)

**Mathematical Foundations for Computer Science**

This is the syllabus for a one-semester course. There are three parts: Set Theory, Algebra, Combinatorics.

The standard texts for this course are:Paul R Halmos, Naive Set Theory, Springer-Verlag.

- Lawvere and Bosebrugh, Sets for Mathematics, Cambridge.
- Sheldon Axler, Linear Algebra Done Right, Springer
- Michael Artin, Algebra, Prentice-Hall India.
- RP Stanley. Enumerative Combinatorics, Cambridge.
- I Anderson, Combinatorics of Finite Sets, Oxford Science Publications.
- B. Bollobas, Combinatorics, Cambridge.
- JH van Lint and RM Wilson, A course in Combinatorics, Cambridge.
- S Jukna. Extremal Combinatorics. Springer.

**Part A (Set Theory)**: Cartesian Closed Categories and Axiomatic Set Theory, Peano's axioms, Induction,

Axiom of Choice, Zorn's Lemma, Transnite Recursion, Ordinal numbers, Cardinal numbers.

Lattices, Fixed points, and Boolean algebra.

**Part B (Algebra):** Linear Algebra, vector spaces, Eigenvalues and Eigenvectors, Inner-Product spaces,

Operators roughly at the level of Axler's book. The connection with matrices roughly as described

in Artin's book (Chapters 2, 4, 7). A few weeks of Groups, Rings, Fields (especially Finite Fields),

Polynomials etc. as needed. (If there is time, Convexity, Tensor Products, Linear Analysis, etc.)

**Part C (Combinatorics):** Basic enumeration (Stanley Chapter I), Inclusion-Exclusion and Mobius

inversion, Polya's counting theorem, Set systems, Hall's theorem, Sperner's theorem, Littlewood-Oord-Klietman, LYM inequality, Dilworth's theorem, Erd}os-Ko-Rado theorem, Kruskal-Katona theorem, Harper's

theorem, FKG inequality, Turan's theorem, Ramsey's theorem, Designs, Codes.