diff options
Diffstat (limited to 'lacey/hw2.tex')
-rw-r--r-- | lacey/hw2.tex | 294 |
1 files changed, 294 insertions, 0 deletions
diff --git a/lacey/hw2.tex b/lacey/hw2.tex new file mode 100644 index 0000000..c553b8c --- /dev/null +++ b/lacey/hw2.tex @@ -0,0 +1,294 @@ +\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 |