path: root/lacey/hw2.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
\long\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{\medskip\noindent{\it Proof.}\quad}
\def\endproof{\leavevmode\hskip\parfillskip\vrule height 6pt width 6pt
depth 0pt{\parfillskip0pt\medskip}}

\let\bu\bullet

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

\noindent{\bf Definition.} For any set $A,$ finite or infinite, define
the power set of $A$ to be the collection of all subsets of $A.$ That
is,
$${\cal P}(A) = \{A' : A'\subseteq A\}.$$

\noindent{\bf Definition.} A set $A\subseteq\bb R$ is dense if for all
$a\neq b\in\bb R,$ there is an element $c\in A$ between $a$ and $b.$

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

\tf
A decreasing nested sequence of bounded intervals has non empty
intersection.
\endtf

False.
This fails if they are bounded and open;
for example, $A_n = (0,{1\over n}].$

\tf
A decreasing nested sequence of closed intervals has non-empty
intersection.
\endtf

True.

\tf
For reals $a < b,$ we have $\sup Q\cap [a,b] = b.$
\endtf

True.

\tf
For reals $a < b,$ we have $\sup Q^c\cap [a,b] = b.$
\endtf

True.

\tf
The rationals are dense.
\endtf

True.

\tf
The subset of the rationals $\{p/2^r | p\in\bb Z,
r\in\{100,101,\ldots\}\}$ are dense.
\endtf

True. % i feel like i want to write a proof.

\tf
The subset of the rationals $\{p/2^r | p\in\bb Z,
r\in\{1,2,\ldots,100\}\}$ are dense.
\endtf

False. Between 0 and $1/2^{100},$ there is no number in this set.

\tf
The set $\{\pi r|r\in\bb Q\}$ is dense.
\endtf

True.

\question{Prove that there is a positive number $s$ such that $s^2 = 3.$
\item{$\bu$} This depends upon the Supremum Axiom of course, applied to
a good set $S.$
\item{$\bu$} Letting $\sigma = \sup S,$ there are two cases which need
to lead to a contradiction: $\sigma^2 < 3$ and $\sigma^2 > 3.$
\item{$\bu$} You could find it useful to note that $1.7^2<3,$ but only
just barely. (But it is not necessary, either)
}

\proof
Let $S = \{s\in\bb R|s^2 < 3\}.$

2 is an upper bound of $S.$

For the sake of contradiction, let $s\in S$ s.t. $s>2.$
Then, $s^2>4>3,$ contradicting our definition of $S.$

By the supremum axiom, this upper-bounded set must have a supremum
$\sigma = \sup S.$

If $\sigma^2 < 3,$
we must have $s>0\in\bb R$ such that $\sigma^2<s^2<3,$ (by density of
the reals) meaning $s\in S$ and $s>\sigma,$ so $\sigma$ is not the
supremum. % TODO: check if we can sorta assume continuity of s^2 like
% this (probably ask Lacey)

If $\sigma^2 > 3,$ choose $s>0$ such that $3 < s^2 < \sigma^2,$ and
let $\epsilon = \sigma-s > 0.$
From a property of the supremum, we must have $a\in S$ such that
$a>\sigma-\epsilon=s.$
We already know $s^2 > 3,$ so $a^2 > 3$, contradicting our construction.

We have thus determined $\sigma^2 = 3,$ proving there is such a positive
real number.
\endproof

\question{Show that these statements are equivalent: for a sequence of
reals $\{x_n\},$
\item{$(1)$} The sequence converges to $x$: for all $\epsilon > 0,$
there is a $N_\epsilon > 1$ so that for all $n > N_\epsilon,$
$|x_n-x|<\epsilon.$
\item{$(2)$} For all $\epsilon > 0,$ there is a $N_\epsilon > 1$ so that
for all $n>N_\epsilon,$ $|x_n-x|<100\epsilon.$
\item{$(3)$} For all $0<\epsilon<10^{-10}$ there is a $N_\epsilon > 1$
so that for all $n>N_\epsilon,$ $|x_n-x|<\epsilon.$
\item{$(4)$} For all $\epsilon > 0$ there is a $N_\epsilon > 10^{10}$ so
that for all $n>N_\epsilon,$ $|x_n-x|<\epsilon.$
}

\proof
We will prove these in a loop.

\smallskip
$(1)\Rightarrow(2)$
\smallskip

For all $\epsilon>0,$ there is a $N_\epsilon>1$ so that for all
$n>N_\epsilon,$ $|x_n-x|<\epsilon<100\epsilon,$ satisfying our
condition.

\smallskip
$(2)\Rightarrow(3)$
\smallskip

We will show for all $0<\epsilon<10^{-10},$ there is a $N_\epsilon>1$ so
that for all $n>N_\epsilon,$ $|x_n-x|<\epsilon.$

Select some $0<\epsilon/100<10^{-12}$ and $N_{\epsilon}$ satisfying
$(2)$.
Then, for all $n>N_\epsilon,$ $|x_n-x|<100(\epsilon/100)=\epsilon,$
satisfying $(3).$

\smallskip
$(3)\Rightarrow(4)$
\smallskip

Let $\epsilon>0.$
Account for where $\epsilon > 10^{-11},$ we take instead $N_\epsilon>1$
such that for all $n>N_\epsilon,$ $|x_n-x| < \min\{10^{-11},\epsilon\}
\leq \epsilon.$

