– Sets and subsets

– Power set

– Common notations

– How to specify a set

Lecture 2

– The penny problem

– Set operations: union, intersection, difference and complement

– Disjoint sets

– Venn diagram

– (A \cup B)^c = A^c \cap B^c

Lecture 3

– Cardinality

– Inclusion–exclusion principle

– Cartesian plane and cartesian product

– Notation for intervals

– Functions: definition, domain, codomain and image

– Graph representation

– Absolute value

– Bounded functions

Lecture 4

– Injective, surjective and bijective functions

– Composition of functions

– Invertible functions

– Equivalence between invertible and bijective functions

Lecture 5

– Invertible functions (continuation)

– Example of how to find the inverse of a function

– Example where (f \circ g)(x) = x does not imply (g \circ f)(x) = x

– Triangle inequality

– MA-MG inequality

– Definition of statement/proposition

Lecture 6

– Negation

– Logical operators: conjunction, disjunction, conditional and biconditional

– Truth tables

– Compound propositions

– Tautology and contradiction

– Propositional equivalence

– De Morgan laws and other useful equivalence laws

Lecture 7

– Satisfiability and solutions

– Predicate logic (definitons of subject and predicate)

– Quantifiers (universal and existential)

Lecture 8

– Negation of quantified expressions

– Nested quantifiers

– Elementary methods of proof: direct proof, contrapositive and contradiction

– Observation on algebraic manipulations

– Definition of converse

– Proof strategy: looking for invariants

Lecture 9

– Peano’s axioms

– Definition of sum

– Definition of product

– Associativity, distributivity, comutativity and cancellation law

Lecture 10

– Proof of the cancellation law

– Definition of order in \mathbb{N}

– Facts about order

– The well-ordering principle

Lecture 11

– The well-ordering principle is equivalent to the induction axiom

– Strong induction is equivalent to weak induction

– For every n \in \mathbb{N}, we have 1 + \dfrac{1}{2} + \ldots + \dfrac{1}{n} \ge 1 + \dfrac{n}{2}

– For every n \in \mathbb{N}, we have 3 \vert (n^3 - n)

Lecture 12

Applications of induction:

– Sum of the first n natural numbers

– Sum of the first n odd numbers

– Fundamental theorem of arithmetic (existence)

– Let n be the nth Fibonacci number. Then, f_n > \alpha^{n-2}, where \alpha is the golden ration.

Lecture 13

– Solving questions of the mock exam

Lecture 14

This lecture was based on the following notes: construction-of-Q-and-Z

Be careful when you read it. There are some tiny mistakes.

They also defined the set \mathbb{N} containing the element 0. We don’t.

Some small adaptations are necessary to make everything work when \mathbb{N} does not contain 0.

You can find these adaptations explicitly in my notes.

– Equivalence relation

– Equivalence classes

– Proof that equivalence classes partition sets

– Definition of \mathbb{Z} using an equivalence relation in \mathbb{N} \times \mathbb{N}

– How to add, multiply and order in \mathbb{Z}

Lecture 15

– Definition of \mathbb{Q} using an equivalence relation in \mathbb{Z} \times \mathbb{N}

– Proof that we indeed have a well-defined equivalence relation

– How to add, multiply and order in \mathbb{Q}

– Existence of multiplicative inverses

– Archimedean property

Lecture 16

– Method of descent

– The equation x^2 = 2 does not have any rational solutions

– Definition of sequence

– Definition of convergence to a limit in \mathbb{Q} and examples

– Definition of Cauchy sequence and examples

Lecture 17

– Every Cauchy sequence is bounded

– Definition 3.1: equivalence relation

– Theorem 3.2: equivalence classes are either equal or disjoint

– Corollary 3.3: equivalence classes partition the ground set

– Definition 4.1: equivalence relation among Cauchy sequences

– Proposition 4.2: the relation defined in 4.1 is indeed an equivalence relation

Lecture 18

– Definition 4.3: definition of real numbers

– Definition 4.4: embedding the rational numbers into the real numbers

– Definition 4.5: sum and product of real numbers

– Proposition 4.6: sum and product in \mathbb{R} are well-defined

