aboutsummaryrefslogtreecommitdiff
path: root/lacey/hw2.tex
diff options
context:
space:
mode:
Diffstat (limited to 'lacey/hw2.tex')
-rw-r--r--lacey/hw2.tex294
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