# Math 448 – Fall 2019: Problem Sets

Below are all of the Problem Sets for Math 448 – Fall 2019 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, Aug 29, 2019
• 0. Read the course syllabus.  There is a link to it below.
• 1. Play Circle-Dot on my Toy Proofs site. Read the introduction to proofs and instructions for Circle-Dot first, and then see if you can beat all of the levels of Circle-Dot. We will discuss this as an example of a Formal Axiom System in class.
• 2. Download and install Lurch to your laptop. There is a link below.
• 3. 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 in Lurch or LaTeX.  It’s up to you.
• 1. Problem #30, Appendix B, page 522 (both parts (a) and (b)).
• 2. Problem #34, Appendix B, page 522
Assignment #2 – Due Tuesday, Sep 3, 2019
1. Send me the email address you use for your Dropbox folder so I can share files with you (like the Lurch file we did together in class).
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 (memorize the template forms). Nothing will improve your proofs more than having all of the rules of logic at your fingertips. We may have a quiz on this either next Tuesday or Thursday in class.
3. Write up and hand in your proofs of the following logic theorems using the formal proof style that we used in class. 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. All proofs should be in the formal proof style we used in class. In these problems $P,Q$ have type ‘statement’, $P(x)$ is a statement about $x$ and $P(x,y)$ a statement about $x,y$.
1. $\neg \neg P \Rightarrow P$
2. $(\neg Q \Rightarrow \neg P) \Leftrightarrow (P\Rightarrow Q)$
3. $P \text{ or }Q \Rightarrow Q \text{ or } P$
4. $P \text{ or } \neg P$
5. $\forall x, \forall y, x=y \Rightarrow y=x$
6. $(\exists x, \forall y, P(x,y)) \Rightarrow (\forall y,\exists x,P(x,y))$
7. $(\exists x,\neg P(x)) \Rightarrow (\neg \forall x, P(x))$
Most of all.. have fun!
Assignment #3 – Thursday, Sep 5, 2019
1. Read Section 5 on Proof Shortucts in my lecture notes from Math 299.
2. Write up and hand in your proofs of the following.
1. Prove the following extremely useful facts.
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 10, 2019

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

1. Prove the following theorems about set theory.
1. Theorem (order doesn’t matter):  $\{a,b\} = \{b,a\}$
2. Theorem (double negative):  $A – (B – A) = A$
3. Theorem (a set of sets):  $\{1,2\} \in \{A : \{1\} \subseteq A\}$
4. Theorem (always in the powerset):  $A\in \wp(A)$
2. Define a relation $\sim$  on $\mathbb{R}$ such that for every $s,t\in \mathbb{R}$ $$s\sim t \Leftrightarrow \sin(s)=\sin(t)$$
1. Prove $\sim$ is an equivalence relation.
2. Describe the equivalence classes (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 12, 2019

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

1. Appendix C #3. 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. Appendix C #17. [Hint: why do they specify $-1\leq x$?]
3. Appendix C #14. [Hint: they are defining relations “beats” and”plays” on the set of couples in the tournament.  How do you translate into a more formal provable math a statement like “Every couple plays every other couple.”.  What does “every other” mean mathematically?  How do you interpret “There are no ties.” as a mathematical statement (in terms of the relations “beats” and “plays”)?]
4. 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 17, 2019
• Read section 6 of the lecture notes. That is what we would have discussed in lecture today. Look at Section 1.1 in the book for additional information. It is not very difficult and something you probably have seen in other classes already. If you have questions about any of it feel free to ask me.
• 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,2019\}$ 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 19, 2019
• Read the proof of Bezout’s Lemma (either the proof of Theorem 1.2 in the textbook or the proof in the lecture notes.
• Write up and hand in your proofs of the following theorems.
1. Let $a,b\in\mathbb{Z}. If$b\mid a$and$a\neq 0$then$b\leq |a|$. 2. Let$b\in\mathbb{Z}$and$b\neq 0\$. Then $$\gcd(b,0)=\left|b\right|$$
3. Exercise 1.2 #8
4. Exercise 1.2 #20