If $N_\epsilon<10^{10},$ the result implies
$M_\epsilon>10^{10}>N_\epsilon$ such that for all
$n>M_\epsilon>N_\epsilon,$ $|x_n-x|<\epsilon.$

\smallskip
$(4)\Rightarrow(1)$
\smallskip

Let $\epsilon > 0.$ We have $N_\epsilon > 10^{10} > 1$ such that for all
$n>N_\epsilon,$ $|x_n-x|<\epsilon.$
This satisfies $(1).$

\endproof

\question{Let $A$ be a nonempty set of positive real numbers, that is
bounded above. Set $B = \{1/a : a\in A\}.$ Prove that $B$ is bounded
below, and that
$$\inf B = {1\over\sup A}.$$
}

\proof

All members of $A$ are positive, so $1/a>0$ for all $a\in A,$ giving a
lower bound for $B.$
By the supremum axiom, there is an infimum $b$ for $B.$

We know that for all $a\in A,$ $b\leq 1/a,$ and for all $\epsilon>0$ and
some respective $c\in A,$ that $1/c<b+\epsilon.$

$1/b\geq a,$ so we know $b\geq\sup A.$
Then, $$c > {1\over b+\epsilon} = {1\over b} + {\epsilon\over
b(b+\epsilon)},$$
of which the error can be reduced to tell us that ${1\over b} = \sup A.$

\endproof

\question{Let $A = \{a_n|n\in\bb N\}$ and $B = \{b_n|n\in\bb N\}$ be two
bounded sets in $\bb R.$ Show that
$$\inf_m a_m + \inf_n b_n \leq \inf_n(a_n + b_n).$$
$$\inf_m a_m + \inf_n b_n = \inf_{m,n} a_m + b_n.$$
}

\proof
We will show the equality first.
Let $a$ and $b$ refer to the infima of $A$ and $B$ respectively.
Let $\epsilon > 0.$
From our definition of infima, we have $m,n\in\bb N$ such that
$a_n < a + \epsilon$ and $b_m < b + \epsilon.$
Thus, $a_n+b_m < a+b+2\epsilon.$
And for all $o,p\in\bb N,$
we have $a \leq a_o$ and $b \leq b_p,$ so $a+b\leq a_o+b_p,$
meaning our infimum $c$ satisfies $a+b\leq c<a+b+2\epsilon,$ so $c =
a+b.$

The inequality is then trivially implied since $\{a_n+b_n:n\in\bb
N\}\subseteq \{a_n+b_m:n,m\in\bb N\},$ so the infimum of the former is
less than or equal to all elements of the latter, and thus forms a lower
bound less than or equal to the infimum of the latter.
\endproof

\question{This concerns the power set, defined above.
\item{$(1)$} What is the power set of the empty set, ${\cal
P}(\emptyset)?$
\item{$(2)$} Find a formula for the cardinality of ${\cal
P}(\{1,2,\ldots,n\})$ for $n=1,2,3,\ldots$ Prove the formula, using
mathematical induction.

\noindent Recall that the mathematical induction is a two step procedure,
requiring
\item{$(1)$} Establish the proposition in a base case, $n=1$ in this
case.
\item{$(2)$} Assuming the proposition true for integer $n\geq 1,$ show
that it is true for $n+1.$
}

\proof
${\cal P}(\emptyset) = \{\emptyset\}.$

This is the $n=0$ case of ${\cal P}(\{1,2,\ldots,n\}),$ and it has
cardinality $1 = 2^0.$

To show the inductive case, assume that $|{\cal P}(\{1,2,\ldots,n\})|=2^n.$

${\cal P}(\{1,2,\ldots,n,n+1\}) = {\cal P}(\{1,2,\ldots,n\})\cup\{x\cup\{n+1\} :
x\in{\cal P}(\{1,2,\ldots,n\})\},$
so its cardinality is $2^{n+1},$ showing the inductive case.

These sets are disjoint because none of the left ones and all of the
right ones have the element $n+1,$ and each have cardinality $2^n,$ and
this enumerates all subsets of $\{1,2,\ldots,n\}$ which are subsets of
$\{1,2,\ldots,n,n+1\},$ and the subsets which include $n+1.$

\endproof

\question{Find bijections for the following functions.
\item{$(2)$} Find a bijection between $(0,1)$ and $[0,1).$
\item{$(3)$} Find a bijection between $(0,1)$ and $(0,1)\cup\bb N.$
}

\tf (Hilbert Hotel) Find a bijection between $\bb Z$ and $\{1/2\}\cup\bb
Z.$
\endtf

Let $f: \bb Z\to\{1/2\}\cup\bb Z.$

For $z>1,$ $f(z) = z-1.$
For $z=0,$ $f(z) = 1/2.$
For $z<0,$ $f(z) = z.$

\tf Find a bijection between $(0,1)$ and $[0,1).$
\endtf
Let $f: [0,1)\to(0,1)$
where $f(0) = 1/2,$ and where $n\in\bb N^{\geq 2},$
$f(1/n)={1\over n+1},$ and $f(x) = x$ otherwise.

\tf Find a bijection between $(0,1)$ and $(0,1)\cup\bb N.$
\endtf
Let $f: (0,1)\cup\bb N\to(0,1).$

If $n\in\bb N,$ $f(n) = {1\over 2^{n+1}},$ and for $m,l\in\bb N,$
$f({1\over 2^m3^l}) = {1\over 2^m3^{l+1}},$ and $f(x) = x$ otherwise.

\bye