# Math 448 – Fall 2021: Problem Sets

Below are all of the Problem Sets for Math 448 – Fall 2021 to date. For the most recent Problem Set and additional information see the Math 448 Home Page.

Welcome!

Welcome to Math 448! I will post assignments and announcements here throughout the semester.  Check back frequently.  Below are links to some resources we will be using in the course.

Assignment #1 – Thursday, Sep 2, 2021
• 0. Read the course syllabus.  There is a link to it below. Report typos.
• 1. Read over Appendix A in the textbook.  This should be easy light reading and mostly familiar material. You don’t need to obsess over it, just refresh the ideas and terms.
• 2. Write up and hand in your answers to the following questions from the textbook.  See the syllabus for instructions on how to write up your assignments. You can do these by hand or type them LaTeX. It’s up to you. Put a pdf of your results in your shared Dropbox folder before the start of class on Thursday. These should be pretty easy, but it’s only the first assignment, so we don’t want you to pull any brain muscles.
• a. Problems #1,2,3,4 (all parts), Appendix B, page 519
• b. Problems #6,8 (all parts), Appendix B, page 519-520
• c. Problems #12 (all parts), Appendix B, page 520. Note that the image of the function is what we could call the image of the domain of the function (or equivalently, the range of the function). Also notice that what the book calls the range, we call the codomain. When the term we used in Math 299 differs from what is in the book, we naturally will go with the terminology and notation we used in Math 299.
Assignment #2 – Due Tuesday, Sep 7, 2021
1. Review all the material in Chapter 1 of the lecture notes for Logic, Predicate Logic, and Equality. Try to refresh your memory. If there’s something you forgot or don’t quite understand, ask. The entire rest of the course will depend on it.
2. Review and memorize the Rules of Inference for Propositional Logic, Predicate Logic, and Equality that are listed in the tables in the Lecture Notes starting on page 8 (memorize the template forms). Nothing will improve your proofs more than having all of the rules of logic at your fingertips.
3. Write up and hand in formal proofs of the following logic theorems using the formal proof style. There is an example of a formal proof of DeMorgan’s Law in Example 2 on page 10 of the notes, and you should use that format (no shortcuts or theorems allowed). These are generally much easier to write in Lurch or LaTeX than by hand because it’s hard to insert lines by hand when writing a formal proof. In these problems $P,Q$ have type ‘statement’ and $P(x)$ and $Q(x)$ are statements about $x$. (Keep in mind the precedence of the logical operations stated in the notes.)
1. $P \Rightarrow \neg \neg P$
2. $(Q \Rightarrow P) \Rightarrow (\neg P\Rightarrow \neg Q)$
3. $(P \text{ or } Q) \text{ and }\neg P \Rightarrow Q$
4. $(\neg \forall x, P(x)\Rightarrow Q(x)) \Leftrightarrow (\exists x, P(x) \text{ and } \neg Q(x))$
5. $\forall x, \Big( x=2 \text{ and } \big((P(x)\Rightarrow Q(x))\Rightarrow P(x)\big)\Big) \Rightarrow P(2)$
4. Most of all.. have fun!
Assignment #3 – Thursday, Sep 9, 2021
1. Read over Section 6 on Proof Shortucts in my lecture notes from Math 299. You can use these shortcuts in your semi-formal proofs for the rest of the course unless otherwise specified, so it’s good to review them. If you have questions, let me know.
2. Read over Appendix B in the textbook. It is mostly review. The main thing of importance is the proof Theorem B.1, which shows that a function is invertible (has an inverse function) if and only if it is bijective.
3. Write up and hand in semi-formal proofs of the following.
1. Prove the following extremely useful facts. We will use these facts a lot in this course.
1. The composition of injective functions is injective.
2. The composition of surjective functions is surjective.
3. The composition of bijective functions is bijective.
2. Prove that if $f$ is invertible then so is $f^{-1}$, and that $\left(f^{-1}\right)^{-1}=f$ in that case.
3. Prove that if $f:A\to B$, $g:B\to C$, and both $f,g$ are invertible, then then so is $g\circ f$, and $(g\circ f)^{-1}=f^{-1}\circ g^{-1}$ in that case.
Assignment #4 – Tuesday, Sep 14, 2021

