Appendix A — Mathematical Foundations

A.1 Sets

The following statements are True or False?

Exercise A.1 \mathbb{Q}\subsetneq\mathbb{R}?

Solution.

True

Note that A\subsetneq B denotes a proper subset. The set of reals \mathbb{R} contains the rationals (e.g. numbers of the form p/q for integers p,q) and the irrationals (e.g. the numbers e,\pi, etc.).

Exercise A.2 \mathbb{Z}\subset\mathbb{N}

Solution.

False

Note that A\subset B denotes a subset, without the restriction of being proper. So, A\subset B implies that either A=B or A is a proper subset of B. Since \mathbb{Z}, the set of integers, has all the naturals (\mathbb{N}) and more (e.g. 0,-1,-2), therefore neither of the above is true.

Exercise A.3 A\cap\emptyset=\emptyset

Solution.

True

Exercise A.4 A\cup B\subsetneq B

Solution.

False

Exercise A.5 For two finite sets A and B, we have |A\cup B|=|A|+|B|.

Solution.

False (i.e., not true in general)

To show that the statement is false, we need to pick just one particular example of A,B such that the relation holds false!

We pick A=\{1, 2, 3\} and B=\{1, 2\}.

Exercise A.6 A\cap(B\cup C)=(A\cap B)\cup(A\cap C). Draw to illustrate.

Solution.

True

This property is known as the distributive property of set intersection.

Exercise A.7 (A\cup B)^c=A^c\cap B^c.

Solution.

True

This formula is known as DeMorgan’s Law of set complementation.

Exercise A.8 For a finite set A, its power set, denoted by \mathcal{P}(A), has 2^{|A|} many elements.

Solution.

True

A.2 Functions

Exercise A.9 Draw the graphs of \log_{e}(x), the natural logarithm function.

Exercise A.10 How is the above graph different from the graph of \log_{2}(x)?

Exercise A.11 Draw the graph of x^2, \sqrt{x}, and x in the same plot.

Exercise A.12 Can you find an m such that the line y=mx stays above the graph of \sqrt{x} for any large positive x?

Exercise A.13 Can you find an m such that the line y=mx stays above the graph of x^2 for any large positive x?

A.3 Summation Notation, Series

  1. Sum of natural numbers: \sum_{k=1}^n k=\frac{n(n+1)}{2}. \tag{A.1}

  2. Finite geometric series: \sum_{k=0}^n x^k=\frac{x^{n+1}-1}{x-1}. \tag{A.2}

  3. Infinite geometric series for |x|<1: \sum_{k=0}^\infty x^k=\frac{1}{1-x}. \tag{A.3}

  4. For |x|<1: \sum_{k=0}^\infty kx^k=\frac{x}{(1-x)^2}. \tag{A.4}

A.4 Mathematical Induction

Exercise A.14 What is mathematical induction?

Exercise A.15 Prove the first identity above using mathematical induction.