Meetings

Click on the theme item for the meeting plan for that theme.Click on the meeting item for references, exercises, and additional reading related to it.

**Theme 1 : Basics of Mathematical Proofs**- 11 meetings- Meeting 01 : Mon, Aug 03, 11:00 am-11:50 am - Raghavendra Rao
- Meeting 02 : Tue, Aug 04, 10:00 am-10:50 am - Raghavendra Rao
- Meeting 03 : Wed, Aug 05, 09:00 am-09:50 am - Raghavendra Rao
- Meeting 04 : Thu, Aug 06, 12:00 pm-12:50 pm -
- Meeting 05 : Mon, Aug 10, 11:00 am-11:50 am -
- Meeting 06 : Tue, Aug 11, 10:00 am-10:50 am -
- Meeting 07 : Wed, Aug 12, 09:00 am-09:50 am -
- Meeting 08 : Thu, Aug 13, 12:00 pm-12:50 pm -
- Meeting 09 : Mon, Aug 17, 11:00 am-11:50 am -
- Meeting 10 : Tue, Aug 18, 10:00 am-10:50 am -
- Meeting 11 : Wed, Aug 19, 09:00 am-09:50 am -

Administrative announcements. References Exercises Reading Administrative announcements.References: None Propositional logic (quick review). Predicate logic. Quantifiers. References [Rosen] Section 1.1, 1.2 and 1.3. Exercises Reading Propositional logic (quick review). Predicate logic. Quantifiers.References: [Rosen] Section 1.1, 1.2 and 1.3. Rules of inference. Arguments and argument forms. References [Rosen] Sections 1.4 and 1.5. Exercises Reading Rules of inference. Arguments and argument forms.References: [Rosen] Sections 1.4 and 1.5. Validity. Notion of a proof. References [Rosen] Exercises Reading Validity. Notion of a proof.References: [Rosen] Proof techniques: Direct proof. Proof by contradiction. Contrapositive. References [Rosen] Exercises Reading Proof techniques: Direct proof. Proof by contradiction. Contrapositive.References: [Rosen] More proof techniques. Existential proofs. Uniqueness proofs. Axioms for set theory. Russell's paradox. References [Rosen] Exercises Reading More proof techniques. Existential proofs. Uniqueness proofs. Axioms for set theory. Russell's paradox.References: [Rosen] Notion of cardinality for infinite sets. Countable and uncountable sets. Examples of countable sets: Set of integers, rational numbers. References [Rosen]. A notes on <a href="http://www.math.ucla.edu/~mwilliams/pdf/cardinality.pdf"> Cardinality</a> by Michael Williams. Exercises Reading Notion of cardinality for infinite sets. Countable and uncountable sets. Examples of countable sets: Set of integers, rational numbers.References: [Rosen]. A notes on Cardinality by Michael Williams. Uncountability. Cantor's diagonalization. References [Rosen]. A notes on <a href="http://www.math.ucla.edu/~mwilliams/pdf/cardinality.pdf"> Cardinality</a> by Michael Williams. Exercises Reading Uncountability. Cantor's diagonalization.References: [Rosen]. A notes on Cardinality by Michael Williams. More examples of uncountable sets. Principle of mathematical induction. Example. References [Rosen]. A notes on <a href="http://www.math.ucla.edu/~mwilliams/pdf/cardinality.pdf"> Cardinality</a> by Michael Williams. Exercises Reading More examples of uncountable sets. Principle of mathematical induction. Example.References: [Rosen]. A notes on Cardinality by Michael Williams. Mathematical Induction: Examples. References [Rosen] Exercises Reading Mathematical Induction: Examples.References: [Rosen] Disproving theorems: counter examples. Fallacies in proofs. References Exercises Reading The book "Mathematical Fallacies Flaws and Flimflam" by Ed Barbeau has a good collection of well known mathematical fallacies. Disproving theorems: counter examples. Fallacies in proofs.References: None Reading: The book "Mathematical Fallacies Flaws and Flimflam" by Ed Barbeau has a good collection of well known mathematical fallacies. **Theme 2 : Describing Sets : Logic & Computation**- 15 meetings- Meeting 12 : Thu, Aug 20, 12:00 pm-12:50 pm -
- Meeting 13 : Mon, Aug 24, 11:00 am-11:50 am -
- Meeting 14 : Mon, Aug 24, 04:45 pm-05:35 pm -
- Meeting 15 : Tue, Aug 25, 10:00 am-10:50 am -
- Meeting 16 : Wed, Aug 26, 09:00 am-09:50 am -
- Meeting 17 : Mon, Aug 31, 11:00 am-11:50 am -
- Meeting 18 : Tue, Sep 01, 10:00 am-10:50 am -
- Meeting 19 : Wed, Sep 02, 09:00 am-09:50 am -
- Meeting 20 : Thu, Sep 03, 12:00 pm-12:50 pm -
- Meeting 21 : Mon, Sep 07, 11:00 am-11:50 am -
- Meeting 22 : Wed, Sep 09, 09:00 am-09:50 am -
- Meeting 23 : Thu, Sep 10, 12:00 pm-12:50 pm -
- Meeting 24 : Mon, Sep 14, 11:00 am-11:50 am -
- Meeting 25 : Tue, Sep 15, 10:00 am-10:50 am -
- Meeting 26 : Wed, Sep 16, 09:00 am-09:50 am -

