MATH 409 Lecture 5

« previous | Tuesday, September 10, 2013 | next »

Lecture Slides

Review

• Principle of Well-Ordering
• Principle of Mathematical Induction
• Strong Induction

Inductive Definition

Now we can use induction to define structures recursively. For example,

• The power $a^{n}$ of a number is $a^{n}=a^{n-1}\,a$, where $a^{0}=1$.
• Factorial $n!$ is $n!=(n-1)!\,n$, where $0!=1$.
• Fibonacci numbers: $F_{n}=F_{n-1}+F_{n-2}$, where $F_{1}=F_{2}=1$.

Binomial Coefficients

For any integers $0\leq k\leq n$, we define the binomial coefficient ${\binom {n}{k}}$ ($n$ choose $k$) by

${\binom {n}{k}}={\frac {n!}{k!\,(n-k)!}}\,\!$

If $k>0$, then

${\binom {n}{k}}={\frac {n\,(n-1)\dots (n-k+1)}{1\cdot 2\dots k}}\,\!$

"$n$ choose $k$" refers to the fact that ${\binom {n}{k}}$ is the number of all $k$-element subsets of an $n$-element set.

Lemma. A helpful recursive form

${\binom {n+1}{k}}={\binom {n}{k-1}}+{\binom {n}{k}}$

Proof.

${\begin{aligned}{\binom {n}{k-1}}+{\binom {n}{k}}&={\frac {n!}{(k-1)!\,(n-k+1)!}}+{\frac {n!}{k!\,(n-k)!}}\\&={\frac {n!}{(k-1)!\,(n-k)!}}\,\left({\frac {1}{n-k+1}}+{\frac {1}{k}}\right)\\&={\frac {n!}{(k-1)!\,(n-k)!}}\cdot {\frac {n+1}{k\,(n-k+1)}}\\&={\frac {(n+1)!}{k!\,(n-k+1)!}}\\&={\binom {n+1}{k}}\end{aligned}}$

quod erat demonstrandum

Pascal's Triangle

The lemma formula above allows us to compute coefficients recursively. The results are usually formatted in a triangular array called Pascal's Triangle, where ${\binom {n}{k}}$ is the $k$^th number in the $n$^th row of the triangle. (numbering starts from 0)

                1
              1   1
            1   2   1
          1   3   3   1
        1   4   6   4   1
      1   5  10  10   5   1
    1   6  15  20  15   6   1
  1   7  21  35  35  21   7   1
1   8  28  56  70  56  28   8   1

Binomial Expansion

Theorem. For any $a,b\in \mathbb {R}$ and $n\in \mathbb {N}$,

$(a+b)^{n}=\sum _{k=0}^{n}{\binom {n}{k}}\,a^{n-k}\,b^{k}$

Proof by induction. Basis. In the case $n=1$, the formula is trivial.

Induction. Assume that the formula holds for a particular value of $n$. Then

${\begin{aligned}(a+b)^{n+1}&=(a+b)\,(a+b)^{n}\\&=(a+b)\,\sum _{k=0}^{n}{\binom {n}{k}}\,a^{n-k}\,b^{k}\\&=\sum _{k=0}^{n}{\binom {n}{k}}\,a^{n-k+1}\,b^{k}+\sum _{k=0}^{n}{\binom {n}{k}}\,a^{n-k}\,b^{k+1}\\&=\sum _{k=0}^{n}{\binom {n}{k}}\,a^{n-k+1}\,b^{k}+\sum _{k=1}^{n+1}{\binom {n}{k-1}}\,a^{n-k+1}\,b^{k}\\&={\binom {n}{0}}\,a^{n+1}+\sum _{k=1}^{n}\left({\binom {n}{k}}+{\binom {n}{k-1}}\right)\,a^{n-k+1}\,b^{k}+{\binom {n}{n}}\,b^{n+1}\\&={\binom {n+1}{0}}\,a^{n+1}+\sum _{k=1}^{n}{\binom {n+1}{k}}\,a^{n+1-k}\,b^{k}+{\binom {n+1}{n+1}}\,b^{n+1}\\&=\sum _{k=0}^{n+1}{\binom {n+1}{k}}\,a^{n+1-k}\,b^{k}\end{aligned}}$

Which completes the induction step.

quod erat demonstrandum

Functions

