# MATH 409 Lecture 2

« previous | Thursday, August 29, 2013 | next »

Lecture Slides

## Challenge 2

Due Sept. 5

Construct a strict linear order ${\displaystyle \prec }$ on the set ${\displaystyle \mathbb {C} }$ of complex numbers that satisfies the axiom OA:

${\displaystyle a\prec b\rightarrow a+c\prec b+c\quad \forall a,b,c\in \mathbb {C} \,\!}$

## Challenge 3

Due Sept. 5

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

Modification of big-Oh:

Let ${\displaystyle f,g\in \mathbb {R} (x)}$ be rational functions in ${\displaystyle x}$ with real coefficients.

Define ${\displaystyle f\prec g}$ if and only if for some constant ${\displaystyle c}$

Asymptotics do not provide an answer, but are a step in the right direction.

## Ordered Fields

Absolute value Supremum and infimum

Recall: Real Line structure formalized by field and ordering formalized by strict linear ordering

### Definition

A field ${\displaystyle F}$ with a strict linear order ${\displaystyle \prec }$ is called an ordered field if this order and arithmetic operation son ${\displaystyle F}$ satisfy the following axioms:

OA. ${\displaystyle a\prec b\implies a+c\prec b+c}$ ${\displaystyle (a\prec b)\wedge (c\succ 0)\implies a\,c\prec b\,c}$ ${\displaystyle (a\prec b)\wedge (c\prec 0)\implies b\,c\prec a\,c}$ ${\displaystyle (0\prec a)\wedge (0\prec b)\implies 0\prec a\,b}$

Theorem. Three axioms OA, OM1, and OM2 are equivalent to two axioms OA and OM

Proof. We wish to prove that

${\displaystyle OA\wedge OM1\wedge OM2\iff OA\wedge OM\,\!}$

So we prove each conditional separately:

{\displaystyle {\begin{aligned}OA\wedge OM1\wedge OM2&\implies OA\wedge OM\\OA\wedge OM&\implies OA\wedge OM1\wedge OM2\end{aligned}}}

OA is on both sides of the implications, so we can disregard it from the RHS and prove the remaining RHS elements incrementally.

${\displaystyle OA\wedge OM1\wedge OM2\implies OM}$

Assume that ${\displaystyle 0\prec a}$ and ${\displaystyle 0\prec b}$. Axiom OM1 implies that ${\displaystyle 0\cdot b\prec a\,b}$. We already know ${\displaystyle 0\cdot b=0}$, thus ${\displaystyle 0\prec a\,b}$.

${\displaystyle OA\wedge OM\implies OM1}$

Assume that ${\displaystyle a\prec b}$ and ${\displaystyle c\succ 0}$. By axiom OA, ${\displaystyle a\prec b}$ implies ${\displaystyle a+(-a)\prec b+(-a)}$, that is ${\displaystyle 0\prec b-a}$. By axiom OM, ${\displaystyle 0\prec (b-a)\,c=bc-ac}$. Adding ${\displaystyle a\,c}$ to both sides of the latter relation, we get ${\displaystyle a\,c\prec b\,c}$.

${\displaystyle OA\wedge OM\implies OM2}$

Assume that ${\displaystyle a\prec b}$ and ${\displaystyle c\prec 0}$. By axiom OA, ${\displaystyle a\prec b}$ implies ${\displaystyle 0\prec b-a}$ while ${\displaystyle c\prec 0}$ implies ${\displaystyle 0\prec -c}$. By axiom OM, we get ${\displaystyle 0\prec (b-a)(-c)=a\,c-b\,c}$. Adding ${\displaystyle b\,c}$ to both sides of the latter relation, we get ${\displaystyle a\,c\prec b\,c}$.

quod erat demonstrandum

### Strict linear order

a strict order on a set ${\displaystyle X}$ is a relation on ${\displaystyle X}$ (usually denoted ${\displaystyle \prec }$ or preceeds), that is antisymmetric and transitive, namely:

• ${\displaystyle a\prec b\implies \neg (b\prec a)}$
• ${\displaystyle a\prec b\wedge b\prec c\implies a\prec c}$

