Unless otherwise specified, all readings are in RosenBook. As always, the future is uncertain, so you should take parts of the schedule that haven't happened yet with a grain of salt.

1. Detailed schedule

2008-09-03

WhatYouShouldKnowAboutMath. WhyYouShouldKnowAboutMath. MathematicalLogic in general; PropositionalLogic in particular. Readings: §1.1.

2008-09-05

More PropositionalLogic: tautologies and logical equivalences. More about implication: converses, inverses, and contraposition. Readings: §1.2.

2008-09-08

PredicateLogic. Readings: §§1.3–1.4.

2008-09-10

InferenceRules and ProofTechniques. Direct proof, proof by contraposition, proof by cases. Readings: §§1.5–1.7. In class I mentioned this website that attempts to collect machine-verifiable proofs of basic mathematical results; it may be worth looking at it just to see how horrendous a detailed machine-verifiable proof can get. Most published proofs in mathematics and related disciplines tend to be "sketchier"—leaving out many details the reader is expected to infer on their own. This has the advantage of making proofs comprehensible to humans (by including only the important points), but may mean that these proofs are not, in fact, correct in all details. See here (PDF file) for a recent editorial lamenting the possible negative effects of this.

2008-09-12

More ProofTechniques, especially those useful for quantified statements: proof by choosing, proof by construction, proof by counterexample, proof by instantiation. Indirect proof (proof by contradiction) and proof by elimination.

2008-09-15

SetTheory basics. Naive set theory; axiomatic set theory up to axiom of the power set. Readings: §§2.1–2.2.

2008-09-17

More axiomatic SetTheory: the axiom schema of specification (which gives set comprehension and intersection). Proving things about sets. The axiom of infinity and its consequences.

2008-09-19

Functions basics: Cartesian product of two sets, relations, functions, sequences. Injections, surjections, and bijections. Readings: §2.3.

2008-09-22

More Functions: Composition and inverses. How bijections define the size of a set.

2008-09-24

Recursion and InductionProofs: simple induction, recursive definitions. Readings: §4.1.

2008-09-26

More InductionProofs: SolvingRecurrences using guess-but-verify, SummationNotation. Readings: §2.4 up to p. 158.

2008-09-29

Still more InductionProofs: strong induction and structural induction. Examples: prime factorizations, game trees, monotone Boolean formulas. Readings: §§4.2–4.3.

2008-10-01

HowToCount: Counting as bijection. Countable and uncountable sets. Readings: §2.4 pp. 158–160.

2008-10-03

HowToCount: Rules for counting. Readings: §§5.1–5.2.

2008-10-06

HowToCount: Permutations, combinations, and BinomialCoefficients. Readings: §§5.3–5.4.

2008-10-08

HowToCount: More BinomialCoefficients. The InclusionExclusion formula. Readings: §7.5.

2008-10-10

Start of ProbabilityTheory: probability spaces and events. Probability of the union of two events. Independence. Readings: §§6.1–6.2.

2008-10-13

More ProbabilityTheory: conditional probability. Readings: §6.3.

2008-10-15

RandomVariables and expectation. Readings: §6.4.

2008-10-17

More RandomVariables. Markov's inequality. Variance and Chebyshev's inequality.

2008-10-20

The ProbabilisticMethod. Alternative formula for variance. Variance of a sum. Covariance.

2008-10-22

Start of GeneratingFunctions. BinomialCoefficients with unusual upper indices. Readings: §7.4.

2008-10-24

The midterm exam will be given Friday, 2008-10-24 at the usual class time and location. It will be a closed-book, cumulative exam covering all material discussed in lecture prior to the test date.

• 2008 midterm sample solutions: 2008-midterm-solutions.pdf.

• 2008 midterm without solutions: 2008-midterm.pdf.

• 2007 midterm sample solutions: 2007-midterm-solutions.pdf.

• 2005 midterm sample solutions: 2005-midterm-solutions.pdf.

• 2005 midterm without solutions: 2005-midterm.pdf.

2008-10-27

Generating GeneratingFunctions: sums, products, pointing, composition and repetition. Getting coefficients out of generating functions using the binomial theorem.

2008-10-29

More GeneratingFunctions: solving recurrences; getting coefficients using partial fraction expansions.

2008-10-31

The DivisionAlgorithm and ModularArithmetic. Readings: §3.4. Also much flaming about learning theory, artificial intelligence, and the awesome and seemingly unattainable power of NP oracles, which was somehow vaguely inspired by the apparent difficulty of factoring. (You are not responsible for this.)

2008-11-03

More ModularArithmetic. Start of NumberTheory: primes and divisibility. Euclid's GCD algorithm. Readings: §3.5.

2008-11-05

More NumberTheory: the extended Euclidean algorithm and applications. Readings: §3.7.

2008-11-07

Relations: basic properties. Readings: §§8.1, 8.3, and 8.4.

2008-11-10

More Relations: equivalence relations and partial orders. Readings: §§8.5–8.6.

2008-11-12

Still more Relations: closures, pre-orders, maximum/maximal/minimum/minimal elements, lattices.

2008-11-14

Start of GraphTheory: digraphs, graphs, basic graph terminology, some standard graphs. Readings: §§9.1–9.2.

2008-11-17

More GraphTheory: subgraphs, products, homomorphisms and isomorphisms. Readings: §9.3.

2008-11-19

GraphTheory: paths, cycles, and connectivity properties. Readings: §9.4.

2008-11-21

LinearAlgebra: matrices, vectors, matrix multiplication and inverses. Readings: §3.8.

2008-12-01

LinearAlgebra and geometry: dot-products, orthogonality, linear transformations.

2008-12-03

AlgebraicStructures: magmas, semigroups, monoids, groups, abelian groups. Homomorphisms and isomorphisms.

2008-12-05

A little bit more about AlgebraicStructures: rings, fields, and ordered fields, with a brief mention of the surreal numbers. Some tricks for ProvingInequalities, including LagrangeMultipliers.