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 {C}$ such that $a\prec b$ implies $a+c\prec b+c$ for all $a,b,c\in \mathbb {C}$

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

Given rational functions $f,g\in \mathbb {R} (x)$, we let $f\prec g$ if there exists $M\in \mathbb {R}$ 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\neq 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 {R}$ such that $p$ and $q$ have no roots in the interval $(M,\infty )$. $h$ is continuous and nowhere zero on $(M,\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)=\left\{c\in X~\mid ~a\prec c\prec b\right\}$, 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,\infty )=\left\{c\in X~\mid ~a\prec c\right\}$
  • $(-\infty ,a)=\left\{c\in X~\mid ~c\prec a\right\}$, where $a\in X$.
• Closed semi-infinite intervals
  • $[a,\infty )=(a,\infty )\cup \{a\}$
  • $(-\infty ,a]=(-\infty ,a)\cup \{a\}$
• Complete infinite interval $(-\infty ,\infty )$

Intervals of the Real Line

Theorem 1. Suppose $E$ is a bounded interval of $\mathbb {R}$ that consists of more than one point. Then there exist $a,b\in \mathbb {R}$ 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 {R}$ bounded above but unbounded below. Then $\exists a\in \mathbb {R}$ such that $E=(-\infty ,a)$ or $(-\infty ,a]$.

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

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

Note: Next challenge: Prove theorems 1 and 4

Natural Numbers, Integers, and Rationals

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

Note: The set $\mathbb {N}$ is well defined. Namely, it is the intersection of all inductive subsets of Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathbb{R}} .

Integers are defined as

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathbb{Z} = -\mathbb{N} \cup \left\{ 0 \right\} \cup \mathbb{N} \,\!}

Rationals are defined as

$\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 $[1,\infty )$ is an inductive set. Hence $\mathbb {N} \subset [1,\infty )$.

• If $n\in \mathbb {N}$, then $n-1\in \mathbb {N} \cup \{0\}$: Let $E$ be set of all $n\in \mathbb {N}$ such that $n-1\in \mathbb {N} \cup \{0\}$. Then $1\in E$ as Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 1-1=0} . Besides, for any Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n \in E} we have $(n+1)-1=n\in \mathbb {N}$ so that $n+1\in E$. Therefore $E$ is an inductive set. Then $\mathbb {N} \subset E$, which implies that $E=\mathbb {N}$.

more appropriately, that should be a ⊆

• If $n\in \mathbb {N}$, then the open interval $(n-1,n)$ contains no natural numbers: Let $E$ be the set of all $n\in \mathbb {N}$ such that Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle (n-1,n) \cap \mathbb{N} = \emptyset} . Then Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 1 \in E} as $\mathbb {N} \subset [1,\infty )$. Now assume Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n \in E} and take any $x\in (n,n+1)$. We have $x-1\neq 0$ since $x>n\geq 1$, and $x-1\not \in \mathbb {N}$ since $x-1\in (n-1,n)$. By the above, $x\not \in \mathbb {N}$. Thus $E$ is an inductive set, which implies $E=\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 Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \prec} if any nonempty subset of $Y$ has a least element.

Theorem. The set $\mathbb {N}$ is well-ordered with respect to the natural ordering of the real line Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathbb{R}} .

Proof. Let Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle E} be an arbitrary nonempty subset of $\mathbb {N}$. The set $E$ is bounded below since 1 is a lower bound of $\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\leq n<m+1$. As shown before, the interval Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle (n-1,n)} is disjoint from $\mathbb {N}$. Then $(-\infty ,n)=(-\infty ,m)\cup (n-1,n)$ is disjoint from $E$, which implies that $n$ is a lower bound of Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle E} . Hence Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n \le \inf E = m} , so Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 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 {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 {N} \subset E$ which implies that $E=\mathbb {N}$.

quod erat demonstrandum

Note: The assertion $P(1)$ is called the basis of induction. The implication $P(k)\implies 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 {Z}$

We can use mathematical induction for $n\in \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 {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 {N}$ we define a new assertion $Q(n)$ "$P(k)$ holds for any natural $k\leq n$". Then $Q(1)$ is equivalent to $P(1)$, in particular, it holds. By assumption Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle Q(n)} implies Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle P(n+1)} for any $n\in \mathbb {N}$. Moreover, $Q(n+1)$ holds if and only if both $Q(n)$ and Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle P(n+1)} hold. Therefore $Q(n)$ implies $Q(n+1)$ for all $n\in \mathbb {N}$. By the principle of mathematical induction, $Q(n)$ holds for all $n\in \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 Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f : X \to Y} is defined as the subset of Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 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 Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x \in X} such that $f(x)=y$.

The function Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f} is injective (or one-to-one) if Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f(x') = f(x)} implies $x=x'$. This can be tested with a horizontal line on graph: for all horizontal lines, the graph of Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\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 $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$.