MATH 409 Lecture 4

« previous | Thursday, September 5, 2013 | next »

Lecture Slides

Solutions to Challenges

Challenge 2

Construct a strict linear order $\prec$ on the set $\mathbb{ℂ}$ such that $a\prec b$ implies $a+c\prec b+c$ for all $a,b,c\in \mathbb{ℂ}$

Given complex numbers $z_1=x_1+i{y}_1$ and $z_2=x_2+i{y}_2$, where $x_1,y_1,x_2,y_2\in \mathbb{ℝ}$ and $i=\sqrt{-1}$. Define $z_1\prec z_2$ if:

• $x_1<x_2$ and
• $x_1=x_2$ and $y_1<y_2$

Challenge 3

Construct a strict linear order $\prec$ on $\mathbb{ℝ}(x)$ of rational functions in variable $x$ with real coefficients that makes $\mathbb{ℝ}(x)$ into an ordered field.

Given rational functions $f,g\in \mathbb{ℝ}(x)$, we let $f\prec g$ if there exists $M\in \mathbb{ℝ}$ such that $f(x)<g(x)$ for all $x>M$.

Showing strict order is easy, and verifying axioms of addition and multiplication is also easy. Hard part is proving linearity:

Assume $f\ne g$ and let $h=g-f$. Then $h(x)=\frac{p(x)}{q(x)}$, where $p$ and $q$ are nonzero polynomials. Since any nonzero polynomial has only finitely many roots, there exists $M\in \mathbb{ℝ}$ such that $p$ and $q$ have no roots in the interval $(M,\mathrm{\infty })$. $h$ is continuous and nowhere zero on $(M,\mathrm{\infty })$. Therefore it maintains its sign on this interval, i.e. either $h(x)>0$ for all $x>M$ or $h(x)<0$ for all $x>M$. In the first case, $f\prec g$. In the second case, $g\prec f$.

Note: This field does not follow the Archimedean principle

General Intervals

Suppose $X$ is a stet endowed with a strict linear order $\prec$.

A subset $E\subset X$ is called an interval if with any two elements it contains all elements of $X$ that lie between them. To be precise, $a,b\in E$ and $a\prec c\prec b$ imply that $c\in E$ for all $a,b,c\in X$.

Examples:

• The empty set and all one-element subsets of $X$ are trivially intervals.
• Open finite interval $(a,b)=\{c\in X\mid a\prec c\prec b\}$, where $a,b\in X$ and $a\prec b$.
• Closed and semi-open intervals
  • $[a,b]=(a,b)\cup \{a,b\}$
  • $[a,b)=(a,b)\cup \{a\}$
  • $(a,b]=(a,b)\cup \{b\}$
• Open semi-infinite intervals
  • $(a,\mathrm{\infty })=\{c\in X\mid a\prec c\}$
  • $(-\mathrm{\infty },a)=\{c\in X\mid c\prec a\}$, where $a\in X$.
• Closed semi-infinite intervals
  • $[a,\mathrm{\infty })=(a,\mathrm{\infty })\cup \{a\}$
  • $(-\mathrm{\infty },a]=(-\mathrm{\infty },a)\cup \{a\}$
• Complete infinite interval $(-\mathrm{\infty },\mathrm{\infty })$

Intervals of the Real Line

Theorem 1. Suppose $E$ is a bounded interval of $\mathbb{ℝ}$ that consists of more than one point. Then there exist $a,b\in \mathbb{ℝ}$ with $a<b$ such that $E=(a,b)$ or $[a,b)$ or $(a,b]$, or $[a,b]$.

Theorem 2. Suppose $E$ is an interval of $\mathbb{ℝ}$ bounded above but unbounded below. Then $\mathrm{\exists }a\in \mathbb{ℝ}$ such that $E=(-\mathrm{\infty },a)$ or $(-\mathrm{\infty },a]$.

