1 files changed, 368 insertions, 0 deletions
diff --git a/lacey/hw1.tex b/lacey/hw1.tex
new file mode 100644
index 0000000..338a531
--- /dev/null
+++ b/lacey/hw1.tex
@@ -0,0 +1,368 @@
+\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