path: root/lacey/hw1.tex

\font\bigbf=cmbx12 at 24pt
\newfam\bbold
\font\bbten=msbm10
\font\bbsev=msbm7
\font\bbfiv=msbm5
\textfont\bbold=\bbten
\scriptfont\bbold=\bbsev
\scriptscriptfont\bbold=\bbfiv
\def\bb#1{{\fam\bbold #1}}

\newcount\pno
\def\tf{\advance\pno by 1\smallskip\bgroup\item{(\number\pno)}}
\def\endtf{\egroup\medskip}

\newcount\qno
\def\question#1{\ifnum\qno=0\else\vfil\eject\fi\bigskip\pno=0\advance\qno by 1\noindent{\bf Question \number\qno.} {\it #1}}

\def\proof{{\it Proof.}\quad}
\def\endproof{\leavevmode\hskip\parfillskip\vrule height 6pt width 6pt
depth 0pt{\parfillskip0pt\medskip}}

{\bigbf\centerline{Holden Rohrer}\bigskip\centerline{MATH 4317\qquad HOMEWORK \#1}}

\question{For each item, if it is a true statement, say so.
Otherwise, give a counterexample.}

\tf For sets $A_1,A_2,\ldots,A_n,$
$\left(\bigcup_{k=1}^n A_k\right)^c = \bigcap_{k=1}^n A_k.$
\endtf

False.
With $U = \{1\},$ and $A_1 = \emptyset,$ (where $n=1$),
the union is $\emptyset,$ so the complement is $\{1\},$ which is not
equal to the intersection $\emptyset.$

\tf For sets $A_1,A_2,\ldots,A_n,$
$\left(\bigcup_{k=1}^\infty A_k\right)^c = \bigcap_{k=1}^\infty A_k^c.$
\endtf

True.

\tf An infinite sequence of decreasing closed intervals $I_1\supset I_2
\supset I_3 \supset \cdots$ has a non-empty intersection.
\endtf

True, when defined on the reals.

\tf Every convergent sequence of rationals has a rational limit.
\endtf

False. Let $a_n = 1 + {1\over a_{n-1}}$ with $a_0 = 1.$
This is a rational expression but converges to the irrational $\phi.$

Also see the Babylonian method.

\tf A finite set can contain its supremum, but not its infimum.
\endtf

False. The set $\{0\}$ has lower bound $m=0.$
This is an infimum because all other lower bounds $w\leq 0=m$ by
definition.
This is in the set.

\tf An unbounded set does not have a supremum.
\endtf

False. A set can be unbounded because it lacks a lower bound like
$\{-2^n : n\in\bb N\},$ but this set has supremum $-1.$o

\tf Two real numbers $a$ and $b$ satisfy $a < b$ if for all $\epsilon >
0,$ $a \leq b + \epsilon.$
\endtf

{\let\to\Rightarrow
False. Let $a = b.$\par $0 < \epsilon \to 0\leq\epsilon\to a\leq a
+\epsilon\to a \leq b + \epsilon.$
}

\tf Let $f: X\to Y$ be a function, and $A,$ $B$ be sets in the codomain
$Y.$ Then, $f^{-1}(A\cap B) = f^{-1}(A)\cap f^{-1}(B).$
\endtf

\proof
Let $A,B\in Y.$
Let $s\in f^{-1}(A)\cap f^{-1}(B).$
$f(s) \in A$ and $f(s)\in B,$ so $f(s) in A\cap B,$ and $s\in
f^{-1}(A\cap B).$

Now, to show the other direction, let $t\in f^{-1}(A\cap B).$
Then, $f(t) \in A\cap B,$ so $f(t) \in A$ and $f(t)\in B,$ so $t\in
f^{-1}(A),$ and $t\in f^{-1}(B),$ and $t\in f^{-1}(A)\cap f^{-1}(B).$

We have shown these two sets are equal.
\endproof

\tf Let $f: X\to Y$ be a function, and $A,$ $B$ be sets in the codomain
$Y.$ Then, $f^{-1}(A\cup B) = f^{-1}(A)\cup f^{-1}(B).$
\endtf

\proof
Let $s\in f^{-1}(A\cup B).$ Then, $f(s)\in A\cup B.$
WLOG, let $f(s)\in A,$ so $s\in f^{-1}(A)\cup f^{-1}(B).$

The other direction is $s\in f^{-1}(A)\cup f^{-1}(B),$ and WLOG, $s\in
f^{-1}(A).$
Then, $f(s)\in A,$ so $f(s)\in A\cup B,$ and $s\in f^{-1}(A\cup B).$

We have shown these two sets are equal.
\endproof

\question{(Exercise 1.2.8) Here are two important definitions related to
a function $f: A\to B.$ The function $f$ is one-to-one (1-1, injective)
if $a_1\neq a_2$ in $A$ implies that $f(a_1)\neq f(a_2)$ in $B.$ The
function $f$ is onto (surjective) if, given any $b\in B,$ it is possible
to find an element $a\in A$ for which $f(a) = b.$ Give an example of
each, or state that the request is impossible.}

I have assumed $0\in\bb N.$

\tf
$f: \bb N\to\bb N$ that is one-to-one but not onto.
\endtf

$f(x) = 2x.$

\tf
$f: \bb N\to\bb N$ that is not one-to-one but is onto.
\endtf

$f(x) = \left\lfloor {x\over 2}\right\rfloor.$

\tf
$f: \bb N\to\bb Z$ that is one-to-one and onto.
\endtf

$f(x) = \left\lfloor {x+1\over 2}\right\rfloor (-1)^x.$

\question{(Exercise 1.2.10) Decide which of the following are true
statements. Provide a short justification for those that are valid and a
counterexample for those that are not:}

\tf Two real numbers satisfy $a<b$ if and only if $a < b+\epsilon$ for
every $\epsilon>0.$
\endtf

False. Where $a=b,$ $\epsilon>0$ implies $a < b+\epsilon.$

\tf Two real numbers satisfy $a < b$ if $a<b+\epsilon$ for every
$\epsilon > 0.$
\endtf

False. Where $a=b,$ $\epsilon>0$ implies $a < b+\epsilon.$

\tf Two real numbers satisfy $a\leq b$ if and only if $a<b+\epsilon$ for
every $\epsilon>0.$
\endtf

\proof

$(\Rightarrow)$

Let $a\leq b.$ If $\epsilon > 0,$ then $a < b + \epsilon.$

$(\Leftarrow)$

We will show the contrapositive.
Let $a > b.$ If $\epsilon > 0,$ then $a > b + \epsilon,$ or $a \geq b +
\epsilon.$

\endproof

\question{(Exercise 1.3.2) Give an example of each of the following, or
state that the request is impossible.}

\tf
A set $B$ with $\inf B\geq\sup B.$
\endtf

Let $B = \{0\}.$ $\inf B = \sup B = 0,$ so $\inf B\geq\sup B.$

\tf
A finite set that contains its infimum but not its supremum.
\endtf

This is impossible.
All finite nonempty sets include their infimum and their supremum.

\tf
A bounded subset of $\bb Q$ that contains its supremum but not its
infimum.
\endtf

$A = \{2^{-n} : n\in\bb N\}$ is bounded (for all $a\in A,$ $|a|\leq 1$)
and it contains its supremum $1$ but not its infimum $0.$

\question{(1.3.7) Prove that if $a$ is an upper bound for $A,$ and if
$a$ is also an element of $A,$ then it must be that $a=\sup A.$}

\proof
Let $a$ be an upper bound for $A.$ That is, for all $b\in A,$ $a\geq b.$
Also let $a\in A.$
Therefore all upper bounds $m$ must satisfy $m\geq a.$

These are the conditions of supremum, so $a$ is a supremum.
\endproof

\question{(1.3.6) Given sets $A$ and $B,$ define $A+B = \{a+b:a\in
A,b\in B\}.$ Follow these steps to prove that if $A$ and $B$ are
nonempty and bounded above then $\sup(A+B)=\sup A + \sup B.$}

\tf
Let $s = \sup A$ and $t = \sup B.$ Show $s+t$ is an upper bound for
$A+B.$
\endtf
\proof
Let $a+b\in A+B.$ From the construction of $A+B,$ $a\in A$ and $b\in B.$

From definition of supremum, $a\leq s$ and $b\leq t.$ Therefore,
$a+b\leq s+t,$ giving $s+t$ is an upper bound for all elements of $A+B.$
\endproof

\tf
Now let $u$ be an arbitrary upper bound for $A+B,$ and temporarily fix
$a\in A.$ Show $t\leq u-a.$
\endtf
\proof
Let $a+b\in A+B$ with fixed $a\in A.$

If $u$ is an upper bound for $A+B,$ then $a+b \leq u.$

As $t$ is the least upper bound of $B,$ for all $\epsilon > 0,$ we have
for some $b\in B,$ that $t-\epsilon < b.$
Thus, $a+t-\epsilon < a+b \leq u.$
$\epsilon$ may be reduced, and we obtain $a+t \leq u$ or $t\leq u-a.$
\endproof

\tf
Finally, show $\sup(A+B) = s+t.$
\endtf
\proof

Let $\epsilon > 0.$
From definition of supremum, for some $a\in A,$ we have
$s-\epsilon < a.$
From the last proof, $s-\epsilon+t < a+t \leq u.$
Since $s+t-\epsilon < u$ for all $\epsilon > 0,$ $s+t\leq u.$

\endproof

\tf
Construct another proof of this same fact using Lemma 1.3.8.
\endtf
\proof
Let $\epsilon > 0.$

From lemma 1.3.8, there exists $a\in A$ and $b\in B$ such that
$s-\epsilon/2 < a$ and $t-\epsilon/2 < b.$
Since we know $s+t$ is an upper bound for $A+B,$
and we may now show $s+t-\epsilon < a+b$ for all $a+b\in A+B.$
The lemma tells us this makes $s+t$ a supremum for $A+B.$
\endproof

\question{(1.3.10, Cut Property) The Cut Property of the real numbers is
the following. If $A$ and $B$ are nonempty, disjoint sets with $A\cup
B=\bb R$ and $a<b$ for all $a\in A$ and $b\in B,$ then there exists $c\in\bb
R$ such that $x\leq c$ whenever $x\in A$ and $y\geq c$ whenever $y\in
B.$}

\tf
Use the Axiom of Completeness to prove the Cut Property.
\endtf
\proof
Let $A$ and $B$ be sets satisfying the properties above.
We will find $s$ such that for all $a\in A,$ and for all $b\in B,$
$a\leq s\leq b.$

All $b\in B$ are upper bounds for $A,$ so the axiom of completeness
tells us $A$ has a least upper bound we'll call $s = \sup A.$
Since $A\cup B\in\bb R$ and $s\in\bb R,$ but $A\cap B = \emptyset$ (by
disjointedness), either $s\in A$ or $s\in B.$

WLOG, let $s\in A$ (we might just as easily have defined $s$ as the
greatest lower bound of $B$).
By construction, $s$ is an upper bound for $A,$ so for all $a\in A,$ $a
\leq s,$ and since $s\in A,$ from our definition of $B,$ for all $b\in B,$
$s < b,$ giving us our cut.
\endproof

\tf
Show that the implication goes the other way; that is, assume $\bb R$
possesses the Cut Property and let $E$ be a nonempty set that is bounded
above. Prove $\sup E$ exists.
\endtf
\proof
Let $A = \bigcup_{e\in E} \{x\in\bb R: x \leq e\}.$
Let $B$ be the complement of $A.$
This creates a disjoint set with $A\cup B = \bb R.$

$E$ is bounded above, so we have $b$ such that for all $e\in E,$ $e <
b.$
This makes $B$ nonempty, and $A$ is trivially nonempty if $E$ is
nonempty.

We also have that all $b\in B$ and $a\in a$ satisfy $b>a$ because all
$b\in B$ satisfy $b>e$ for a some $e\in E,$ but $a \leq e$ in that same
case.
The cut property gives us $c$ between $A$ and $B$ such that $a\leq c\leq
b,$ and since $B$ contains all possible upper bounds for $A,$ this is a
least upper bound.

\endproof

\tf
The punchline of parts $(1)$ and $(2)$ is that the Cut Property could be
used in place of the Axiom of Completeness as the fundamental axiom that
distinguishes th ereal numbers from the rational numbers. To drive this
point home, give a concrete example showing that the Cut Property is not
a valid statement when $\bb R$ is replaced by $\bb Q.$
\endtf
\proof
Let $A = \{x\in\bb Q : x<\sqrt 2\}$ and $B = \{x\in\bb Q : \sqrt 2\leq
x\}.$
$A\cup B = \bb Q,$ and $A\cap B = \emptyset,$ and for all $a\in A$ and
$b\in B,$ $a<\sqrt 2\leq b,$ so this satisfies all of the conditions.

However, the only number which is between $A$ and $B$ is $\sqrt 2,$
and any nearby rational $r$ satisfies either $r>\sqrt 2$ (putting it in
$B$), or $r<\sqrt 2$ (putting it in $A$), telling us $\bb Q$ doesn't
hold the cut property.
\endproof

\question{(1.3.11) Decide if the following statements about suprema and
infima are true or false. Give a short proof for those that are true.
For any that are false, supply an example where the claim in question
does not appear to hold.}

\tf
If $A$ and $B$ are nonempty, bounded, and satisfy $A\subset B,$ then
$\sup A\leq\sup B.$
\endtf
\proof
For all $a\in A,$ $a\in B,$ so by definition of supremum, $a\leq\sup B.$
Therefore, $\sup B$ is an upper bound for $A,$ and $\sup A < \sup B,$
again by definition of the supremum.
\endproof

\tf
If $\sup A<\inf B$ for sets $A$ and $B,$ then there exists a $c\in\bb R$
satisfying $a<c<b$ for all $a\in A$ and $b\in B.$
\endtf
\proof
Let $\sup A<\inf B.$ Let $a\in A$ and $b\in B.$ Let $c = {\sup A + \inf
B\over 2}.$

From definitions of supremum and infimum, $a \leq \sup A < c < \inf B \leq
b,$ so $a < c < b.$
\endproof

\tf
If there exists $c\in\bb R$ satisfying $a<c<b$ for all $a\in A$ and
$b\in B,$ then $\sup A < \inf B.$
\endtf

False. Let $B = \{2^{-n} : n\in\bb N\}$ and $A = \{-b : b\in B\}.$

For all $a\in A$ and $b\in B,$ $a < 0 < b,$ but $\sup A = \inf B = 0.$

\bye