MATH 409 Lecture 3

From Notes
Jump to navigation Jump to search

« 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×X→ℝ that satisfies the following conditions:

positivity
d(x,y)≥0 for all x,y∈X
d(x,y)=0 if and only if x=y
symmetry
d(x,y)=d(y,x)
triangle inequality
d(x,y)≤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|≥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)|≤|y−z|+|z−x|, which is equivalent to d(x,y)≤d(z,y)+d(z,x).

quod erat demonstrandum


Other examples of metric spaces:

  • Euclidean space X=ℝn, with d(x,y)=∑i=1n(yi−xi)2.
  • Normed vector space X with norm ‖⋅‖ and d(x,y)=‖y−x‖.
  • Discrete metric space on any set X with d(x,y)=1 if x≠y and d(x,y)=0 if x=y.
  • Space of sequences: let X be a set of all infinite words x=x1x2… over a finite alphabet;
    • d(x,y)=2−n if xi=yi for 1≤i≤n while xn+1≠yn+1
    • d(x,y)=0 if xi=yi for all i≥1.

Recall supremum and infimum


Completeness Axiom

The set ℝ of real numbers is a set satisfying the following postulates:

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

Theorem 1. Suppose X and Y are nonempty subsets of ℝ such that a≤b for all a∈X and b∈Y. Then there exists a c∈ℝ such that a≤c for all a∈X and c≤b for all b∈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≤sup⁡X for all a∈X since sup⁡X is an upper bound of X. Besides sup⁡X≤b for any b∈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⊂ℝ 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∈ℝ such that a≤c for all a∈X and c≤b for all b∈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 ℝ 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….

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

A set E⊂ℝ is called inductive if 1∈E, and for any real number x, x∈E implies x+1∈E. The set ℕ of natural numbers is the smallest inductive subset of ℝ. Namely, it is the intersection of all inductive subsets of R.

The set of integers is defined as ℤ=−ℕ∪{0}∪ℕ.

The set of rationals is defined as ℚ={m/n∣m∈ℤ,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 ϵ≤1. Let E be the set of all natural numbers n such that nϵ≤1. Observe that E is nonempty (1∈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∈E such that n>m−12 (as otherwise, m−12 would be an upper bound for E). Then n+1 is a natural number and m<m+12<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 ℝ 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 ϵ=ab.


Density of Rational Numbers

Theorem. [Density of Rational Numbers.] For any real numbers a and b, a<b, there exists a rational number ξ such that a<ξ<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≥0, it is obvious that −1∈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 −mn<b so that −m∈E. By the completeness axiom, k=sup⁡E exists. By definition of sup⁡E, there exists m∈E such that m>k−12. Then m+1 is an integer and k<k+12<m+1, which implies m+1 is not in E. Therefore m/n<b≤(m+1)/n. Consequently, m/n≥b−1n>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≥0, there exists a unique number r>0 (denoted a) such that r2=a.

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

(skip...)

Main idea: Consider a set E={x>0∣x2<a} We will show that r=sup⁡E is the desired number. First we need to show sup⁡E exists.