Theorem 3. Suppose $E$ is an interval of $\mathbb{ℝ}$ bounded below but unbounded above. Then $\mathrm{\exists }a\in \mathbb{ℝ}$ such that $E=(a,\mathrm{\infty })$ or $[a,\mathrm{\infty })$.

Theorem 4. Suppose $E$ is an interval of $\mathbb{ℝ}$ that is neither bounded above nor bounded below. Then $E=\mathbb{ℝ}$.

Note: Next challenge: Prove theorems 1 and 4

Natural Numbers, Integers, and Rationals

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{ℝ}$.

Note: The set $\mathbb{\mathbb{N}}$ is well defined. Namely, it is the intersection of all inductive subsets of $\mathbb{ℝ}$.

Integers are defined as

$\mathbb{\mathbb{Z}}=-\mathbb{\mathbb{N}}\cup \left\{0\right\}\cup \mathbb{\mathbb{N}}$

Rationals are defined as

$\mathbb{\mathbb{Q}}=\{\frac{p}{q}\mid p\in \mathbb{\mathbb{Z}}\text{ and }q\in \mathbb{\mathbb{N}}\}$

Properties of Natural Numbers

• 1 is the least natural number: the interval $[1,\mathrm{\infty })$ is an inductive set. Hence $\mathbb{\mathbb{N}}\subset [1,\mathrm{\infty })$.

• If $n\in \mathbb{\mathbb{N}}$, then $n-1\in \mathbb{\mathbb{N}}\cup \{0\}$: Let $E$ be set of all $n\in \mathbb{\mathbb{N}}$ such that $n-1\in \mathbb{\mathbb{N}}\cup \{0\}$. Then $1\in E$ as $1-1=0$. Besides, for any $n\in E$ we have $(n+1)-1=n\in \mathbb{\mathbb{N}}$ so that $n+1\in E$. Therefore $E$ is an inductive set. Then $\mathbb{\mathbb{N}}\subset E$, which implies that $E=\mathbb{\mathbb{N}}$.

more appropriately, that should be a ⊆

• If $n\in \mathbb{\mathbb{N}}$, then the open interval $(n-1,n)$ contains no natural numbers: Let $E$ be the set of all $n\in \mathbb{\mathbb{N}}$ such that $(n-1,n)\cap \mathbb{\mathbb{N}}=\mathrm{\varnothing }$. Then $1\in E$ as $\mathbb{\mathbb{N}}\subset [1,\mathrm{\infty })$. Now assume $n\in E$ and take any $x\in (n,n+1)$. We have $x-1\ne 0$ since $x>n\ge 1$, and $x-1\in ̸\mathbb{\mathbb{N}}$ since $x-1\in (n-1,n)$. By the above, $x\in ̸\mathbb{\mathbb{N}}$. Thus $E$ is an inductive set, which implies $E=\mathbb{\mathbb{N}}$.

Principle of Well-Ordering

Suppose $X$ is a set endowed with a strict linear order $\prec$. We say that a subset $Y\subset X$ is well-ordered with respect to $\prec$ if any nonempty subset of $Y$ has a least element.

Theorem. The set $\mathbb{\mathbb{N}}$ is well-ordered with respect to the natural ordering of the real line $\mathbb{ℝ}$.

Proof. Let $E$ be an arbitrary nonempty subset of $\mathbb{\mathbb{N}}$. The set $E$ is bounded below since 1 is a lower bound of $\mathbb{\mathbb{N}}$. Therefore $m=\inf E$ exists. Since $m$ is a lower bound of $E$ while $m+1$ is not, we can find $n\in E$ such that $m\le n<m+1$. As shown before, the interval $(n-1,n)$ is disjoint from $\mathbb{\mathbb{N}}$. Then $(-\mathrm{\infty },n)=(-\mathrm{\infty },m)\cup (n-1,n)$ is disjoint from $E$, which implies that $n$ is a lower bound of $E$. Hence $n\le \inf E=m$, so $n=m=\inf E$ by weak antisymmetry. Thus $n$ is the least element of $E$.