Strict order ${\displaystyle \prec }$ is called linear (or total) if for any ${\displaystyle a,b\in X}$ we have either ${\displaystyle a\prec b}$ or ${\displaystyle b\prec a}$ or ${\displaystyle a=b}$

Auxiliary Notation: ${\displaystyle a\succ b}$ means that ${\displaystyle b\prec a}$.

### Properties of Ordered Fields

Theorem. ${\displaystyle a\succ 0\implies -a\prec 0}$

Proof. subtract ${\displaystyle a}$ from both sides of the relation ${\displaystyle a\succ 0}$, we get ${\displaystyle 0\succ -a}$.

quod erat demonstrandum

Theorem. ${\displaystyle a\prec b\implies a-b\prec 0}$

Proof. subtract ${\displaystyle b}$ from both sides of the relation ${\displaystyle a\prec b}$, we get ${\displaystyle a-b\prec b-b=0}$.

quod erat demonstrandum

Theorem. ${\displaystyle a\prec b\wedge c\prec d\implies a+c\prec b+d}$

Proof. Adding ${\displaystyle c}$ to both sides of ${\displaystyle a\prec b}$, we get ${\displaystyle a+c\prec b+c}$. Adding ${\displaystyle b}$ to both sides of ${\displaystyle c\prec d}$, we get ${\displaystyle b+d\prec b+d}$. By transitivity, ${\displaystyle a+c\prec b+c\prec b+d}$ implies ${\displaystyle a+c\prec b+d}$.

quod erat demonstrandum

Theorem. ${\displaystyle 0\prec a\prec b\wedge 0\prec c\prec d\implies a\,c\prec b\,d}$

Proof. similar proof as above.

quod erat demonstrandum

Theorem. ${\displaystyle a\succ 0\wedge b\prec 0\implies a\,b\prec 0}$

Proof. ${\displaystyle b\prec 0}$ implies ${\displaystyle -b\succ 0}$. Then ${\displaystyle a\,(-b)\succ 0}$. Note that ${\displaystyle a\,(-b)=a(-1\cdot b)=(-1)(a\,b)=-a\,b}$. Hence ${\displaystyle -a,\,b\succ 0}$ so that ${\displaystyle a\,b\prec 0}$

quod erat demonstrandum

Theorem. ${\displaystyle a\prec 0\wedge b\prec 0\implies a\,b\succ 0}$

Proof. It follows that ${\displaystyle -a\succ 0}$ and ${\displaystyle -b\succ 0}$. Then ${\displaystyle (-a)(-b)\succ 0}$. But ${\displaystyle (-a)(-b)=(-1\cdot a)(-1\cdot b)=(-1)(-1)a\,b=1a\,b=a\,b}$.

quod erat demonstrandum

Theorem. ${\displaystyle a\neq 0\implies a^{2}\succ 0}$ where ${\displaystyle a^{2}=a\cdot a}$

Proof. (need linearity) Since ${\displaystyle a\neq 0}$, we have either ${\displaystyle a\succ 0}$ or ${\displaystyle a\prec 0}$:

1. In the first case, positive times positive is positive by OM.
2. In the second case, negative times negative is negative by the previous property.
quod erat demonstrandum

Theorem. ${\displaystyle -1\prec 0\prec 1}$

Proof. We know that ${\displaystyle 1\neq 0}$ by field axioms and ${\displaystyle a^{2}\succ 0}$ for any ${\displaystyle a\neq 0}$. We obtain ${\displaystyle 0\prec 1^{2}=1}$. Then ${\displaystyle -1\prec 0}$.

quod erat demonstrandum

Theorem. ${\displaystyle 0\prec a\implies 0\prec a^{-1}}$

Proof. We know either ${\displaystyle 0\prec a^{-1}}$ or ${\displaystyle a^{-1}\prec 0}$ or ${\displaystyle a^{-1}=0}$. However, ${\displaystyle a^{-1}\prec 0}$ would imply that ${\displaystyle 1=a\,a^{-1}\prec 0}$, a contradiction.

Further, ${\displaystyle a^{-1}=0}$ would imply that ${\displaystyle 1=a\,a^{-1}=a\cdot 0=0}$, another contradiction. Hence ${\displaystyle 0\prec a^{-1}}$.

quod erat demonstrandum

