# MATH 409 Lecture 4

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

Lecture Slides

## Solutions to Challenges

### Challenge 2

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

Given complex numbers ${\displaystyle z_{1}=x_{1}+i\,y_{1}}$ and ${\displaystyle z_{2}=x_{2}+i\,y_{2}}$, where ${\displaystyle x_{1},y_{1},x_{2},y_{2}\in \mathbb {R} }$ and ${\displaystyle i={\sqrt {-1}}}$. Define ${\displaystyle z_{1}\prec z_{2}}$ if:

• ${\displaystyle x_{1} and
• ${\displaystyle x_{1}=x_{2}}$ and ${\displaystyle y_{1}

### Challenge 3

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

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

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

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

Note: This field does not follow the Archimedean principle

## General Intervals

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

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

Examples:

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

### Intervals of the Real Line

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

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

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

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

Note: Next challenge: Prove theorems 1 and 4

## Natural Numbers, Integers, and Rationals

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

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

Integers are defined as

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

Rationals are defined as

${\displaystyle \mathbb {Q} =\left\{{\frac {p}{q}}~\mid ~p\in \mathbb {Z} {\mbox{ and }}q\in \mathbb {N} \right\}}$

### Properties of Natural Numbers

• 1 is the least natural number: the interval ${\displaystyle [1,\infty )}$ is an inductive set. Hence ${\displaystyle \mathbb {N} \subset [1,\infty )}$.
• If ${\displaystyle n\in \mathbb {N} }$, then ${\displaystyle n-1\in \mathbb {N} \cup \{0\}}$: Let ${\displaystyle E}$ be set of all ${\displaystyle n\in \mathbb {N} }$ such that ${\displaystyle n-1\in \mathbb {N} \cup \{0\}}$. Then ${\displaystyle 1\in E}$ as ${\displaystyle 1-1=0}$. Besides, for any ${\displaystyle n\in E}$ we have ${\displaystyle (n+1)-1=n\in \mathbb {N} }$ so that ${\displaystyle n+1\in E}$. Therefore ${\displaystyle E}$ is an inductive set. Then ${\displaystyle \mathbb {N} \subset E}$, which implies that ${\displaystyle E=\mathbb {N} }$.
more appropriately, that should be a ⊆
• If ${\displaystyle n\in \mathbb {N} }$, then the open interval ${\displaystyle (n-1,n)}$ contains no natural numbers: Let ${\displaystyle E}$ be the set of all ${\displaystyle n\in \mathbb {N} }$ such that ${\displaystyle (n-1,n)\cap \mathbb {N} =\emptyset }$. Then ${\displaystyle 1\in E}$ as ${\displaystyle \mathbb {N} \subset [1,\infty )}$. Now assume ${\displaystyle n\in E}$ and take any ${\displaystyle x\in (n,n+1)}$. We have ${\displaystyle x-1\neq 0}$ since ${\displaystyle x>n\geq 1}$, and ${\displaystyle x-1\not \in \mathbb {N} }$ since ${\displaystyle x-1\in (n-1,n)}$. By the above, ${\displaystyle x\not \in \mathbb {N} }$. Thus ${\displaystyle E}$ is an inductive set, which implies ${\displaystyle E=\mathbb {N} }$.

### Principle of Well-Ordering

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

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

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

### Principle of Mathematical Induction

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

• ${\displaystyle P(1)}$ holds,
• whenever ${\displaystyle P(k)}$ holds, so does ${\displaystyle P(k+1)}$.

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

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

quod erat demonstrandum
Note: The assertion ${\displaystyle P(1)}$ is called the basis of induction. The implication ${\displaystyle P(k)\implies P(k+1)}$ is called the induction step.

Examples of assertions ${\displaystyle P(n)}$:

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

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

### Strong Induction

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

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

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

quod erat demonstrandum

## Functions

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

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

### Properties

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

The function ${\displaystyle f}$ is injective (or one-to-one) if ${\displaystyle f(x')=f(x)}$ implies ${\displaystyle x=x'}$. This can be tested with a horizontal line on graph: for all horizontal lines, the graph of ${\displaystyle 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 ${\displaystyle f:X\to Y}$ and ${\displaystyle g:Y\to X}$. We say that ${\displaystyle g}$ is the inverse function of ${\displaystyle f}$ (denoted ${\displaystyle f^{-1}}$) if ${\displaystyle y=f(x)}$ if and only if ${\displaystyle g(y)=x}$ for all ${\displaystyle x\in X}$ and ${\displaystyle y\in Y}$.

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

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