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{ℝ}$ that satisfies the following conditions:

positivity

$d(x,y)\ge 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)\le 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|\ge 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)|\le |y-z|+|z-x|$, which is equivalent to $d(x,y)\le d(z,y)+d(z,x)$.

quod erat demonstrandum

Other examples of metric spaces:

• Euclidean space $X={\mathbb{ℝ}}^n$, with $d(x,y)=\sqrt{\sum _{i=1}^n(y_i-x_i{)}^2}$.
• Normed vector space $X$ with norm $\Vert \cdot \Vert$ and $d(x,y)=\Vert y-x\Vert$.
• Discrete metric space on any set $X$ with $d(x,y)=1$ if $x\ne 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\dots$ over a finite alphabet;
  • $d(x,y)=2^{-n}$ if $x_i=y_i$ for $1\le i\le n$ while $x_{n+1}\ne y_{n+1}$
  • $d(x,y)=0$ if $x_i=y_i$ for all $i\ge 1$.

Recall supremum and infimum

Completeness Axiom

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

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

Theorem 1. Suppose $X$ and $Y$ are nonempty subsets of $\mathbb{ℝ}$ such that $a\le b$ for all $a\in X$ and $b\in Y$. Then there exists a $c\in \mathbb{ℝ}$ such that $a\le c$ for all $a\in X$ and $c\le 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\le \sup X$ for all $a\in X$ since $\sup X$ is an upper bound of $X$. Besides $\sup X\le 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{ℝ}$ 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{ℝ}$ such that $a\le c$ for all $a\in X$ and $c\le 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{ℝ}$ 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{ℝ}$ is called inductive if $1\in E$, and for any real number $x$, $x\in E$ implies $x+1\in E$. The set $\mathbb{\mathbb{N}}$ of natural numbers is the smallest inductive subset of $\mathbb{ℝ}$. Namely, it is the intersection of all inductive subsets of $R$.

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

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

Archimedean Principle

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

Proof. In the case $ϵ>1$, we can take $n=1$. Now assume $ϵ\le 1$. Let $E$ be the set of all natural numbers $n$ such that $nϵ\le 1$. Observe that $E$ is nonempty ($1\in E$) and it is bounded above ($1/ϵ$ 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, $(n+1)ϵ>1$.

quod erat demonstrandum

This is more meaningful when $ϵ$ is very small.

Plus, this means that $\mathbb{ℝ}$ 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 $na>b$. Proof involves $ϵ=\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 $ϵ=b-a$). Let $E$ be the set of all integers $m$ such that $m/n<b$. Observe that $E$ is bounded above ($nb$ is an upper bound). Let us show that the set $E$ is nonempty. If $b\ge 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\le (m+1)/n$. Consequently, $m/n\ge 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\ge 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=\{x>0\mid x^2<a\}$ We will show that $r=\sup E$ is the desired number. First we need to show $\sup E$ exists.