- 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.