Introduction to first order logic. References The book "Logic in Computer Science" by Michael Huth and Mark Ryan is a good book on Logic from a computer science perspective. Lectures will be in part based on this book. Exercises Reading Introduction to first order logic.References: The book "Logic in Computer Science" by Michael Huth and Mark Ryan is a good book on Logic from a computer science perspective. Lectures will be in part based on this book. Decidability. Undecidability of a First order formula. Expressivenes of first order formula. References Logic in Computer Science by Huth and Ryan. Exercises Reading Decidability. Undecidability of a First order formula. Expressivenes of first order formula.References: Logic in Computer Science by Huth and Ryan. [Make up for THU 27-08-2015]. Undecidability of checking validity of FO w.f.f. Expressiveness of First order logic: Path(u,v) cannot be expressed in FO. Compactness theorem (statement only). References FOr undecidability, the reduction is based on the one given in the book "Logic for Computer Scientists" by Uwe Schoening. For expressiveness, please See "Logic in Computer Science" by Michael Huth and Mark Ryan. Exercises Reading [Make up for THU 27-08-2015]. Undecidability of checking validity of FO w.f.f. Expressiveness of First order logic: Path(u,v) cannot be expressed in FO. Compactness theorem (statement only).References: FOr undecidability, the reduction is based on the one given in the book "Logic for Computer Scientists" by Uwe Schoening. For expressiveness, please See "Logic in Computer Science" by Michael Huth and Mark Ryan. Notion of a proof in first order logic. Soundness and Completeness of FO. (Statement only). References [Enderton] Exercises Reading Notion of a proof in first order logic. Soundness and Completeness of FO. (Statement only).References: [Enderton] Formal model for number theory. Peano arithmetic. Goedel's incompleteness theorem(Statement only). References Class notes + [Enderton] Exercises Reading Formal model for number theory. Peano arithmetic. Goedel's incompleteness theorem(Statement only).References: Class notes + [Enderton] Verification of systems using logic. Model Checking. Linear Time Temporal Logic. References <a href="http://www.cs.bham.ac.uk/research/projects/lics/"> Book</a> by Michael Huth and Mark Ryan "Logic in Computer Science" Exercises Reading Verification of systems using logic. Model Checking. Linear Time Temporal Logic.References: Book by Michael Huth and Mark Ryan "Logic in Computer Science" Linear Time Temporal logic semantics and examples. References <a href="http://www.cs.bham.ac.uk/research/projects/lics/"> Book</a> by Michael Huth and Mark Ryan "Logic in Computer Science" Exercises Reading Linear Time Temporal logic semantics and examples.References: Book by Michael Huth and Mark Ryan "Logic in Computer Science" Modelling systems using LTL. Mutual exlcusion: an example. References <a href="http://www.cs.bham.ac.uk/research/projects/lics/"> Book</a> by Michael Huth and Mark Ryan "Logic in Computer Science" See Chapter 4. Exercises Reading Modelling systems using LTL. Mutual exlcusion: an example.References: Book by Michael Huth and Mark Ryan "Logic in Computer Science" See Chapter 4. Modal Logic: syntax and semantics References <a href="http://www.cs.bham.ac.uk/research/projects/lics/"> Book</a> by Michael Huth and Mark Ryan "Logic in Computer Science", Chapter 5. Exercises Reading Modal Logic: syntax and semanticsReferences: Book by Michael Huth and Mark Ryan "Logic in Computer Science", Chapter 5. Effective Computability: Models of computation References [HMU]. Also see Dexter Kozen: "Automata and Computability" Exercises Reading Effective Computability: Models of computationReferences: [HMU]. Also see Dexter Kozen: "Automata and Computability" Recursive and Recursively enumerable languages. Decidability and semi-decidability. The halting problem. Undecidability. References [HMU]. Also see Dexter Kozen: "Automata and Computability" Exercises Reading Recursive and Recursively enumerable languages. Decidability and semi-decidability. The halting problem. Undecidability.References: [HMU]. Also see Dexter Kozen: "Automata and Computability" Halting problem is undecidable. References Exercises Reading Halting problem is undecidable.References: None PCP is undecidable References Exercises Reading PCP is undecidableReferences: None More on undecidability. References Exercises Reading More on undecidability.References: None To Be Announced References Exercises Reading To Be AnnouncedReferences: None **Theme 3 : Size of Sets : Counting & Combinatorics**- 17 meetings- Meeting 27 : Mon, Sep 21, 11:00 am-11:50 am - Jayalal Sarma
- Meeting 28 : Tue, Sep 22, 10:00 am-10:50 am - Jayalal Sarma
- Meeting 29 : Wed, Sep 23, 09:00 am-09:50 am - Jayalal Sarma
- Meeting 30 : Tue, Sep 29, 10:00 am-10:50 am - Jayalal Sarma
- Meeting 31 : Wed, Sep 30, 09:00 am-09:50 am - Jayalal Sarma
- Meeting 32 : Thu, Oct 01, 12:00 pm-12:50 pm - Jayalal Sarma
- Meeting 33 : Mon, Oct 05, 11:00 am-11:50 am - Jayalal Sarma
- Meeting 34 : Tue, Oct 06, 10:00 am-10:50 am - Jayalal Sarma
- Meeting 35 : Wed, Oct 07, 09:00 am-09:50 am -
- Meeting 36 : Thu, Oct 08, 12:00 pm-12:50 pm -
- Meeting 37 : Mon, Oct 12, 11:00 am-11:50 am -
- Meeting 38 : Tue, Oct 13, 10:00 am-10:50 am -
- Meeting 39 : Wed, Oct 14, 09:00 am-09:50 am -
- Meeting 40 : Thu, Oct 15, 12:00 pm-12:50 pm -
- Meeting 41 : Tue, Oct 20, 10:00 am-10:50 am -
- Meeting 42 : Wed, Oct 21, 09:00 am-09:50 am -
- Meeting 43 : Mon, Oct 26, 11:00 am-11:50 am -