Principle of Mathematical Induction

Theorem. Let $P(n)$ be an assertion depending on a natural variable $n$. Suppose that

• $P(1)$ holds,
• whenever $P(k)$ holds, so does $P(k+1)$.

Then $P(n)$ holds for all $n\in \mathbb{\mathbb{N}}$.

Proof. Let $E$ be the set of all natural numbers $n$ such that $P(n)$ holds. Clearly $E$ is an inductive set. Therefore $\mathbb{\mathbb{N}}\subset E$ which implies that $E=\mathbb{\mathbb{N}}$.

quod erat demonstrandum

Note: The assertion $P(1)$ is called the basis of induction. The implication $P(k)⟹P(k+1)$ is called the induction step.

Examples of assertions $P(n)$:

• $1+2+\dots +n=\frac{n(n+1)}{2}$
• $n(n+1)(n+2)$ is divisible by 6
• $n=2p+3q$ for some $p,q\in \mathbb{\mathbb{Z}}$

We can use mathematical induction for $n\in \mathbb{\mathbb{Z}}$ by starting with a different (shifted) base.

Strong Induction

Theorem. Let $P(n)$ be an assertion depending on a natural variable $n$. Suppose that $P(n)$ holds whenever $P(k)$ holds for all natural $k<n$. Then $P(n)$ holds for all $n\in \mathbb{\mathbb{N}}$.

In other words, for $n=1$, the assuption of the theorem means that $P(1)$ holds unconditionally. For $n=2$, it means that $P(1)$ implies $P(2)$. For $n=3$, it means that $P(1)$ and $P(2)$ imply $P(3)$. And so on...

Proof. For any $n\in \mathbb{\mathbb{N}}$ we define a new assertion $Q(n)$ "$P(k)$ holds for any natural $k\le n$". Then $Q(1)$ is equivalent to $P(1)$, in particular, it holds. By assumption $Q(n)$ implies $P(n+1)$ for any $n\in \mathbb{\mathbb{N}}$. Moreover, $Q(n+1)$ holds if and only if both $Q(n)$ and $P(n+1)$ hold. Therefore $Q(n)$ implies $Q(n+1)$ for all $n\in \mathbb{\mathbb{N}}$. By the principle of mathematical induction, $Q(n)$ holds for all $n\in \mathbb{\mathbb{N}}$ and thus $P(n)$ holds as well.

quod erat demonstrandum

Functions

A function (or map) $f:X\to Y$ is an assignment: to each $x\in X$ we assign an element $f(x)\in Y$.

The graph of the function $f:X\to Y$ is defined as the subset of $X\times Y$ consisting of all pairs of the form $(x,f(x))$ for $x\in X$. Two functions are considered the same if their graphs coincide

Properties

A function $f:X\to Y$ is surjective (or onto) if for each $y\in Y$, there exists at least one $x\in X$ such that $f(x)=y$.

The function $f$ is injective (or one-to-one) if $f(x^{\prime })=f(x)$ implies $x=x^{\prime }$. This can be tested with a horizontal line on graph: for all horizontal lines, the graph of $f$ should intersect only once.

A function is bijective if and only if it is both injective and surjective.

Inverse Function

Suppose we have two functions $f:X\to Y$ and $g:Y\to X$. We say that $g$ is the inverse function of $f$ (denoted $f^{-1}$) if $y=f(x)$ if and only if $g(y)=x$ for all $x\in X$ and $y\in Y$.

Theorem 1. The inverse function $f^{-1}$ exists if and only if $f$ is bijective

Theorem 2. A function $g:Y\to X$ is an inverse function of a function $f:X\to Y$ if and only if $(g\circ f)(x)=x$ for all $x\in X$ and $(f\circ g)(x)=y$ for all $y\in Y$.