– Lemma 4.8: every Cauchy sequence which is not in the equivalence class of 0 is ‘far’ from 0 after a certain point

Lecture 19

– Theorem 4.7: every real number different from 0 admits a multiplicative inverse

– Definition 4.9: order in the real numbers

– Theorem 4.11: \mathbb{R} has the archimedean property

Lecture 20

– Theorem 4.12: \mathbb{Q} is dense in \mathbb{R}

– Let (x_n)_{n \in \mathbb{N}} be a non-decreasing and bounded sequence. Then, (x_n)_{n \in \mathbb{N}} is Cauchy. A proof of this can be found here.

– Lemma 4.14: the upper bound sequence (u_n)_{n \in \mathbb{N}} is non-increasing and the lower bound sequence (\ell_n)_{n \in \mathbb{N}} is non-decreasing

Lecture 21

– Theorem 4.13: \mathbb{R} has the least upper bound property

– Pigeonhole principle and introduction to Bolzano–Weierstrass. A proof can be found here.

Lecture 22

– Recalling the definition of convergent sequence: page 259, def 13.10.

– Recalling the definition of infimum and supremum: page 256, def 13.3

– Monotone convergence theorem: page 261, thm 13.16

– Limits and arithmetic: page 272, thm 14.5

Lecture 23

– Existence of \sqrt{2}: page 257, example 13.7

– Every convergent sequence has a unique limit: page 260, Lemma 13.14

– If a_n \to L and b_n - a_n \to 0, then b_n \to L: page 272, Lemma 14.3

-If a_n \to 0 and (b_n)_n is bounded, then a_nb_n \to 0 : page 274, Proposition 14.7

– The squeeze theorem: suppose that a_n \le b_n \le c_n for all n \in \mathbb{N} . If a_n \to L and c_n \to L, then also b_n \to L. Page 273, Theorem 14.6

– Bolzano–Weiestrass theorem: every bounded sequence of real numbers has a convergent subsequence. Page 277, Theorem 14.17.

Lecture 24

– Solution of the problems in the mock exam.

Lecture 25

– Theorem 14.19, page 279: Every Cauchy sequence is convergent.

– Definition 14.20, page 279: convergent series.

– Lemma 14.27, page 281: If \sum a_k converges, then a_k \to 0.

– Recalling that the harmonic series is an example where the terms tend to 0 but the series diverges (Example 14.28, page 282)

– Proposition 14.10, page 275: If (b_n)_n is a sequence such that |b_{n+1}/b_n| \to x, where x \in [0,1), then b_n \to 0.

– Theorem 14.24, page 280: \sum_{i=0}^{\infty} \beta^n = (1-\beta)^{-1} if |\beta|<1 .

Lecture 26

– Proposition 14.29, page 282: The comparison test.

– Corollary 14.30, page 283: if \sum |a_k| converges, then \sum a_k converges.

– Theorem 14.31, page 283: The ratio test.

– Example 14.32, page 284: Exponential series.

– Theorem 14.33, page 284: Root test.

Lecture 27

– Definition of deleted neighborhood, page 294

– Definition 15.4, page 294: \lim \limits_{x \to a} f(x)

– Definition 15.7, page 295: sequential limit

– Theorem 15.8, page 295: equivalence between sequential limit and limit

– Lemma 15.9, page 296: limit of sum and product of functions

– Definition 15.10, page 296: continuous functions

– Examples of non-continuous functions in one point and in all points

– Example of continuous functions: polynomials

– Proposition 15.13, page 297: squeeze theorem for continuity

Lecture 28

– Theorem 15.16, page 298: Continuity of composite functions

– Theorem 15.19, page 299: The intermediate value theorem

– Corollary 15.21, page 300: if f:[0,1]\to [0,1] is a continuous function, then it has a fixed point.

– Theorem 15.24, page 302: if f is continuous in a closed interval, then it is bounded.

– Theorem 15.24 does not hold if we have an open interval in the domain of the function.

Lecture 29

– Definition of probability space (Sample space, sigma-algebra and probability measure)

– Proposition 9.8, page 171: Elementary properties