(See MATH 409 Lecture 4#Functions→)

Composition

The composition of functions $f:X\to Y$ and $g:Y\to Z$ is a function from $X$ to $Z$ denoted $g\circ f$, that is defined by $\left(g\circ f\right)\left(x\right)=g\left(f\left(x\right)\right)$ for $x\in X$.

Properties

• If $f$ and $g$ are one-to-one (injective), then composition $g\circ f$ is also one-to-one. (converse is not necessarily true; if $g\circ f$ is injective, then we only know that $f$ is injective)
• Similarly, if $f$ and $g$ are onto (surjective), then the composition $g\circ f$ is also onto. (converse is not necessarily true; if $g\circ f$ is surjective, then we only know that $g$ is surjective)
• $f$ and $g$ are bijective if and only if their composition $f\circ g$ is bijective
• If $f$ and $g$ are invertible, then their composition $g\circ f$ is also invvertible, and $\left(g\circ f\right)^{-1}=f^{-1}\circ g^{-1}$
• If $id_{Z}$ denotes the identity function on set $Z$, then $f\circ id_{X}=f=id_{Y}\circ f$ for any function.
• for any functions $f:X\to Y$ and $g:Y\to X$, we have $g=f^{-1}$ iff $g\circ f=id_{X}$ and $f\circ g=id_{Y}$

Images and Preimages

Given a function $f:X\to Y$, the image of a set $E\subset X$ under $F$, denoted $f(E)$ is a subset of $Y$ defined by $f(e)=\left\{f(x)~\mid ~x\in E\right\}$.

The preimage (or inverse image) of a set $D\subset Y$ under $f$, denoted $f^{-1}(D)$, is a subset of $X$ defined by $f^{-1}(D)=\left\{x\in X~\mid ~f(x)\in D\right\}$

Remark: If the function $f$ is invertible, then the pre-image $f^{-1}(D)$ is also the image of $D$ under the inverse function $f^{-1}$. However, $f^{-1}(D)$ is well-defined even if $f$ is not invertible.

Properties

• $f\left(\bigcup _{\alpha \in I}E_{\alpha }\right)=\bigcup _{\alpha \in I}f(E_{\alpha })$, $f(\bigcap _{\alpha \in I}E_{\alpha })\subset \bigcap _{\alpha \in I}f(E_{\alpha })$
• Same as previous for $f^{-1}$ and $D$
• $f^{-1}(D\setminus D_{0})=f^{-1}(D)\setminus f^{-1}(D_{0})$

Cardinality

Given two sets $A$ and $B$, ew say that $A$ is of the same cardinality as $B$ if there exists a bijective function $f:A\to B$. Notation: $|A|=|B|$.

Theorem. The relation "is of the same cardinality as" is an equivalence relation. In other words, it is:

• reflexive ($|A|=|A|$)
• symmetric ($|A|=|B|$ implies $|B|=|A|$), and
• transitive ($|A|=|B|$ and $|B|=|C|$ implies Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle |A| = |C|} )

Proof. Since bijective functions show that two sets are of the same cardinality,

• Reflexivity: The identity map Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle id_A : A \to A} is bijective.
• Symmetry: If Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f} is a bijection of Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle A} onto Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle B} , then the inverse map $f^{-1}$ is a bijection of Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle B} onto Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle A} .
• Transitivity: If Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f : A \to B} and Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle g : B \to C} are bijections, then the composition Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle g \circ f} is a bijection of Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle A \to C} .

quod erat demonstrandum

Countable and Uncountable Sets

A nonempty set is finite if it is of the same cardinality as Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \left\{ 1,2,\ldots,n \right\} = [1,n] \cap \mathbb{N}} for some Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n \in \mathbb{N}} . Otherwise, it is infinite.

An infinite set is called countable (or countably infinite) if it is of the same cardinality as Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathbb{N}} . Otherwise it is uncountable (or uncountably infinite).

An infinite set Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle E} is countable if it is possible to arrange all elements of Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle E} into a single sequence (an infinite list) Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x_1, x_2, \ldots} .

Countable Sets

Examples:

• Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathbb{N}} (natural numbers)
• Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 2 \mathbb{N}} (even numbers)
• Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathbb{Z}} (integers)
• Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathbb{N}\times \mathbb{N}} (pairs of natural numbers)
• Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathbb{Q}} (rational numbers, extension of above)
• Algebraic Numbers (roots of nonzero polynomials with integer coefficients)

The last bullet will be a problem on the next homework, and the hint is to count the number of polynomials first then count the roots. The third property below will also be useful

Properties

• Any infinite set contains a countable subset
• Any infinite subset of a countable set is also countable.
• The union of any finite or countable sets is also finite or countable

Uncountable Sets

Theorem. The set Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathbb{R}} is uncountable.

Proof. It is enough to prove that the interval Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle (0,1)} is uncountable. Assume the contrary. Then all numbers from Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle (0,1)} can be arranged into an infinite list Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x_1, x_2, \ldots} . Any number Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x \in (0,1)} admits a decimal expansion of the form Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 0.d_1d_2d_3\ldots} , where each digit Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle d_i} is in Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \left\{ 0,1,2,3,4,5,6,7,8,9 \right\}} . In particular,

${\begin{aligned}x_{1}&=0.{\color {blue}d_{11}}d_{12}d_{13}d_{14}d_{15}\ldots \\x_{2}&=0.d_{21}{\color {blue}d_{22}}d_{23}d_{24}d_{25}\ldots \\x_{3}&=0.d_{31}d_{32}{\color {blue}d_{33}}d_{34}d_{35}\ldots \\x_{4}&=0.d_{41}d_{42}d_{43}{\color {blue}d_{44}}d_{45}\ldots \\x_{5}&=0.d_{51}d_{52}d_{53}d_{54}{\color {blue}d_{55}}\ldots \end{aligned}}$

Now for any $n\in \mathbb {N}$, choose a decimal digit Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \tilde{d}_n} such that Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \tilde{d}_n \ne d_{nn}} and Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \tilde{d}_n} is neither Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 0} nor Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 9} . Then Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 0.\tilde{d}_1\tilde{d}_2\tilde{d}_3\ldots} is the decimal expansion of some number Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \tilde{x} \in (0,1)} . By construction, it is different from all expansions in the list. Although some real numbers admit two decimal expansions (e.g. Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 0.5000\ldots = 0.4999\ldots} ), the condition ${\tilde {d}}_{n}\not \in \{0,9\}$ ensures that Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \tilde{x}} is not such a number. Thus Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \tilde{x}} is not listed. CONTRADICTION!

quod erat demonstrandum