Theorem. ${\displaystyle 0\prec a\prec b\implies a^{-1}\succ b^{-1}}$

Proof. Since ${\displaystyle 0\prec a}$ and ${\displaystyle 0\prec b}$, it follows that ${\displaystyle 0\prec a^{-1}}$ and ${\displaystyle 0\prec b^{-1}}$. Multiplying both sides of ${\displaystyle a\prec b}$ by ${\displaystyle a^{-1}\,b^{-1}}$, we get ${\displaystyle b^{-1}\prec a^{-1}}$.

quod erat demonstrandum

### Which fields can be ordered?

• ${\displaystyle \mathbb {R} }$ is ordered with respect to ${\displaystyle <}$.
• ${\displaystyle \mathbb {Q} }$ is also ordered with respect to ${\displaystyle <}$ (since it is a subset of ${\displaystyle \mathbb {R} }$).
• ${\displaystyle \mathbb {F} _{2}}$ (field of two elements) cannot be ordered: in any ordered field, ${\displaystyle -1\prec 0\prec 1}$, in particular ${\displaystyle -1\prec 1}$. However, in the field of two elements, ${\displaystyle -1=1}$.
• ${\displaystyle \mathbb {C} }$ cannot be ordered: In any ordered field, ${\displaystyle -1\prec 0}$ and ${\displaystyle a^{2}\succ 0}$ for all ${\displaystyle a\neq 0}$. However, ${\displaystyle i^{2}=-1}$, where ${\displaystyle i={\sqrt {-1}}\neq 0}$
• The field ${\displaystyle \mathbb {R} (x)}$ of rational functions is an ordered field with respect to some relation

## Absolute Value

(in preparation for next time)

The absolute value (or modulus) of a real number ${\displaystyle a}$, denoted ${\displaystyle |a|}$ is denoted as follows:

${\displaystyle |a|={\begin{cases}a&a\geq 0\\-a&a<0\end{cases}}\,\!}$

This definition makes sense for any ordered field.

### Properties

• ${\displaystyle |a|\geq 0}$: if ${\displaystyle a\geq 0}$, we're done by the definition. If ${\displaystyle a<0}$, we know that ${\displaystyle -a>0}$
• ${\displaystyle |a|=0}$ iff ${\displaystyle a=0}$
• ${\displaystyle |-a|=|a|}$
• if ${\displaystyle M>0}$, then ${\displaystyle |a|
• ${\displaystyle |a\,b|=|a|\cdot |b|}$
• ${\displaystyle |a+b|\leq |a|+|b|}$

## Supremum and Infimum

Let ${\displaystyle E\subset \mathbb {R} }$ be a nonempty set and ${\displaystyle M}$ be a real number. We say that ${\displaystyle M}$ is an upper bound of the set ${\displaystyle E}$ if ${\displaystyle a\leq M}$ for all ${\displaystyle a\in E}$. Similarly, ${\displaystyle M}$ is a lower bound of the set ${\displaystyle E}$ if ${\displaystyle a\geq M}$ for all ${\displaystyle a\in E}$.

We say the set ${\displaystyle E}$ is bounded above if it admits an upper bound and bounded below if it admits a lower bound. The set ${\displaystyle E}$ is called bounded if it is bounded above and below

In particular, a real number ${\displaystyle M}$ is called the supremum (or the least upper bound) of hte set ${\displaystyle E}$ and denoted ${\displaystyle \sup {E}}$ if

1. ${\displaystyle M}$ is an upper bound of ${\displaystyle E}$, and
2. ${\displaystyle M\leq M_{+}}$ for any upper bound ${\displaystyle M_{+}}$ of ${\displaystyle E}$.

Similarly, ${\displaystyle M}$ is called the infimum (or greatest lower bound) of the set ${\displaystyle E}$ and denoted ${\displaystyle \inf {E}}$ if

1. ${\displaystyle M}$ is a lower bound of ${\displaystyle E}$, and
2. ${\displaystyle M\geq M_{-}}$ for any lower bound ${\displaystyle M_{-}}$ of ${\displaystyle E}$.

Completeness Axiom. A nonempty subset ${\displaystyle E\subset \mathbb {R} }$ has a supremum if ${\displaystyle E}$ is bounded above.