Review of Basics. Permutations, Combinations. Double Counting as a combinatorial proof technique. References [KR] Page 335 - 340 and Pages 354 - 369.<br> Exercises Exercises from [KR] : Exercises for section 5.1, 5.3, 5.4. Reading Sections 5.1, 5.2, 5.3 in the Benjamin-Quinn [BQ] Book. Review of Basics. Permutations, Combinations. Double Counting as a combinatorial proof technique.References: [KR] Page 335 - 340 and Pages 354 - 369. Exercises: Exercises from [KR] : Exercises for section 5.1, 5.3, 5.4. Reading: Sections 5.1, 5.2, 5.3 in the Benjamin-Quinn [BQ] Book. Counting by Bijections. Examples. Approximate Bijection. References Sections 6.1 in the Benjamin-Quinn [BQ] Book. Exercises Reading Counting by Bijections. Examples. Approximate Bijection.References: Sections 6.1 in the Benjamin-Quinn [BQ] Book. Catalan numbers. Diagonal Avoiding paths. Counting by bijections. References Section 2.4 in <a href="http://mathcircle.berkeley.edu/BMC6/pdf0607/catalan.pdf">Notes by Tom Davis</a>. Exercises Reading Catalan numbers. Diagonal Avoiding paths. Counting by bijections.References: Section 2.4 in Notes by Tom Davis. Permutation and Combinations with repetitions. Multichoosing. Interpretations. Identities related to multichoosing. References Exercises Reading Permutation and Combinations with repetitions. Multichoosing. Interpretations. Identities related to multichoosing.References: None Inclusion-Exclusion Principle. Proof. Applications References <a href="http://math.mit.edu/~fox/MAT307-lecture04.pdf">Lecutre notes</a>. The proof of PI was not done as per this (please use class notes). But examples are from here. Exercises Use inclusion-exclusion to derive a formula for the number of numbers less than n, but co-prime to n. Reading Inclusion-Exclusion Principle. Proof. ApplicationsReferences: Lecutre notes. The proof of PI was not done as per this (please use class notes). But examples are from here. Exercises: Use inclusion-exclusion to derive a formula for the number of numbers less than n, but co-prime to n. Derangements, Chromatic Polynomial of a graph. References Section 6.6 in [KR]<br> Section 9.1 in <a href="http://www.ltcc.ac.uk/courses/enumerative_combinatorics/l9.pdf">Notes on Enumerative Combinatorics by Cameron</a>. Exercises Reading Derangements, Chromatic Polynomial of a graph.References: Section 6.6 in [KR]

