MATH 409 Lecture 3

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

Lecture Slides

Help sessions available MTWR 19:00–21:30 in BLOC 111

Metric Spaces

Recall the definition and properties of absolute value

Given a nonempty set $X$, a metric (or distance function) on $X$ is a function $d:X\times X\to \mathbb {R}$ that satisfies the following conditions:

positivity

$d(x,y)\geq 0$ for all $x,y\in X$

$d(x,y)=0$ if and only if $x=y$

symmetry

$d(x,y)=d(y,x)$

triangle inequality

$d(x,y)\leq d(x,z+d(z,y)$

One can go from $x$ to $y$, or take a detour through $z$. When taking this detour, it has to be at least as long as going directly from $x$ to $y$

A set endowed with metric is called a metric space

Theorem. The function $d(x,y)=|y-x|$ is a metric on the real line:

Proof. $|y-x|\geq 0,|y-x|=0$ if and only if $y-x=0$, which is equivalent to $x=y$. This proves positivity.

Symmetry follows since $x-y=-(y-x)$ and $|-a|=|a|$

Finally, $d(x,y)=|y-x|=|(y-z)+(z-x)|$ and therefore $|(y-z)+(z-x)|\leq |y-z|+|z-x|$, which is equivalent to $d(x,y)\leq d(z,y)+d(z,x)$.

quod erat demonstrandum

Other examples of metric spaces:

• Euclidean space $X=\mathbb {R} ^{n}$, with $d(x,y)={\sqrt {\sum _{i=1}^{n}(y_{i}-x_{i})^{2}}}$.
• Normed vector space $X$ with norm $\|\cdot \|$ and $d(x,y)=\|y-x\|$.
• Discrete metric space on any set $X$ with $d(x,y)=1$ if $x\neq y$ and $d(x,y)=0$ if $x=y$.
• Space of sequences: let $X$ be a set of all infinite words $x=x_{1}\,x_{2}\,\ldots$ over a finite alphabet;
  • $d(x,y)=2^{-n}$ if $x_{i}=y_{i}$ for $1\leq i\leq n$ while $x_{n+1}\neq y_{n+1}$
  • $d(x,y)=0$ if $x_{i}=y_{i}$ for all $i\geq 1$.

Recall supremum and infimum

Completeness Axiom

The set $\mathbb {R}$ of real numbers is a set satisfying the following postulates:

1. $\mathbb {R}$ is a field
2. There is a strict linear order $<$ on $\mathbb {R}$ that makes it into an ordered field
3. Completeness Axiom. If a non-empty subset $E\subset \mathbb {R}$ is bounded above, then $E$ has a supremum.

Theorem 1. Suppose $X$ and $Y$ are nonempty subsets of $\mathbb {R}$ such that $a\leq b$ for all $a\in X$ and $b\in Y$. Then there exists a $c\in \mathbb {R}$ such that $a\leq c$ for all $a\in X$ and $c\leq b$ for all $b\in Y$.

Proof. The set $X$ is bounded above because all elements of $Y$ are greater than all elements of $X$. By the completeness axiom, $\sup {X}$ exists. We have $a\leq \sup {X}$ for all $a\in X$ since $\sup {X}$ is an upper bound of $X$. Besides $\sup {X}\leq b$ for any $b\in Y$ since $b$ is an upper bound of $X$ while $\sup {X}$ is the least upper bound. This supremum is $c$.

quod erat demonstrandum

Theorem 2. If a nonempty subset $E\subset \mathbb {R}$ is bounded below, then $E$ has an infimum.

Proof. Let $X$ denote the set of all lower bounds of $E$. Then any element of $X$ is less than or equal to any element of $E$. Since $E$ is bounded below, the set $X$ is not empty. By theorem 1, there exists a $c\in \mathbb {R}$ such that $a\leq c$ for all $a\in X$ and $c\leq b$ for all $b\in E$. That is $c$ is a lower bound of $E$ and an upper bound of $X$. Thus by construction there is no gap between $X$ and $E$, and so $c=\inf {E}$.

quod erat demonstrandum

Natural, Integer, and Rational Numbers

Postulate 1 guarantees $\mathbb {R}$ contains 0 and 1. Then we can define natural numbers 2 = 1+1, 3 = 2+1, etc. Last lecture, we proved that $0<1$. Repeatedly adding 1 to both sides gives $0<1<2<3\dots$.

However, The entire set of natural numbers can only be defined in an implicit way.

A set $E\subset \mathbb {R}$ is called inductive if $1\in E$, and for any real number $x$, $x\in E$ implies $x+1\in E$. The set $\mathbb {N}$ of natural numbers is the smallest inductive subset of $\mathbb {R}$. Namely, it is the intersection of all inductive subsets of $R$.

The set of integers is defined as $\mathbb {Z} =-\mathbb {N} \cup \{0\}\cup \mathbb {N}$.

The set of rationals is defined as $\mathbb {Q} =\left\{m/n~\mid ~m\in \mathbb {Z} ,n\in \mathbb {N} \right\}$.

Archimedean Principle

Theorem. [Archimedian Principle]. For any real number $\epsilon >0$, there exists a natural number $n$ such that $n\epsilon >1$.

Proof. In the case $\epsilon >1$, we can take $n=1$. Now assume $\epsilon \leq 1$. Let $E$ be the set of all natural numbers $n$ such that $n\,\epsilon \leq 1$. Observe that $E$ is nonempty ($1\in E$) and it is bounded above ($1/\epsilon$ is an upper bound). By completeness axiom, $m=\sup {E}$ exists. By definition of $\sup {E}$, there exists $n\in E$ such that $n>m-{\frac {1}{2}}$ (as otherwise, $m-{\frac {1}{2}}$ would be an upper bound for $E$). Then $n+1$ is a natural number and $m<m+{\frac {1}{2}}<n+1$. It follows that $n+1$ is not in $E$. Consequently, $\left(n+1\right)\,\epsilon >1$.

quod erat demonstrandum

This is more meaningful when $\epsilon$ is very small.

Plus, this means that $\mathbb {R}$ contains no infinitesimal (i.e. infinitely small) numbers other than 0.

Corollary. For any $a,b>0$, there exists a natural number $n$ such that $n\,a>b$. Proof involves $\epsilon ={\frac {a}{b}}$.

Density of Rational Numbers

Theorem. [Density of Rational Numbers.] For any real numbers $a$ and $b$, $a<b$, there exists a rational number $\xi$ such that $a<\xi <b$.

Proof. By the Archimedean Principle, there exists a natural number $n$ such that $n(b-a)>1$ (when $\epsilon =b-a$). Let $E$ be the set of all integers $m$ such that $m/n<b$. Observe that $E$ is bounded above ($n\,b$ is an upper bound). Let us show that the set $E$ is nonempty. If $b\geq 0$, it is obvious that $-1\in E$. If $b<0$, we have $-b>0$. By the Archimedean Principle, there exists a natural number $m$ such that $m(-nb)^{-1}>1$. Then $-{\frac {m}{n}}<b$ so that $-m\in E$. By the completeness axiom, $k=\sup {E}$ exists. By definition of $\sup {E}$, there exists $m\in E$ such that $m>k-{\frac {1}{2}}$. Then $m+1$ is an integer and $k<k+{\frac {1}{2}}<m+1$, which implies $m+1$ is not in $E$. Therefore $m/n<b\leq \left(m+1\right)/n$. Consequently, $m/n\geq b-{\frac {1}{n}}>b-(b-a)=a$. Thus $a<m/n<b$.

quod erat demonstrandum

What just happened?

Note: Don't forget to look up the hint for homework problem 1.3.3 (density of irrational numbers) in the back of the book.

Existence of Square Roots

For any $a\geq 0$, there exists a unique number $r>0$ (denoted ${\sqrt {a}}$) such that $r^{2}=a$.

Proof. There are two parts to this proof: existence and uniqueness.

(skip...)

Main idea: Consider a set $E=\left\{x>0~\mid ~x^{2}<a\right\}$ We will show that $r=\sup {E}$ is the desired number. First we need to show $\sup {E}$ exists.