Homework Assignments
Homework will be due once per week. This page will be updated every time a new problem set is posted. Solutions for each problem set will be posted on this page after the assignment is due.
The overall guiding principle in your writing is to remember that your work is meant to be read by a skeptical peer; your job is to write a (logically) convincing argument to this audience. Your answers should always be written in narrative form; you should of course include relevant computations and equations, but these should be situated in the framework of some overall narrative that explains your reasoning, and they should always be naturally integrated into the structure of your writing. You should follow standard rules of composition: write in complete sentences, include appropriate punctuation, group sentences with a common theme into a paragraph, provide appropriate narrative transition when your reasoning takes a significant turn, etc. When writing formal proofs, you should not use abbreviations like $\forall$, $\exists$, $\Rightarrow$. (The notable exception being if you're writing is explicitly discussing a particular logical connective like $\wedge$ or $\Rightarrow$.) It is acceptable to use the notation $\in$ when describing elements in a formal proof (e.g., "Since $2 \in \mathbb{Z}$, we see that ..."). As a general rule, a mathematical symbol should never start a sentence or follow punctuation; the exception is that you can write a mathematical symbol after a colon which is announcing the beginning of a list of mathematical objects. Of course your work should be legible and neat.
If you collaborate with anyone on this problem set, include this information at the top of your submission (write something like ``I collaborated with..."). Problems marked "($\star$)" should be completed by yourself, or with assistance from the instructor.
Though you are welcomed to collaborate with the instructor, Math cafe tutors, or your classmates on problems, you are not permitted to reference outside sources or people when completing homework problems. For example, it is a violation of the Honor Code to use any of the following resources to find a solution to a problem: using a search engine to mine the internet for a solution, visiting an online mathematics discussion group, or collaborating with students not registered for this course.
The two parts of this assignment will be submitted in via separate Google forms that show up with each assignment. You work for Part A should be collected into one PDF, and your work for Part B should be collected in another PDF. Please be sure you've written your solutions in a way that allow you to submit your solutions for Part A separate from your solutions for Part B!
assignments
Upload your solutions here.
- Read the course syllabus in its entirety. If you have questions, ask the instructor.
- Read the course FAQ in its entirety. If you have questions, ask the instructor.
Part A
- Prove one of the distributive laws for $\vee$ and $\wedge$ for logical statements: if $P$, $Q$ and $R$ are statements, then
- $(P \vee (Q \wedge R)) \Leftrightarrow \left((P\vee Q) \wedge (P \vee R)\right)$
- $(P \wedge (Q \vee R)) \Leftrightarrow \left((P\wedge Q) \vee (P \wedge R)\right)$
[N.B.: The statement of this problem is a slightly less formal rendering of the more precise mathematical content you're asked to prove. For example, if you choose to prove the first option, you're really showing the following: for all statements $P,Q,$ and $R$, the statement $(P \vee (Q \wedge R)) \Leftrightarrow \left((P\vee Q) \wedge (P \vee R)\right)$ is true. The same is true for other problems on this assignment.]
- Prove one of the Demorgan's laws for logical statements: if $P$, $Q$ and $R$ are statements, then
- $\neg (P \vee Q) \Leftrightarrow \left(\neg P \wedge \neg Q\right)$
- $\neg (P \wedge Q) \Leftrightarrow \left(\neg P \vee \neg Q\right)$
- Suppose that $P$,$Q$ and $R$ are statements. Prove that the statement "$P \Rightarrow (Q \vee R)$" is equivalent to the statement "$(P \wedge \neg Q) \Rightarrow R$".
[NB: we'll frequently encounter results formulated as in the first statement. They sound like "Suppose BLAH. Prove THIS or THAT." This homework problem shows us that we can start our proofs of by saying "Suppose that BLAH and NOT THIS are true. We will prove THAT is true."]
Part B
- Is the $\wedge$ connective associative? That is, if $P$, $Q$ and $R$ are statements, are $(P \wedge Q) \wedge R$ and $P \wedge (Q \wedge R)$ logically equivalent? (Whatever your assertion, you should --- of course --- support it with a rigorous proof.)
[NB: you won't be asked to prove it here, but moving forward you can use the fact that the $\vee$ and $\Leftrightarrow$ connectives are associative. It turns out that $\Rightarrow$ is not associative!]
- ($\star$) Though the connectives $\Rightarrow$ and $\Leftrightarrow$ are extremely useful, it turns out that they are redundant: both can be expressed in terms of $\vee, \wedge$ and $\neg$.
- Prove that if $P$ and $Q$ are any statements, then $(P \Rightarrow Q) \Leftrightarrow \neg P \vee Q$
- Suppose that $P$ and $Q$ are statements. Reexpress $P \Leftrightarrow Q$ in terms of statements involving $P$ and $Q$, the connectives $\vee$ and $\wedge$, and the modifier $\neg$. Prove your assertion, and be careful with parentheses!
(Note: your answer to the second part will begin by stating your intended assertion and then verifying it. A formal proof does not require you to exhibit where your assertion comes from.)
- Prove that $\Rightarrow$ is transitive: if $P,Q,$ and $R$ are statements, then $$\left((P \Rightarrow Q) \wedge (Q \Rightarrow R)\right) \Rightarrow (P \Rightarrow R).$$
[N.B.: It is a fact (that you don't have to prove, but you may use in future assignments) that $\Leftrightarrow$ is also transitive.]
Here are some other problems you ought to complete, but you won't submit them as part of the assignment.
- You have spent an outsized portion of your mathematical life thinking about functions whose domain and codomain are some subsets of $\mathbb{R}$. Often these functions have been continuous. Sometimes in high school, students learn that a function is continuous if its graph can be drawn without picking up the pen while being drawn. The technical definition is more specific, and relies on what it means for $f$ to be continuous at some point $x_0$. The spiritual content of continuity of a function $f:\mathbb{R} \to \mathbb{R}$ at $x_0$ is as follows: for any specified tolerance, there is some notion of "close enough" so that if $x$ is ``close enough" to $x_0$, then the distance between $f(x_0)$ and $f(x)$ is smaller than the specified tolerance. Write this as a quantified statement, and then write out its negation as a quantified statement. Your statements should take the form of quantified variables followed by a predicate, where your predicate should only include the connectives $\wedge$ and $\vee$, together with the modifier $\neg$ (and any necessary parentheses).
- In number theory, Goldbach's conjecture states that every positive even number greater than $2$ can be written as the sum of two prime numbers.
- Write Goldbach's conjecture in the form of a quantified statement. (You might choose to use $2\mathbb{Z}$ to denote the set of even numbers, and $\mathbb{P}$ to denote the set of primes.)
- Many mathematicians believe that Goldbach's conjecture is true. What would you need to do in order to prove that Goldbach's conjecture is false?
Here are the Solutions.
Upload your solutions here.
Part A
- Let $A,B$ and $C$ be sets. Prove $A \times (B \cup C) = (A \times B) \cup (A \times C)$.
- For each of the following statements, determine if it is true or false for all sets $A,B,C$ and $D$. In the former case, give a proof. In the latter, give an explicit counterexample, including an explanation of how your purported counterexample shows the given statement to be false
- $(A \times B) \cup (C \times D) = (A \cup C) \times (B \cup D)$
- $(A \times B) \cap (C \times D) = (A \cap C) \times (B \cap D)$
- Suppose that $A$ and $B$ are sets. Prove that there exists an injection $f:A \to B$ if and only if there exists a surjection $g:B \to A$.
Part B
- Here are some important facts about images and inverse images: for any sets $X$ and $Y$, any subsets $A,B \subseteq X$ and $C,D \subseteq Y$, and any function $f:X \to Y$, we have
- $f(A \cup B) = f(A) \cup f(B)$.
- $f(A \cap B) \subseteq f(A) \cap f(B)$.
- $f^{-1}(C \cup D) = f^{-1}(C) \cup f^{-1}(D)$
- $f^{-1}(C \cap D) = f^{-1}(C) \cap f^{-1}(D)$
- $f^{-1}(f(A)) \supseteq A$
- $f(f^{-1}(C)) \subseteq C$
- Prove the first assertion above.
- Prove the fourth assertion above.
- Give an explicit example which shows that the second fact is false if we replace "$\subseteq$" with equality. (Though not stated explicitly at such, this implicitly asks you to provide specific values of $A,B,C,D,X,Y$ and $f$, and then prove that the equality of set fails in this case.)
- Prove that equality holds in the fifth fact for all subsets $A \subseteq X$ if and only if $f$ is injective.
- If $f:X \to Y$ and $g:U \to V$ satisfy $f(X) \subseteq U$, then we define the composition function $g \circ f: X \to V$ by the following rule: for any $x \in X$, we let $(g \circ f)(x) = g(f(x))$.
- Prove that if $f$ and $g$ are injections, then $g \circ f$ is an injection.
- Suppose $f$ and $g$ are surjections and that $Y = U$. Prove that $g \circ f$ is a surjection.
- Prove that $|(0,1)| = |[0,1]|$ by constructing an explicit bijection from $(0,1)$ to $[0,1]$.
[Hint: (1) We'll see later in the semester that it's impossible for there to be a continuous bijection from $(0,1)$ to $[0,1]$, so the function you create will wind up being discontinuous. (2) Rosenlicht gives an explanation for why infinite sets are precisely the sets which have a proper subset with which they are in bijection; the idea he uses can be adapted for your construction.]
Here are the Solutions.
Upload your solutions here.
Part A
- Prove that $|(0,1)| = |\mathbb{R}|$. Feel free to use (without proof) familiar facts about functions that you encountered in the calculus sequence or high school.
- Is $|\mathbb{R}| = |\mathbb{R}\times\mathbb{N}|$? Prove your assertion.
- In class we proved some results that tell us that the symbols "$=$", "$\leq$", and "$\geq$" (when used in the context of cardinalities) follow some familiar rules. In this problem you will prove some of the other "familiar" rules about these symbols.
- Prove that for any sets $A$,$B$, and $C$, if $|A| \leq |B|$ and $|B| \leq |C|$, then $|A| \leq |C|$.
- Prove that for any sets $A$,$B$, and $C$, if $|A| \geq |B|$ and $|B| \geq |C|$, then $|A| \geq |C|$.
- Prove that for any sets $A$,$B$, and $C$, if $|A|=|B|$ and $|B|=|C|$, then $|A|=|C|$.
- Prove that for any set $A$ we have $|A| = |A|$ and $|A| \leq |A|$ and $|A| \geq |A|$.
Part B
- Suppose that $A$ is an infinite set, and that $|B| \geq 2$. Let $\mathcal{F}$ be the set of functions with domain $A$ and codomain $B$. Prove that $\mathcal{F}$ is uncountable.
[Hint: Argue that $A$ has some countably infinite subset $\{a_1,a_2,a_3,\cdots\}$, then mimic Cantor's diagonalization argument to prove that there can't be a surjection $g:\mathbb{N} \to \mathcal{F}$.]
- Suppose that $\mathbb{F}$ is a field. A subfield $\hat{\mathbb{F}}$ is a subset of ${\mathbb{F}}$ which is a field under the addition and multiplication operations of $\mathbb{F}$.
- Show that for any subfield $\hat{\mathbb{F}}$ of $\mathbb{F}$, one has $0_{\hat{\mathbb{F}}} = 0_{\mathbb{F}}$.
- Show that for any subfield $\hat{\mathbb{F}}$ of $\mathbb{F}$, one has $1_{\hat{\mathbb{F}}} = 1_{\mathbb{F}}$.
- Suppose that $\mathbb{F}$ is a field for which there exists an element $i \in \mathbb{F}$ with $i^2+1_{\mathbb{F}} = 0_{\mathbb{F}}$. Prove that $\mathbb{F}$ cannot be ordered; i.e., it cannot be the case that there exists some subset $\mathbb{F}_+$ of $\mathbb{F}$ which is closed under addition and multiplication, and so that for any $f \in \mathbb{F}$ precisely one of the following statements holds: (1) $f \in \mathbb{F}_+$, or (2) $f = 0$, or (3) $-f \in \mathbb{F}_+$.
Here are the Solutions.
Upload your solutions here.
Part A
- Suppose that $\mathbb{F}$ is an ordered field, and that $a,b \in \mathbb{F}_+$. Prove that $a < b$ if and only if $a^2 < b^2$.
- Carefully prove --- using established properties of fields and the definition of ordered --- that any ordered field $\mathbb{F}$ must be infinite.
- Carefully prove --- using only axioms of an ordered field, properties of fields, the definition of inequality, and the trichotomy law --- that if $\mathbb{F}$ is an ordered field, and if $a,b \in \mathbb{F}$ satisfy the property that for all $\varepsilon \in \mathbb{F}_+$ we have $a \leq b+\varepsilon$, then $a \leq b$.
[Hint: it's useful to remember that while we don't know that the familiar number $2$ is on our field $\mathbb{F}$, the field $\mathbb{F}$ does have it's own ``copy" of $2$, namely $1_\mathbb{F}+1_\mathbb{F}$. If you want to use this element, you should denote it $2_\mathbb{F}$, and you should verify any claims you make about this element and its properties.]
Part B
- Suppose that $\mathbb{F}_1$ and $\mathbb{F}_2$ are complete ordered fields, where we use $+$ and $\cdot$ to denote the operations in $\mathbb{F}_1$ and $\oplus$ and $\odot$ to denote the operations in $\mathbb{F}_2$. We will use $<$ and $>$ to denote inequalities in $\mathbb{F}_1$, and $\prec$ and $\succ$ to denote inequalities on $\mathbb{F}_2$. We say that a function $f:\mathbb{F}_1 \to \mathbb{F}_2$ is operation preserving if, for all $s,t \in \mathbb{F}_1$ we have $$f(s+t) = f(s) \oplus f(t) \quad \text{ and } \quad f(s\cdot t) = f(s) \odot f(t).$$ We say that a function $f:\mathbb{F}_1 \to \mathbb{F}_2$ is not identically zero if there exists some $a \in \mathbb{F}_1$ so that $f(a) \neq 0_{\mathbb{F}_2}$. Prove that if $f:\mathbb{F}_1 \to \mathbb{F}_2$ is operation preserving and not identically zero, then it is inequality preserving: for all $s,t \in \mathbb{F}_1$, if $s < t$, then $f(s) \prec f(t)$.
[Hint: In your argument you might find it useful to prove that $f(1_{\mathbb{F}_1}) = 1_{\mathbb{F}_2}$, that $f(0_{\mathbb{F}_1})=0_{\mathbb{F}_2}$, and that for all $a \in \mathbb{F}_1$ we have $f(-a) = -f(a)$. It might also be useful to argue that if $b \neq 0_{\mathbb{F}_1}$, then $f(b) \neq 0_{\mathbb{F}_2}$.]
Note: In class we claimed that there is only one complete ordered field. This problem is one of the steps in arguing that this is true.
- Suppose that $\mathbb{F}$ is a complete ordered field, and that $X$ and $Y$ are nonempty sets so that $X \cup Y = \mathbb{F}$ and $X \cap Y = \emptyset$. Suppose further that for all $x \in X$ and all $y \in Y$ we have $x < y$. Prove that there exists some $\alpha \in \mathbb{F}$ so that $X = \{f \in \mathbb{F}: f < \alpha\}$ or $X = \{f \in \mathbb{F}: f \leq \alpha\}$.
- Suppose that $\mathbb{F}$ is a real number system, and that $X_1$ and $X_2$ are sets with least upper bounds $\alpha_1$ and $\alpha_2$, respectively. Argue that the set $X_1+X_2 = \{x_1+x_2: x_1 \in X_1 \text{ and }x_2 \in X_2\}$ has least upper bound $\alpha_1+\alpha_2$.
Here are the Solutions.
Upload your solutions here.
Part A
- For a set $S$ within a metric space $(E,d)$, the interior of $S$ --- denoted $\text{int}(S)$ --- is the union of all open sets contained in $S$: $$\text{int}(S) = \bigcup_{V \subseteq S \atop V \text{ open}} V.$$
- Prove that $\text{int}(S) = \{x \in E: \exists \varepsilon > 0 \text{ such that }B_E(x,\varepsilon) \subseteq S\}.$
- Prove that $S$ is open if and only if $S = \text{int}(S)$.
- Let $\mathbb{I}$ be the set of irrational numbers; that is $\mathbb{I} = \mathbb{Q}^c$. Prove that $\text{int}(\mathbb{I}) = \emptyset$. [Notes: (1) In this problem the ambient metric space is $(\mathbb{R},|\cdot|)$. (2) In light of the previous problem, one can interpret this result as saying that $\mathbb{I}$ is as far from being open as possible.]
- Let $S$ be a subset of a metric space $(E,d)$. Then the closure of $S$, denoted $\bar S$, is the intersection of all closed sets that contain $S$: $$\bar S = \bigcap_{K \supseteq S \atop K \text{ closed}} K.$$
- Prove that $S$ is closed if and only if $\bar S = S$.
- Prove that $\bar S = \{p \in E: \forall \varepsilon>0 \exists q \in S \cap B_E(p,\varepsilon)\}$.
- Prove that $\bar S = \{p \in E: p\not\in \text{int}(S^c)\}$.
Part B
- Suppose that $S$ is a subset of a metric space $(E,d)$. The boundary of $S$, written $\partial S$, is defined by $$\partial S = \bar S \cap \overline{S^c}.$$
- Prove that $\text{int}(S)$, $\text{int}(S^c)$ and $\partial S$ are mutually disjoint (i.e., the intersection of any two of these subsets is empty).
- Prove that $E = \text{int}(S) \cup \partial S \cup \text{int}(S^c)$.
- Prove that $S$ is closed if and only if $\partial S \subseteq S$.
- Prove that $S$ is open if and only if $\partial S \cap S = \emptyset$.
- Let $S$ be a subset of a metric space $(E,d)$. Prove that $(\bar S)^c = \text{int}(S^c)$.
- ($\star$) Let $n \in \mathbb{N}$ be given, and consider the function $d:\mathbb{R}^n \times \mathbb{R}^n \to \mathbb{R}$ given by $$d\left(\left(\begin{array}{r}x_1\\\vdots\\x_n\end{array}\right),\left(\begin{array}{r}y_1\\\vdots\\y_n\end{array}\right)\right) = \sum_{i=1}^n (x_i-y_i)^2.$$ Prove that $(\mathbb{R}^n,d)$ is not a metric space.
Here are the Solutions.
- For a set $S$ within a metric space $(E,d)$, the interior of $S$ --- denoted $\text{int}(S)$ --- is the union of all open sets contained in $S$: $$\text{int}(S) = \bigcup_{V \subseteq S \atop V \text{ open}} V.$$
-
Update: problems 5 and 6 have been struck from this pset, so you'll just do problems 1--4. Given the change, I've moved problem 3 into Part B.
Upload your solutions here.
Part A
- Prove that the closure of $S$ is the set of all limits of convergent sequences from $S$. That is, prove that $$\overline{S} = \left\{L \in X: \exists \{s_1,s_2,s_3,\cdots\} \text{ with each $s_i \in S$ and so that }L = \lim_{n \to \infty}\{s_n\}_{n =1}^\infty\right\}.$$
- Suppose that $\{p_n\}_{n =1}^\infty$ is a sequence in a metric space $(E,d)$ which converges to $L \in E$. Prove that $\{L,p_1,p_2,\cdots\}$ is a closed set in $E$. [Note: in this last expression, we consider $\{L,p_1,p_2,\cdots\}$ as a set in $E$, not as a sequence of points in $E$.]
[Hint: you can do this directly by applying the definition of "closed".]
Part B
- Suppose that $\{a_1,a_2,a_3,\cdots\}$ is a sequence in $\mathbb{R}$ with limit $L$, and construct a new sequence $\{b_n\}_{n \in \mathbb{N}}$ so that $b_n = \frac{1}{n}(a_1+a_2+\cdots+a_n)$. Prove that $\lim_{n \to \infty}\{b_n\} = L$.
- A permutation of $\mathbb{N}$ is a bijection $\sigma:\mathbb{N} \to \mathbb{N}$. For a sequence $\{p_1,p_2,\cdots\}$ in a metric space $(E,d)$, we say that $\{q_1,q_2,\cdots\}$ is a rearrangement of $\{p_1,p_2,\cdots\}$ if there exists some bijection $\sigma:\mathbb{N} \to \mathbb{N}$ so that for all $i \in \mathbb{N}$ we have $q_{\sigma(i)} = p_i$. As an example, if we let $\sigma$ be the permutation given by $$\sigma(n) = \left\{\begin{array}{cc}n+1 &\text{ if }n \text{ is odd}\\n-1 &\text{ if }n \text{ if even}\end{array}\right.$$ then the corresponding rearrangement of $\{p_1,p_2,\cdots\}$ is the sequence $\{p_2,p_1,p_4,p_3,p_6,p_5,\cdots,\}$.
Suppose that $\{p_1,p_2,\cdots\}$ is a sequence and there exists some $L \in E$ so that $\lim_{n \to \infty}\{p_n\} = L$. Prove that if $\{q_1,q_2,\cdots\}$ is a rearrangement of $\{p_1,p_2,\cdots\}$, then $\lim_{n \to \infty}\{q_n\} = L$ as well.
Here are the Solutions.
-
Upload your solutions here.
Note: this week you will only turn in problems from Part A. You can also work on problems from Part B if you like, but you will not turn them in for a grade. You can complete the first problem, and the first part of the second problem, before the start of class on Monday, October 25. You will be able to complete all three problems by the end of class on October 25.
Part A
- Suppose $(E,d)$ is a metric space, and that $S \subseteq E$ is complete. Prove that $S$ is closed (as a subset of $E$).
- Prove that compact sets are closed under finite union; that is, if $S_1,\cdots,S_n$ are each compact within a fixed metric space $(E,d)$, prove that $\cup_{i=1}^n S_i$ is also compact. Then, give an example to show that compact sets are not closed under arbitrary union.
- Are compact sets closed under arbitrary intersection? Prove or give a counterexample.
Part B (Optional and not to turn in!)
- Prove that any sequence of $\mathbb{R}$ has a monotonic subsequence. [Hint: you might break this into two cases: first when there exists some subsequence which has no minimum element, and second when this condition does not hold.]
- Suppose that $\{a_n\}_{n \in \mathbb{N}}$ is a bounded sequence of real numbers. We define two new sequences from this original sequence. The first is $\{u_n\}_{n \in \mathbb{N}}$, where for each $n \in \mathbb{N}$ we define $u_n = l.u.b.\{a_n,a_{n+1},a_{n+2},\cdots\}$; and the second is $\{\ell_n\}_{n \in \mathbb{N}}$, where for each $n \in \mathbb{N}$ we define $\ell_n = g.l.b.\{a_n,a_{n+1},a_{n+2},\cdots\}$.
- Prove that $\{u_n\}_{n \in \mathbb{N}}$ is convergent. [N.B. $\lim_{n \to \infty} \{u_n\}$ is often called the limit supremum of the original sequence $\{a_n\}_{n \in \mathbb{N}}$, and is denoted $\displaystyle \limsup_{n \to \infty} \{a_n\}$.]
- Prove that $\{\ell_n\}_{n \in \mathbb{N}}$ is convergent. [N.B. $\lim_{n \to \infty} \{\ell_n\}$ is often called the limit infimum of the original sequence $\{a_n\}_{n \in \mathbb{N}}$, and is denoted $\displaystyle \liminf_{n \to \infty} \{a_n\}$.]
- Suppose that $\lim_{n \to \infty} \{a_n\}$ exists. Prove that $\limsup_{n \to \infty}\{a_n\} = \lim_{n \to \infty} \{a_n\}$.
[NB. The same idea that you use in your proof can be used to prove that if $\lim_{n \to \infty} \{a_n\}$ exists, then $\liminf_{n \to \infty} \{a_n\} = \lim_{n \to \infty} \{a_n\}$, and so in fact we get $\liminf_{n \to \infty} \{a_n\} = \limsup_{n \to \infty} \{a_n\}$ in this case. As it turns out, if one has a sequence for which its limit inferior agrees with its limit superior, then one can use this to argue that the original sequence is convergent!]
- Define a sequence in $\mathbb{R}$ by $a_1 = \sqrt{2}$ and $a_n = \sqrt{2+a_{n-1}}$ for all $n \geq 2$. Prove that the sequence converges and determine its limit.
[Note: one way to view the content of this problem is to say that we're evaluating $\sqrt{2+\sqrt{2+\sqrt{2+\sqrt{2+\cdots}}}}$.]
Here are the Solutions.
-
Upload your solutions here.
Part A
- Let $E$ be compact, and suppose that $\{V_i\}_{i \in \mathcal{I}}$ is some open cover of $E$. Prove that there exists some $\varepsilon>0$ so that for all $p \in E$ there exists some $i \in \mathcal{I}$ with $\bar B_E(p,\varepsilon) \subseteq V_i$.
[Hint: try a proof by contradiction, and use this to create a sequence. What do you know about sequences in compact spaces?]
- Suppose that $f:E \to \hat E$ is a function that has the proper that for every open set $V \subseteq \hat E$, the set $f^{-1}(V)$ is open in $E$. Prove that if $S$ is a connected subset of $E$, then $f(S)$ is a connected subset of $\hat E$.
- Prove the intermediate value theorem: if $[a,b]$ is an interval in $\mathbb{R}$ and $f:[a,b] \to \mathbb{R}$ is a continuous function for which $f(a)f(b)<0$, then there exists some $c \in (a,b)$ so that $f(c) = 0$. [Hint: this is problem 3.]
Part B
- Let $f:\mathbb{R}^n \times \mathbb{R}^m \to \mathbb{R}^{n+m}$ be the function defined by $$f\left(\left(\begin{array}{c}x_1\\\vdots\\x_n\end{array}\right),\left(\begin{array}{c}y_1\\\vdots\\y_m\end{array}\right)\right) = \left(\begin{array}{c}x_1\\\vdots\\x_n\\y_1\\\vdots\\y_m\end{array}\right).$$ Prove that if $S$ and $T$ are closed subsets of $\mathbb{R}^n$ and $\mathbb{R}^m$ (respectively), then $f(S \times T)$ is a closed subset of $\mathbb{R}^{n+m}$.
- In the metric space $\mathbb{R}$ (under the usual metric), one of the very important objects of study is infinite series; they are defined as follows. If $\{a_n\}_{n \in \mathbb{N}}$ is a sequence of real numbers, then we define a new sequence $\{s_n\}_{n\in\mathbb{N}}$ by setting $s_n = a_1+\cdots +a_n$. (The sequence $\{s_n\}_{n \in \mathbb{N}}$ is sometimes called the sequence of partial sums.) The series $\sum_{n=1}^\infty a_n$ then is effectively shorthand for $\lim_{n \to \infty}\{s_n\}$, in the following sense: if $\lim_{n \to \infty} \{s_n\}$ exists, then we say that $\sum_{n=1}^\infty a_n$ converges to $\lim_{n \to \infty} \{s_n\}$; whereas if $\lim_{n \to\infty}\{s_n\}$ fails to exist, then we say that $\sum_{n=1}^\infty a_n$ diverges (or fails to converge).
- Prove the divergence test: if $\lim_{n \to \infty}\{a_n\} \neq 0$, then $\sum_{n=1}^\infty a_n$ diverges. (You might find it easier to prove the contrapositive of this statement.)
- Suppose that $\{a_n\}_{n \in \mathbb{N}}$ is a sequence such that $a_n \geq 0$ for all $n$. Prove that $\sum_{n=1}^\infty a_n$ converges if and only if there exists some $M \in \mathbb{R}_+$ with the property that for all $k \in \mathbb{N}$ we have $a_1+\cdots+a_k \leq M$.
Here are the Solutions.
- Let $E$ be compact, and suppose that $\{V_i\}_{i \in \mathcal{I}}$ is some open cover of $E$. Prove that there exists some $\varepsilon>0$ so that for all $p \in E$ there exists some $i \in \mathcal{I}$ with $\bar B_E(p,\varepsilon) \subseteq V_i$.
-
Upload your solutions here.
Part A
- Suppose that $f:E \to \hat E$ is a continuous function. Prove that closed sets are closed under inverse image; this means for all closed $C \subseteq \hat E$, one has $f^{-1}(C)$ is closed in $E$.
- Suppose that $a < b$ are real numbers and that $f:[a,b] \to \mathbb{R}$ is a continuous function so that $f(q) = 0$ for all $q \in [a,b] \cap \mathbb{Q}$. Prove that $f$ is identically zero (i.e., show that $f(x) = 0$ for all $x \in [a,b]$).
- Suppose that $f:[a,b] \to [c,d]$ is a strictly increasing, surjective function. Prove that $f$ is continuous.
[NB: to say that $f$ is strictly increasing means that whenever $x < y $, then $f(x) < f(y)$.]
Part B
- Suppose that $f:E_1 \to E_2$ is a continuous bijection, and that $E_1$ is compact. Prove that $f^{-1}$ is continuous as well. [Hint: can you show that $f$ sends closed sets to closed sets?]
- Last problem set you considered the notion of infinite series, which gives a formal way to consider --- for a sequence $\{a_n\}_{n \in \mathbb{N}}$ of real numbers --- whether the infinite sum $a_1+a_2 + a_3 + \cdots$ is meaningful. There are a handful of critical results concerning infinite series; you've already proved a few of them, but there are still a handful to go.
- Prove the geometric series theorem. This says that for $a,r \in \mathbb{R}$ with $a \neq 0$ and $|r| < 1$, we have $\sum_{n=0}^\infty ar^n$ converges to $\frac{a}{1-r}$. (NB: in fact, the geometric series is and "iff" result, but you only need to worry about proving this one direction. You can assume both directions moving forward.)
- Prove the limit comparison test. This says that if $\{a_n\}_{n \in \mathbb{N}},\{b_n\}_{n \in \mathbb{N}}$ are sequences of positive real numbers so that $\lim_{n \to \infty} \frac{a_n}{b_n} = L$ for some $L \in \mathbb{R}_+$, then $\sum_{n=0}^\infty a_n$ converges if and only if $\sum_{n=0}^\infty b_n$ converges.
Here are the Solutions.
-
Upload your solutions here.
Note: this week you will only turn in problems from Part A.
Part A
- Suppose that $S$ is a nonempty compact subset of $E$, and let $p_0 \in E$ be given. Prove that there exists some $p \in S$ so that $d(p_0,p) = \inf\{d(p_0,q): q \in S\}$.
- A function $f:E \to \hat E$ is called uniformly continuous if it has the following property: for all $\varepsilon>0$ there exists $\delta>0$ so that for all $p,q \in E$ with $d_E(p,q)<\delta$ one has $d_{\hat E}(f(p),f(q))<\varepsilon$.
Prove that a composition of uniformly continuous functions is uniformly continuous.
- Suppose that $f:\mathbb{R} \to \mathbb{R}$ is uniformly continuous, and for each $n \in \mathbb{N}$ let $f_n:\mathbb{R} \to \mathbb{R}$ be given by $f_n(x) = f(x+\frac{1}{n})$. Show that $\{f_n\}$ converges uniformly to $f$.
Here are the Solutions.
-
The problems this week are for you to consider, but are not meant to be submitted for a grade. You are encouraged to engage with them as you would a standard problem set, particularly since they engage with content that is relevant for upcoming exams.
Part A
- We finish our development of some well-known results on seriesby tackling prove what is perhaps the most important series test of all!
Ratio Test: Suppose that $\{a_n\}_{n \in \mathbb{N}}$ is a sequence which doesn't contain $0$. Prove that if $\lim_{n \to \infty} \left|\frac{a_{n+1}}{a_{n}}\right| = L$, then
- If $L<1$ then $\sum_{n=1}^\infty a_n$ converges.
- If $L>1$ then $\sum_{n=1}^\infty a_n$ does not converge.
NB. In your proof of the first result, you can use the following Cauchy criterion for convergence of a series: $\sum_{n=1}^\infty a_n$ converges if and only if for all $\varepsilon>0$ there exists $N \in \mathbb{N}$ so that for all $m,k>N$ we have $$\left|\sum_{n=k+1}^m a_n\right|<\varepsilon.$$
- We have seen that every differentiable function is continuous, but is it true that the derivative of any differentiable function is itself continuous? The answer is no: functions which are derivatives can fail to be continuous. It's a very interesting question to ask just how discontinuous such a function can be. In this problem we'll produce a function which is differentiable everywhere, but whose derivative fails to be continuous at a point.
Consider the function $f:\mathbb{R} \to \mathbb{R}$ defined by $$f(x)= \left\{\begin{array}{ll}x^2\sin\left(\frac{1}{x}\right),&\text{ if }x \neq 0\\0,&\text{ if }x = 0\end{array}\right. .$$ Prove that $f$ is differentiable on $\mathbb{R}$, but that its derivative fails to be continuous at $x=0$. You may assume the following facts:
- If $h$ and $g$ are functions and $x_0$ is a point so that $\lim_{x \to x_0} h(x) = 0$ and so that $g(x)$ is bounded in some open set containing $x_0$, then $\lim_{x \to x_0} (hg)(x) = 0$. [The proof for this is much like the proof you were asked to do on the second midterm concerning limits of sequences.]
- $|\sin(x)| = 1$ when $x$ is an odd multiple of $\pi/2$; $\sin(x) = 0$ when $x$ is a multiple of $\pi$; $\cos(x) = 0$ when $x$ is an odd multiple of $\pi/2$; and $|cos(x)|=1$ when $x$ is a multiple of $\pi$.
- $\frac{d}{dx}[\sin(x)] = \cos(x)$ and $\frac{d}{dx}[\cos(x)] = -\sin(x)$
- $\{\sin\left(\frac{1}{x}\right): x \neq 0\}$ is bounded
- Prove that derivatives satisfy the following version of the intermediate value property: if $f:[a,b] \to \mathbb{R}$ is differentiable on some open set containing $[a,b]$ and $f'(a) < 0 < f'(b)$, then there exists some $c \in (a,b)$ so that $f'(c) = 0$.
[Note that from above we see that the usual intermediate value theorem is off the table for this proof: we don't know that $f'(x)$ is continuous, so it fails the hypothesis of the usual intermediate value theorem. Instead, you might want to argue that there exists some (local) extreme for $f$ in $(a,b)$; you can do this using the extreme value theorem on $f$ and then verifying that $f(a)$ and $f(b)$ are not extreme values based on the given derivative information.]
- Suppose that $f$ is differentiable on an open interval containing zero. Suppose further that $\{x_n\}$ is some sequence so that $\lim\{x_n\} = 0$, with $f(x_n) = 0$ for all $n \in \mathbb{N}$, and with $x_n \neq 0$ for all $n \in \mathbb{N}$. Prove that $f(0) = f'(0) = 0$.
Here are the Solutions.
- We finish our development of some well-known results on seriesby tackling prove what is perhaps the most important series test of all!
-
Upload your solutions here.
Note: this week you will only turn in problems from Part A, but there are additional problems for Part B that you should think about as you work to understand the theory behind integration.
Part A
- Prove that the function $f:[a,b] \to \mathbb{R}$ given by $f(x) = x$ is Riemann integrable by verifying the definition of integrability. [Note: the good news here is that you know what the value of $\int_a^b x~dx$ should be! But you still need to show that Riemann sums get closer to this value.]
- Suppose that $\{x_n\}$ is the sequence with $x_n = \frac{1}{n}$. Let $f:[0,1] \to \mathbb{R}$ be $$f(x) = \left\{\begin{array}{ll}1,&\text{ if }x = x_n \text{ for some }n\\0,&\text{ if }x \neq x_n \text{ for any }n\end{array}\right.$$ Prove that $f$ is Riemann integrable with value $0$.
- Suppose that $f:[a,b] \to \mathbb{R}$ is a continuous function so that $f(x) \geq 0$ for all $x \in [a,b]$, and additionally there exists some $c \in (a,b)$ so that $f(c) \neq 0$. Prove that $\int_a^b f(x)~dx > 0$. You can do this either
- by showing there exists some $k>0$ and some $\delta>0$ so that for any partition $P$ with $\|P\|<\delta$ and any $S \in RS_P(f)$ we have $S>k$, or
- using what we know about splitting integrable functions up across subintervals to compute a lower bound on the integral directly (i.e., without Riemann sums).
Part B (not to be turned in)
- Use the step function characterization of integrability to prove that if $f:[a,b] \to \mathbb{R}$ is integrable, then $|f|:[a,b] \to \mathbb{R}$ given by $|f|(x) = |f(x)|$ is integrable.
- Prove that for an integrable function $f:[a,b] \to \mathbb{R}$ we have $$\left|\int_a^bf(x)~dx\right| \leq \int_a^b |f(x)|~dx.$$
- Consider the function $f:[0,1] \to \mathbb{R}$ given by $$f(x) = \left\{\begin{array}{ll}\frac{1}{x^2},&\text{ if }x \neq 0\\0,&\text{ if }x = 0.\end{array}\right.$$ Prove that $f$ is not integrable by showing that it fails the Cauchy criteria for integrability.
[Note: in a standard integral calculus class you would have learned that $\int_0^1 \frac{1}{x^2}~dx$ converges by the $p$-test. Recall, though, that despite the similarity in notation that we've adopted, this latter integral is actually not a "normal" integral, but is instead in the class of "improper" integrals. One can make rigorous the idea of "improper" integrals, and thereby give integral values (satisfying some of the integration properties we're used to) for a broader class of functions than the class of integrable functions.]
Here are the Solutions.