Section 9.1 in Notes on Enumerative Combinatorics by Cameron.Pigeon Hole Principle and two applications. References Kennth Rosen's Book Section 5.2. I used some examples from the old notes as well. Exercises If I have at least two friends on Facebook, there will be two friends in my friends list such that I have the same number of mutual friends with them. Reading Pigeon Hole Principle and two applications.References: Kennth Rosen's Book Section 5.2. I used some examples from the old notes as well. Exercises: If I have at least two friends on Facebook, there will be two friends in my friends list such that I have the same number of mutual friends with them. More Applications of PHP. Dirichlet's Approximation principle, Monotone subsequence lemma. References <ul> <li><a href="https://www.expii.com/topic/2468">Dirichlet's Principle</a></li> <li><a href="http://www2.math.ethz.ch/education/bachelor/lectures/hs2013/math/tpdm/lecture-notes.pdf">Lecture 2 of the notes by Benny Sudakov</a></li> </ul> Exercises Reading <a href="http://stat.wharton.upenn.edu/~steele/Publications/PDF/VOTMSTOEAS.pdf">Variations of Erdoz-Szekeres Monnotone Subsequence Theorem</a> More Applications of PHP. Dirichlet's Approximation principle, Monotone subsequence lemma.Erdos-Szekeres Subsequence Theorem. Happy Ending Problem. Ramsey Theory. Ramsey Numbers. Erdos-Szekeres upper bound. References <a href="http://people.maths.ox.ac.uk/gouldm/ramsey.pdf">Section 6 of the Notes</a> Exercises Reading <a href="http://www.math.ucsd.edu/~ronspubs/90_06_ramsey_theory.pdf">Essay on Ramsey Numbers</a> Erdos-Szekeres Subsequence Theorem. Happy Ending Problem. Ramsey Theory. Ramsey Numbers. Erdos-Szekeres upper bound.References: Section 6 of the Notes Reading: Essay on Ramsey Numbers Lower Bounds for Diagonal Ramsey Numbers. The probabilistic method. References <a href="http://people.maths.ox.ac.uk/gouldm/ramsey.pdf">Section 6 of the Notes</a> Exercises <a href="">Infinite version of Ramsey Numbers. Applications to Program Termination Arrguments.</a> Reading Lower Bounds for Diagonal Ramsey Numbers. The probabilistic method.Solving Recurrences. Linear Homogeneous Recurrences with constant coefficients. Characterestic equation. Case when the characterestic equation has distinct roots. References Exercises Reading Solving Recurrences. Linear Homogeneous Recurrences with constant coefficients. Characterestic equation. Case when the characterestic equation has distinct roots.References: None More examples of recurrence relations and their solutions. References Exercises Reading More examples of recurrence relations and their solutions.References: None Linear Non-homogeoneous Recurrence relations with constant coefficients. Particular solution. A characterization of the general solution. References Exercises Reading Linear Non-homogeoneous Recurrence relations with constant coefficients. Particular solution. A characterization of the general solution.References: None Example of Non-homogeneous recurrence relations. Forms of particular solution from the forms of the non-homogeneous part of the linear recurrence relations. Solution examples. References Exercises Reading Example of Non-homogeneous recurrence relations. Forms of particular solution from the forms of the non-homogeneous part of the linear recurrence relations. Solution examples.References: None Solving recurrences by substitution. Index substitution and Functional Substitution. Examples, Counting. Derangements using Recurrence relations. Generating Function for infinite sequences. Extended binomial theorem. References Rosen's Textbook - Section 6.3 and 6.4<br> <a href="https://mikespivey.wordpress.com/2011/11/22/derangements/">Counting Derangements</a> Exercises Reading Solving recurrences by substitution. Index substitution and Functional Substitution. Examples, Counting. Derangements using Recurrence relations. Generating Function for infinite sequences. Extended binomial theorem.References: Rosen's Textbook - Section 6.3 and 6.4