Write or type up semi-formal proofs of the following.

1. Let $\sim$ be an equivalence relation on a set $A$ and $a,b\in A$. Prove the following easy and useful facts about equivalence classes.
1. $a\in [a]$
2. $a\in [b] \Leftrightarrow a\sim b$
2. Define a relation $\sim$  on $\mathbb{R}$ such that for every $s,t\in \mathbb{R}$ $$s\sim t \Leftrightarrow \cos(s)=\cos(t)$$
1. Prove $\sim$ is an equivalence relation.
2. Describe the set of all equivalence classes and give three particular examples of equivalence classes for $\sim$ and state exactly what numbers are in each one (no proof needed).
3. Let $\sim$ be an equivalence relation on a set $A$. Define $A/\mathord\sim$ to be the set of all equivalence classes of $\sim$, i.e., $$A/\mathord\sim = \{\,[a] : a\in A\,\}$$ Prove that $A/\mathord\sim$ is a partition of $A$.
4. Let $P$ be a partition of a set $A$ and defined a relation $\sim$ on $A$ such that for every $a,b\in A$, $$a\sim b \Leftrightarrow \exists z\in P, a\in z \text{ and } b\in z$$
1. Prove that $\sim$ is an equivalence relation.
2. Prove that $P=A/\mathord\sim$.
Assignment #5 – Thursday, Sep 16, 2021

Fun with induction!Write up and hand in your proofs of the following induction problems.

1. Partial Sums of a Geometric Series. Let $r\in\mathbb{R}$ be a real number other than $1$. For any $n\in\mathbb{N}$, $$1+r+r^2+r^3+\cdots+r^n=\frac{r^{n+1}-1}{r-1}$$ Note: you can use well known properties of the real numbers to justify lines that we do not have a formal definition for. For example, ‘by arithmetic’ or ‘by commutativity of multiplication’ or ‘by the law of exponents’. But anything we defined in the course you have to justify using the recipes in the notes (like induction).
2. Half of a Fundamental Theorem. A positive integer is said to be a baby prime if its only positive integer divisors are $1$ and itself. Use strong induction to prove that every positive integer is a product of baby primes.
3. Putnam Practice! (2009 B1) [Hint: Induction!] Show that every positive rational number can be written as a quotient of products of factorials of (not necessarily distinct) primes. For example, $$\frac{10}{9}=\frac{2!\cdot 5!}{3!\cdot 3!\cdot 3!}$$ [For Putnam practice problems you should not write them in semi-formal proof style, but rather use the word-wrapped style you would submit on the Putnam itself.]
Assignment #6 – Tuesday, Sep 21, 2021
• Ban on Fractions!! until further notice (and probably for the rest of the course) you cannot write any fractions in your proofs. They are banned! You will thank me later.
• Write up and hand in your proofs of the following problems from the textbook.
1. Exercise 1.1 #5 (i.e., exercise #5 in section 1.1 of the textbook).
2. Exercise 1.1 #6.
3. Exercise 1.1 #8.
4. Exercise 1.1 #10.
5. Induction Practice. For any subset $A$ of $\{1,2,\ldots,2021\}$ that does not contain any pair of consecutive numbers, let $P_A$ be the product of the elements of $A$. (The product of the elements in the empty set is $1$.) Determine with proof the sum of $P_A^2$ over all such subsets, $A$.
Assignment #7 – Thursday, Sep 23, 2021
• Write up and hand in your proofs of the following theorems.
1. Let $b\in\mathbb{Z}$ and $b\neq 0$. Then $\gcd(b,0)=\left|b\right|$
2. Let $n$ be any integer. Then $\gcd(n,n+1)=1$.
3. Let $a,b,k\in\mathbb{Z}$ with $a\neq 0$ or $b\neq 0$. Then $$\gcd(a,b)=\gcd(a,b+ak)$$