MATH 409 Lecture 2

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

Lecture Slides

Challenge 2

Due Sept. 5

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

$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 $\prec$ on the set $\mathbb {R} (x)$ of rational functions in variable $x$ with real coefficients that makes $\mathbb {R} (x)$ into an ordered field.

Towards an Answer

Modification of big-Oh:

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

Define $f\prec g$ if and only if for some constant $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 $F$ with a strict linear order $\prec$ is called an ordered field if this order and arithmetic operation son $F$ satisfy the following axioms:

OA.	$a\prec b\implies a+c\prec b+c$
OM1.	$(a\prec b)\wedge (c\succ 0)\implies a\,c\prec b\,c$
OM2.	$(a\prec b)\wedge (c\prec 0)\implies b\,c\prec a\,c$
OM1 + OM2 = OM.	$(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

$OA\wedge OM1\wedge OM2\iff OA\wedge OM\,\!$

So we prove each conditional separately:

${\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.

---

$OA\wedge OM1\wedge OM2\implies OM$

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

---

$OA\wedge OM\implies OM1$

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

---

$OA\wedge OM\implies OM2$

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

quod erat demonstrandum

Strict linear order

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

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

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

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

Properties of Ordered Fields

Theorem. $a\succ 0\implies -a\prec 0$

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

quod erat demonstrandum

Theorem. $a\prec b\implies a-b\prec 0$

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

quod erat demonstrandum

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

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

quod erat demonstrandum

Theorem. $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. $a\succ 0\wedge b\prec 0\implies a\,b\prec 0$

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

quod erat demonstrandum

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

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

quod erat demonstrandum

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

Proof. (need linearity) Since $a\neq 0$, we have either $a\succ 0$ or $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. $-1\prec 0\prec 1$

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

quod erat demonstrandum

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

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

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

quod erat demonstrandum

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

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

quod erat demonstrandum

Which fields can be ordered?

• $\mathbb {R}$ is ordered with respect to $<$.
• $\mathbb {Q}$ is also ordered with respect to $<$ (since it is a subset of $\mathbb {R}$).
• $\mathbb {F} _{2}$ (field of two elements) cannot be ordered: in any ordered field, $-1\prec 0\prec 1$, in particular $-1\prec 1$. However, in the field of two elements, $-1=1$.
• $\mathbb {C}$ cannot be ordered: In any ordered field, $-1\prec 0$ and $a^{2}\succ 0$ for all $a\neq 0$. However, $i^{2}=-1$, where $i={\sqrt {-1}}\neq 0$
• The field $\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 $a$, denoted $|a|$ is denoted as follows:

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

This definition makes sense for any ordered field.

Properties

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

Supremum and Infimum

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

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

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

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

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

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

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