Counting DerangementsGenerating Function Method for solving linear recurrence relations. Linear case first. References [Rosen] Section 6.4. Exercises Reading Generating Function Method for solving linear recurrence relations. Linear case first.References: [Rosen] Section 6.4. Non-homogeneous case, Higher Degree Case, Non-linear special cases : Catalan Numbers. References <a href="http://www.math.drexel.edu/~foucart/TeachingFiles/F12/M235Lect4.pdf">Notes</a> Exercises Reading Non-homogeneous case, Higher Degree Case, Non-linear special cases : Catalan Numbers.References: Notes **Theme 4 : Structured Sets : Operations & Relations**- 10 meetings- Meeting 44 : Tue, Oct 27, 10:00 am-10:50 am -
- Meeting 45 : Wed, Oct 28, 09:00 am-09:50 am -
- Meeting 46 : Thu, Oct 29, 12:00 pm-12:50 pm -
- Meeting 47 : Mon, Nov 02, 11:00 am-11:50 am -
- Meeting 48 : Tue, Nov 03, 10:00 am-10:50 am -
- Meeting 49 : Wed, Nov 04, 09:00 am-09:50 am -
- Meeting 50 : Thu, Nov 05, 12:00 pm-01:20 pm -
- Meeting 51 : Mon, Nov 09, 11:00 am-11:50 am -
- Meeting 52 : Tue, Nov 10, 10:00 am-10:50 am -
- Meeting 53 : Mon, Nov 16, 11:00 am-12:00 pm -

