Mathematical Foundations for Computer Science

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 Mobius
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.