– Modification of Problem 9.3, page 170: what is the probability that we obtain exactly 50 heads when we throw 100 coins?

– Monty-hall problem. See this lovely video in Numberphile.

Lecture 30

– Problem 9.1, page 170: the Bertrand’s Ballot problem. See page 172 for a solution, or my notes.

Lecture 31

– Definition 9.14, page 175: Conditional Probability

– Proposition 9.18, page 176? Bayes’ Formula

– Conditional probability is a probability measure. See here.

– Identically distributed random variables. See board pictures: 1, 2, 3 and 4.

Lecture 32

– Random variables with the same distribution

– Bernoulli random variables

– Independent events

– Independent random variables

– Binomial distribution

– Geometric distribution

See some of the board pictures here: 1, 2, 3, 4, 5, 6, 7, 8, 9 and 10

Lecture 33

– Definition of expected value

– Expected value of non-negative random variables

– Expected value of Bernoulli and Binomial random variables

– Linearity of the expectation

– The tail-sum formula

– Expected value of geometric random variables (using the tail-sum formula).

See some of the board pictures here: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 and 11

Lecture 34

– The coupon collector

– Problem 1: suppose that A, B and n other people line up in random order. What is the expected number of people between A and B?

– Problem 2: suppose that 2n people are partitioned into pairs at random, which each partition being equally likely. If there are n men and n women, what is the expected number of male-female coupes?

See some of the board pictures here: 1, 2, 3, 4, 5, 6, 7, 8 and 9

Lecture 35

– We Reviewed the content of the third midterm

Lecture 36

– Markov’s inequality

– Indicator functions (definition and expectation)

– Recalling what are independent random variables

– If X and Y are independent discrete random variables, then \mathbb{E}(XY) = \mathbb{E}(X)\mathbb{E}(Y)

– Definition of Variance

– The variance of a binomial random variable \text{Bin}(n,p) is np(1-p)

– Chebyshev’s inequality

See some of the board pictures here: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14 and 15.

Lecture 37

– Definition of graph

– Definition of degree and notation

– The handshaking lemma

– Every graph has an even number of vertices of odd degree

– Every graph has two vertices of same degree

– Definition of clique (complete graph)

– The number of graphs with vertex set \{1,2,\ldots,n\} is 2^{\binom{n}{2}}

– Proof of Mantel’s theorem. See Theorem 1 in these notes.

See some of the board pictures here: 1, 2, 3, 4, 5, 6, 7 and 8.

Lecture 38

– Definition of \text{ex}(n,K_3) (the extremal number of the triangle)

– Mantel’s theorem revisited: if G is a triangle-free graph on n vertices and e(G) = \text{ex}(n,K_3), then latex]G[/latex] is a complete bipartite graph, with parts of size \lfloor n/2 \rfloor and \lceil n/2 \rceil.

– Notation: G(S) denotes the graph with vertex set S and edge set \{T \subseteq S: T \in E(G)\}.

– Big Oh and little oh notation (see here, for example)

– Lemma: Let G be a graph on n vertices and at least \left (\frac{1}{2} + \varepsilon \right) \binom{n}{2} edges, where \varepsilon > 0 . Let S be a random uniformly-chosen set in V(G) of size n_0. Then, we have \mathbb{E}(e(G(S))) \ge \left (\frac{1}{2} + \varepsilon \right) \binom{n_0}{2}

– See a few board pictures (1, 2, 3 and 4) and my notes (1, 2, 3 and 4 — here r=2)

Lecture 39

– Proof of the supersaturation theorem for triangles: if e(G)\ge \left (\frac{1}{2} + \varepsilon \right) \binom{n}{2} , then G has at least \alpha n^3 triangles, where \alpha>0 is a constant depending on \varepsilon.

– Jensen’s inequality for convex functions

– Kovari–Sos–Turan theorem (for C4). See Theorem 3.1 in these notes

– See a few board pictures here: 1, 2, 3, 4, 5, 6, 7 and 8.

Lecture 40

– Finishing the proof of Kovari–Sos–Turan for C4

– Reviewing the content of the final exam