Structured Sets. Relations, Representing relations. Graphs and Hypergraphs. Reflexivity, Symmetry and Transitivity properties. Testing the properties given the graph. References Section 7.1-7.5 in Kenneth Rosen's Textbook Exercises Reading Structured Sets. Relations, Representing relations. Graphs and Hypergraphs. Reflexivity, Symmetry and Transitivity properties. Testing the properties given the graph.References: Section 7.1-7.5 in Kenneth Rosen's Textbook Equivalence Classes. Closure of relations. Reflexive, Symmetric and Transitive closures. Computing the transitive closure. References Section 7.1-7.5 in Kenneth Rosen's Textbook Exercises design an algorithm for finding the equivalence classes of a given equivalence relation (given as a graph). Reading Equivalence Classes. Closure of relations. Reflexive, Symmetric and Transitive closures. Computing the transitive closure.References: Section 7.1-7.5 in Kenneth Rosen's Textbook Exercises: design an algorithm for finding the equivalence classes of a given equivalence relation (given as a graph). Posets, Examples, Total order, Hasse diagrams. References Section 7.6 in Kenneth Rosen's Textbook Exercises Reading Posets, Examples, Total order, Hasse diagrams.References: Section 7.6 in Kenneth Rosen's Textbook Total order and Well-order, Well-ordering induction. An example proof using well-ordering. References Section 7.6 in Kenneth Rosen's Textbook Exercises Reading Total order and Well-order, Well-ordering induction. An example proof using well-ordering.References: Section 7.6 in Kenneth Rosen's Textbook Maximal, Minimal, greatest, least elements. GLBs and LUBs. Lattices. Examples and non-examples. Identities on lattices. Distributive lattices. References Section 7.6 in Kenneth Rosen's Textbook Exercises Reading Maximal, Minimal, greatest, least elements. GLBs and LUBs. Lattices. Examples and non-examples. Identities on lattices. Distributive lattices.References: Section 7.6 in Kenneth Rosen's Textbook Complete posets and their structure. Knaster-Tarski Fixed Point theorem. Proof. Cantor-Bernstein-Schroeder Theorem. Applications. References <a href="http://www.drmaciver.com/2012/02/the-power-of-fixed-point-theorems-in-set-theory/">Notes</a> Exercises Reading Complete posets and their structure. Knaster-Tarski Fixed Point theorem. Proof. Cantor-Bernstein-Schroeder Theorem. Applications.References: Notes Using Knaster-Tarski's theorem to prove Schroeder-Bernstein theorem. Applications of fixed points to argue about semantics of while loops. <br> <br>Outline : Another use of structure of a lattice. Incidence algebra. Delta, Zeta and Mobious functions of a lattice. Mobious inversion. Deriving Principle of inclusion-exclusion as a Corollary. References <a href="http://www.drmaciver.com/2012/02/the-power-of-fixed-point-theorems-in-set-theory/">Notes</a> Exercises Reading Using Knaster-Tarski's theorem to prove Schroeder-Bernstein theorem. Applications of fixed points to argue about semantics of while loops.

Outline : Another use of structure of a lattice. Incidence algebra. Delta, Zeta and Mobious functions of a lattice. Mobious inversion. Deriving Principle of inclusion-exclusion as a Corollary.References: Notes Structured Sets. Closure, Associativity, Identity, Inverse, Commutativity. Groups, Semigroups, monoids, groupoids. References Kozen's Textbook material Exercises Reading Structured Sets. Closure, Associativity, Identity, Inverse, Commutativity. Groups, Semigroups, monoids, groupoids.References: Kozen's Textbook material Subgroups. Cosets. Lagrange's theorem. Group action on sets. Orbits. References Use notes from class. Exercises Reading Subgroups. Cosets. Lagrange's theorem. Group action on sets. Orbits.References: Use notes from class. Polya's counting method. Burnside's Lemma References <a href="http://www.saylor.org/site/wp-content/uploads/2011/05/Burnsides-Lemma.pdf">Notes</a>. The example used in class was different. Exercises Reading Polya's counting method. Burnside's LemmaReferences: Notes. The example used in class was different. **Theme 5 : Evaluation Meetings**- 5 meetings- Meeting 54 : Tue, Sep 08, 10:00 am-10:50 am -
- Meeting 55 : Thu, Sep 24, 12:00 pm-12:50 pm -
- Meeting 56 : Mon, Oct 19, 11:00 am-11:50 am -
- Meeting 57 : Thu, Nov 12, 12:00 pm-12:50 pm -
- Meeting 58 : Mon, Nov 23, 09:30 am-12:30 pm -

Quiz 1 based on contents of Lectures 1 to 23 References Exercises Reading Quiz 1 based on contents of Lectures 1 to 23References: None Short Exam 1 based on contents of Lectures 1 to 31 References Exercises Reading Short Exam 1 based on contents of Lectures 1 to 31References: None Quiz 2 based on contents of Lectures 24 to 44 References Exercises Reading Quiz 2 based on contents of Lectures 24 to 44References: None Short Exam 2 based on contents of Lectures 40 to 52 References Exercises Reading Short Exam 2 based on contents of Lectures 40 to 52References: None Based on the materials covered in the entire course. References Exercises Reading Based on the materials covered in the entire course.References: None