Math 299 – Spring 2023: Training Workouts

Welcome to Math 299, where mathematicians are born!  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.

• Download and install Dropbox on your laptop and send me the email address you used for your Dropbox account if you haven’t done so already.
• Read the course syllabus (see below).  Let me know if you have any questions.
• Read Problem #1 on the 2021 Prove it! admissions test and then play the Scrambler! Product Catalog game until you figure out how to reliably beat any goal on all three machines (Juggler, Frogger, Whirligig). You do not have to answer parts (a)-(f) of the question or hand in anything, but you should try figure out a strategy that is guaranteed to beat all three machines no matter what goal comes up when you select “New Goal”. I will ask you in class how to solve each machine. Prize cookies may be awarded.

• 0.For each assignment that you hand in in Dropbox, make a folder called “Assignement #n”, where n is the Assignment number I have posted here. So for this assignment, put it in a subfolder of our shared Dropbox folder called “Assignment #1” and put your document in there. All assignments must be handed in prior to class on the day they are due. Be sure to name your files as explained in the syllabus below.
• 1. Answer Problem #1.4 at the end of Chapter 1 in the lecture notes. Type up your answer (you can use any editor for this assignment) and save your file to Dropbox as described above.
• 2. Try to figure out how to consistently beat Trix Game.  This is another example of a Toy Proof system. I’ll ask for volunteers in class. Write up your solution and put it in the same document as the provious problem. Cookies may be awarded.

• Reminder: For each assignment that you hand in in Dropbox, make a folder called “Assignement #n”, where n is the Assignment number I have posted here. So for this assignment, put it in a subfolder of our shared Dropbox folder called “Assignment #2” and put your documents in there. All assignments must be handed in prior to class on the day they are due. Be sure to name your files as explained in the syllabus below.
• 1. Prove each of the following Circle-Dot theorems. You must use the Toy Proof software to ensure that your proofs are correct. Prove them using the software, and then print that web page to a PDF document and place that pdf document in your Dropbox homework folder with the appropriate file name. You can prove all four parts in one proof if you want, rather than proving them separately (but its ok if you prove then separately too). If you put one pdf for each problem below, name the files so I know which one is which. You can also just insert the printout into a larger document so that you can type comments or mark up the pdf with a stylus (for my iPad users).
  • Thm H: $\bullet\bigcirc\bullet$
  • Thm J: $\bigcirc\bigcirc\bigcirc$
  • Thm M: $\bigcirc\bigcirc\bullet\bullet\bullet$
  • Thm R:  $\bullet\bigcirc\bullet\bigcirc\bullet\bigcirc$
• 2. (Bonus) Can you explain why every circle-dot expression can be proven in the Circle-Dot toy system, or if not, determine with certainty exactly those expressions which can? Write up your answer in a pdf document (using whatever editor you like for now) and put it in the same Dropbox folder with this assignment.
• 3. Download and install Lurch 0.8. Install it on the computer that you use to do your homework where you have our shared Dropbox folder. Bring that laptop to class with you until further notice.

• 0. Install Lurch 0.8 on your laptop and bring it to class with you from now on. If the link I sent in the last assignment didn’t work for you use this link instead (or the link at the bottom of this page).
• 1. Answer questions 2.1, 2.2, and 2.3 in the lecture notes. You can type up your answers using any editor or write them by hand on paper. Either way scan or print your document to a pdf and put it in the appropriate folder in Dropbox. (Don’t put a .doc or .docx or .tex file.)

• 0. Memorize the rules inference for Propositional Logic in Section 4.2 of the lecture notes.  We will have a quiz in class on Tuesday where you will be asked to recall them entirely from memory. (Memorize the template forms in the second table on page 15-16.)

• 1. Type up a Formal proof of each of the following statements. You can only use the rules of Propositional Logic discussed in class. To do that, start your new document by using the Lurch menu File > Choose Topic.. > Logic > Propositional Logic > Blank Document. Put your name at the top. For each theorem, first state the theorem, then give a proof of it directly below the theorem as I did in the examples in class (I put a copy of both the original document I shared with you and the one I did in class in your Dropbox folder).

  Number each statement in the proof, and give a reason for every statement (except Assumptions, which need no reason).  Use the auto-numbered list in the Lurch to number the lines – don’t type the line numbers by hand. Be sure to give the line numbers for the statements used as the premises (i.e. inputs) immediately after the reason.  Use the TAB key to indent your assumptions, and also to line up your reasons in a separate column.  Do all of your work in Lurch.  Save your work often! Lurch has been known to crash! You can use Lurch to check your work as I showed you in class.

  If you have questions, just let me know. Put your assignment in Dropbox in a folder for Assignment 4. Save it as a .lurch file (not a pdf) so I can type in it and leave comments and grades. It’s ok to put the file in there when it is partially finished – I won’t grade it until after Tuesday, and if you get stuck or have a problem while working on the proofs I can open your file and help you figure it out.

  • a. $Q \text{ and } P \Rightarrow P \text{ and } Q$
  • b. $Q \Rightarrow Q \text{ or } P$
  • c. $Q \Rightarrow (P \Rightarrow Q)$
  • d. $P \Leftrightarrow \neg\neg P$
  • e. $\rightarrow\leftarrow \Rightarrow P$
  • f. $\neg ( \neg P \text{ and } P )$

• Prove each of the following tautologies. Type up your formal proofs in Lurch.  Use the formal style we used in class – numbered lines, one statement per line, and a reason and premises stated for each line that needs one.  You can only use the rules of propositional logic and the copy rule.  Start your new document by using the Lurch menu File > Choose Topic.. > Logic > Propositional Logic > Blank Document. No other rules and no other theorems.  Put your files in your Dropbox folder in a subfolder named “Assignment 5” and name your files “Assignment 5 – firstname.lurch”.
• • a. Easy warm up: $R \Rightarrow (Q \Rightarrow (P \text{ or } Q))$
  • b. Alternate Definition of implies 1:  $\neg P \text{ or } Q \Rightarrow (P \Rightarrow Q)$
  • c. (Half of) Associativity of ‘or’: $(P \text{ or } Q) \text{ or } R \Rightarrow P \text{ or } (Q \text{ or } R)$
  • d. DeMorgan’s Law 2: $\neg (P \text{ and } Q) \Rightarrow \neg P \text{ or } \neg Q$

• 1. Prove each of the following tautologies. Type up your formal proofs in Lurch.  Use the formal style we used in class – numbered lines, one statement per line, and a reason and premises stated for each line that needs one.  You can only use the rules of propositional logic and the copy rule.  Start your new document by using the Lurch menu File > Choose Topic.. > Logic > Propositional Logic > Blank Document. No other rules and no other theorems.  Put your files in your Dropbox folder in a subfolder named “Assignment 6” and name your files “Assignment 6 – firstname.lurch”. Since Lurch may bog down if you ask it to check this many proofs in one document, you can make more than one Lurch document, with the filename indicating which problem(s) it contains and put them all in the Assignment 6 folder.
• • a. Easy peasy:  $P \text{ and } Q \Leftrightarrow Q \text{ and } P $
  • b. Finishing what we started:  $P \text{ and } \neg Q \Rightarrow \neg(P \Rightarrow Q)$
  • c. Excluded middle:  $P \text{ or } \neg P$
  • d. Alternate definition of implies 2:  $(P \Rightarrow Q) \Rightarrow \neg P \text{ or } Q $
  • e. Distributivity of ‘or’ over ‘and’:   $$P \text{ or } (Q \text{ and } R) \Leftrightarrow (P \text{ or } Q) \text{ and } (P \text{ or } R)$$
  • f. Alternate OR- rule:  $(P \text{ or } Q) \text{ and } \neg P \Rightarrow Q$

• 1. Memorize the rules for quantifiers ($\forall$, $\exists$) in Template form from the lecture notes for a possible quiz in class on Thursday.
• 2. Answer the following questions in the Lecture Notes – 5.24 parts (f), (h), (i), (j) and (k). Just type your answers in your Lurch document with the two proofs below.
• 3. Prove each of the following theorems. Type up your formal proofs in Lurch.  Use the formal style we have been using – numbered lines, one statement per line, and a reason and premises stated for each line that needs one.  You can only use the rules of propositional logic and predicate logic (no other rules and no other theorems even if they are available in Lurch).  You should use the rules from Logic > Predicate Logic > Blank Document topic in your lurch file (select it from the File>Choose Topic menu and check the both boxes at the bottom of the dialog before clicking the OK button). Put your files in your Dropbox folder in a subfolder called ‘Assignment 7’.
• • a. Existence warmup: $(\exists x,Q(x))\Rightarrow (\exists x,P(x)\Rightarrow Q(x)).$
  • b. Mini-DeMorgan’s Law: $(\forall x,\neg P(x)) \Rightarrow (\neg \exists y, P(y))$

• 1. Memorize the rules for quantifiers ($\forall$, $\exists$), equality (reflexive and substitution), and unique existence ($\exists !$) from the lecture notes for a possible quiz in class on Tuesday.
• 2. Prove each of the following theorems. Type up your formal proofs in Lurch. Use the formal style we have been using – numbered lines, one statement per line, and a reason and premises stated for each line that needs one.  You can only use the rules of propositional logic, predicate logic, equality, unique existence, and the copy rule (no other rules and no other theorems even if they are available in Lurch).  You should use the rules from Logic > Predicate Logic & Equality > Blank Document topic in your lurch file (select it from the File>Choose Topic menu and check the both boxes at the bottom of the dialog before clicking the OK button). Put your files in your Dropbox folder.  Use the appropriate filename as specified in the syllabus.  If you have more than one file for this assignment make a subfolder called ‘Assignment 8’ and put them all in there.
• • a. The other half:  $(\exists y, P(y)) \text{ or } (\exists z, Q(z)) \Rightarrow (\exists x, P(x) \text{ or } Q(x))$ (We did the reverse direction in class together.)
  • b. Easy peasy: $0\lt 7 \Rightarrow (\exists x,0\lt x) \text{ and } (\exists x,x\lt 7)$
  • c. Another easy warm up: $\left(\forall x,\forall y,L(x,y)\right)\Rightarrow L(\text{Alice},\text{Bob})$
  • d. Transitivity of equality: $x=y \text{ and } y=z \Rightarrow x=z$
  • e. Quantifier fun: $(\exists x,P(x) \Rightarrow Q(x)) \Leftrightarrow (\forall y,P(y)) \Rightarrow (\exists z,Q(z))$
  • f. Makes sense: $((\forall x,\exists !y,L(x,y)) \text{ and } \neg(a=b)) \Rightarrow \neg(L(c,a) \text{ and }L(c,b))$

• Prove each of the following theorems. Type up your formal proofs in Lurch. Use the formal style we have been using – numbered lines, one statement per line, and a reason and premises stated for each line that needs one. You can only use the rules of propositional logic, predicate logic, equality, unique existence, and the copy rule (no other rules and no other theorems even if they are available in Lurch).  You should use the rules from Logic > Predicate Logic & Equality > Blank Document topic in your lurch file (select it from the File>Choose Topic menu and check the both boxes at the bottom of the dialog before clicking the OK button). Put your files in your Dropbox folder.  Use the appropriate filename as specified in the syllabus.  If you have more than one file for this assignment make a subfolder called ‘Assignment 9’ and put them all in there.
• • 1. And implication of implications $\big((P\Rightarrow Q)\Rightarrow P\big)\Rightarrow P$
  • 2. A case of cases: $(P \Rightarrow R) \text{ or } (Q\Rightarrow R)\Rightarrow ((P \text{ and }Q)\Rightarrow R)$
  • 3. Let variables represent people and $L(x,y)$ means “$x$ loves $y$”. Translate the following English sentence into a statement of formal logic, and prove it the way we proved that I am Dracula in tonight’s class.

    If everyone loves themselves then everyone loves someone.

  • 4. Equivalent definition of unique existance: $(\exists !x,P(x))\Leftrightarrow(\exists x,P(x) \text{ and }\forall y,\neg (y=x) \Rightarrow \neg P(y))$

• Do overs! Prove each of the following theorems. Some of them will be for the second (or third) time, but this time you can use the theorems built into Lurch instead of just the rules of inference (you can still use the rules of inference, too, of course). Type up your semi-formal proofs in Lurch (you don’t have to use every shortcut, or any shortcuts for that matter, since some shortcuts will prevent Lurch from checking your work). You should use the rules from Logic > Predicate Logic & Equality with theorems > Blank Document topic in your lurch file (select it from the File>Choose Topic menu and check the both boxes at the bottom of the dialog before clicking the OK button). The shorter your proof (with green thumbs), the better! Don’t just give the same proof you gave previously (or one that we did in class). Put your files in your Dropbox folder.  Use the appropriate filename as specified in the syllabus.  If you have more than one file for this assignment make a subfolder called ‘Assignment 10’ and put them all in there.
• • 1. Super Easy Now: $P\text{ or }\neg P$
    
  • 2. Take Two: $P\text{ or }\neg P$
    This time don’t use the Excluded Middle rule. Instead prove it by contradiction using DeMorgan’s Law.
  • 3. DeMorgan Extravaganza: $$\neg \Big(\forall x, \exists y, \forall z, P(x,y,z)\Big) \Rightarrow \Big(\exists x, \forall y, \exists z, \neg P(x,y,z)\Big)$$
  • 4. Double trouble: $\Big(\neg(P\Rightarrow Q) \text{ or }\neg P\Big) \text{ or }Q $
  • 5. A first taste of numbers: Using the first five Peano Axioms and Logic only, try to prove Exercise 7.2 in the Lecture Notes $$\forall n, n\neq 0 \Rightarrow \exists m,n=\sigma(m)$$ Unfortunately, Lurch can’t easily check this one (because I don’t have the Peano Axioms built in). So time for the training wheels to come off!

1. Midterm Take Home!  Rename the midterm subfolder in Dropbox on your hard drive ‘Assignment 11’. Finish answering any problems that you didn’t finish on time in class.
2. Prove the following theorems You can use an informal proof that uses theorems from logic, but not about the natural numbers and Peano Axioms. Write up your solutions in Lurch (though you probably won’t be able to validate them unless you add the Peano Axioms to the top of your file, which I didn’t really teach you how to do).
   • a. Problem 7.3: $\forall n, n\neq \sigma(n)$
     Hint: Try induction.
   • b. Problem 7.4: $\forall n, \sigma(n)=n+1$
     Hint: You don’t need induction for this one.
   • c. Problem 7.5: $\forall m, \forall n, \forall p, (m+n)+p = m+(n+p)$
     Hint: Try induction on $p$ for arbitrary $m,n$.

• Prove each of the following theorems. Type up your semiformal proofs in Lurch.  Use the semiformal style illustrated in class – unnumbered lines, one statement per line, and a reason for each line that needs one.  Use the shortcut versions of the Peano Axioms in the table in section 7.3 of the lecture notes, rather than the formal versions in section 7.1. You can (and should) use the shortcut of using rules derived from previously proven theorems. When proving theorems in the problem set at end of chapter 7 you can use any earlier numbered theorem as a rule of inference to help you prove a later numbered theorem (but not the other way around, unless you prove it first). You can also prove any theorems we proved in class or that were assigned in a previous homework assignment as a rule of inference (or rules derived from them) in your proofs. For induction proofs, use the version of the induction templat (N4) that has you show $P(\sigma(k))$ rather than the one that has you show $P(k+1)$ because the latter one needs parentheses that will only confuse you. Unfortunately, Lurch cannot check a semi-formal proof because it doesn’t know how to handle the shortcuts. Put your file in your Dropbox folder in a subfolder called ‘Assignment 11’.
• • 7.12 (multiplicative identity) $\forall n,1\cdot n=n \text{ and } n\cdot 1=n$
      (Hint: try induction on $n$ and remember you can use previous problems as rules [7.1-7.11].)
  • 7.23 (reflexivity of $\leq$) $\forall n,n\leq n$
  • 7.35 (every number divides itself) $\forall m,1\mid m \text{ and } m\mid m$

1. Memorize the definitions – in the Flavors of Induction table and the Definitions of Number Theory table on pages 39-49 of the Lecture Notes for a quiz on Tuesday. (You do not have to memorize the Peano axioms.)
2. Prove each of the following theorems. Type up your semiformal proofs in Lurch.  Use the semiformal style illustrated in class. When proving theorems in the problem set at end of chapter 7 you can use any earlier numbered theorem as a rule of inference to help you prove a later numbered theorem (but not the other way around, unless you prove it first). You can also prove any theorems we proved in class or that were assigned in a previous homework assignment as a rule of inference (or rules derived from them) in your proofs. Put your file in your Dropbox folder in a subfolder called ‘Assignment 13’.
   • (a) 7.8 (commutativity of addition) $\forall m,\forall n, m+n=n+m$
   • (b) 7.10 (cancellation law for addition) $\forall m,\forall n,\forall p, m+p=n+p \Rightarrow m=n$
   • (c) 7.36 (divisors are smaller) $\forall m, \forall n, n\neq 0\text{ and }m\mid n \Rightarrow m\leq n$
   • (d) (no ‘tweens) Imitate the proof we did in class to prove that there is no natural number between $n$ and $\sigma(n)$, i.e., prove $$\forall n,\neg \exists k,n\lt k \text{ and } k\lt \sigma(n)$$
   • (e) (easier than 2) The number 4 is not prime.

• 1. Do over. Choose any homework problem that was assigned after the midterm exam and write up its proof in Overleaf using the semiformal proof style illustrated in class.
• 2. Prove the following theorem in the same Overleaf project as the previous problem. Download the pdf from Overleaf and put it in your Dropbox folder in a subfolder named “Assignment #14”. If you have any questions about Overleaf or $\LaTeX$, just ask me on the Homework Hotline.
  • TheoremThe natural number $k!$ is always positive.

• 1. Prove the three theorems – (8.2(c), 8.5 (a), and 8.7) at the end of our shared Overleaf document that I made in class (Math 299 – in class 2023). The one I shared with you is read-only so make a copy and delete the proofs that are already there. I have the probmems and the proof environments already typed for you there, so you just have to fill in the proofs. Download the pdf when you are finished and put it in your Dropbox folder in a subfolder named “Assignment #15”. If you have any questions about Overleaf or $\LaTeX$, just ask me on the Homework Hotline.

• Let’s get real. Prove each of the following theorems and write up your semiformal proof in a single LaTeX file project. When you are done, download the pdf file from Overleaf and put it in your Dropbox folder in a subfolder named “Assignment #15”. You can only use the Axioms of Real numbers, and anything prior to Chapter 9 (or any theorems that you prove yourself using those Axioms, but not theorems in the problem sets in Chapter 9 of the lecture notes). You do not need, and should not use, anything at all from Chapter 7 of the lecture notes. All constants in the following questions are real numbers.
  • 0. multiplicative inverse of one is its own multiplicative inverse $$(1^-)^-=1^-$$
  • 1. Alternate definition of multiplicative inverse Let $x$ be a real number. If $x\neq 0$ then $x^-=\frac{1}{x}$.
  • 2. Uniqueness of predecessors Let $x$ and $y$ be real numbers. If $x+1=y+1$ then $x=y$.
  • 3. Not both There do not exist any real numbers $x$ and $y$ such that $x\lt y$ and $y\lt x$.
  • 4. Nostalgia for M1 Let $x$ and $y$ be real numbers. Then $x\cdot(y+1)=x+x\cdot y$.
  • 5. Yah, not as easy as you might expect $$0\lt 1$$ (where 0 and 1 are the real number constants, not the natural number constants).

• Memorize the Axioms for the Real Numbers (except for the completenes axiom) for a quiz on Thursday.
• Prove each of the following theorems and write up your semiformal proof in a single LaTeX file project. When you are done, download the pdf file from Overleaf and put it in your Dropbox folder in a subfolder named “Assignment #17”. You do not need, and should not use, anything at all from Chapter 7 of the lecture notes. You do not need to use the completeness axiom, so I’ll save you time by telling you there is no need to even try to go down that path. You can use ‘by arithmetic’ to justify statements about natural number arithmetic involving only natural number constants (no variables). You can also assume that the embedding of the natural numbers in the real numbers is valid, so that, e.g. the real number 2 corresponds to the natural number 2 (which in turn is the successor of 1, so that… wait for it… $1+1=2$… in the real numbers as well).
  • 1. (9.26) zero divisors If $x,y$ are real numbers and $x\cdot y=0$ then either $x=0$ or $y=0$.
  • 2.Recursive definitions can be used to define infinite sequences of real numbers in addition to
    • a. (8.24) Define a recursive sequence of natural numbers $a$ such that $a_0=0$ and for all natural numbers $n$ we have $a_{n+1}=3\cdot a_n+2$. Then for any $n$ $$2\cdot a_n+1=3^n$$
    • b. Now define a recursive sequence of real numbers $a$ such that $a_0=0$ and for all natural numbers $n$ we have $a_{n+1}=3\cdot a_n+2$. Then for any $n$ $$a_n=3^n-1$$
  • 3. Unnatural There exists a real number between zero and one.

Mixed bag. Prove each of the following theorems and write up your semiformal proof in a single LaTeX file project. When you are done, download the pdf file from Overleaf and put it in your Dropbox folder in a subfolder named “Assignment #18”. The proof of each theorem can only use results from earlier chapters and the axioms, definitions, and previously proven results from the same chapter that the theorem is from.

• a. Thm 9.28 (Unnatural numbers) There exist integers which are not natural numbers.
• b. Thm 9.46 (interesting multiples of 25) For all $n\in\mathbb{N}^+$, the number $6^n-5\cdot n-1$ is divisible by $25$.
• c. Thm 9.10 (Alternate Additive Inverse) If $x$ is a real number then $\vphantom{x}^-{x}=\vphantom{1}^-{1}\cdot x$.
• d. Thm 10.11 (transitivity of $\subseteq$) $A\subseteq B\text{ and } B\subseteq C \Rightarrow A\subseteq C$
• e. Thm 10.35 (power sets of complements) $A\subseteq B\Rightarrow \mathcal{P}(B’)\subseteq\mathcal{P}(A’)$
• f. Thm 10.59 (linear bijections) A linear function is bijective if and only if it has nonzero slope.
  Here we define a linear function to be a map $f\colon \mathbb{R}\to\mathbb{R}$ such that for some $m,b\in\mathbb{R}$, $$f(x)=m\cdot x+b$$ In this situation we say that $m$ is the slope of $f$.

• Prove each of the following theorems and write up your semiformal proof in a single LaTeX file project. When you are done, download the pdf file from Overleaf and put it in your Dropbox folder in a subfolder named “Assignment #19”.
  • 1. A set of sets (Thm 10.4): $\{\,1,2\,\}\in\{\,A : \{\,1\,\}\subseteq A\,\}$
  • 2. Modular addition:Let $a,b,c,d$ be integers and $m$ a positive integer. If $a\underset{m}{\equiv}b$ and $c\underset{m}{\equiv}d$ then $$a+c\underset{m}{\equiv}b+d$$

1. Memorize the definitions of Basic Set Theory in the table on page 60 of the lecture notes for a short quiz at the start of class.
2. Mixed bag. Prove each of the following theorems and write up your semiformal proof in a single LaTeX file project. When you are done, download the pdf file from Overleaf and put it in your Dropbox folder in a subfolder named “Assignment #20”. In these problems $A , B, C$ and $D$ are sets.
   • a. Thm 10.2 (Order doesn’t matter) $\{\,a,b\,\}=\{\,b,a\,\}$
   • b. Thm 10.35 (Powerset and Union) $\mathcal{P}(A)\cup\mathcal{P}(B) \subseteq \mathcal{P}(A\cup B)$
   • c. Thm 10.32 (Subsets are contagious) If $A\subseteq C$ and $B\subseteq D$ then $A\times B\subseteq C\times D$.
   • d. Thm 10.57 (identity for composition) If $f\colon A\to A$ then $$f\circ \text{id}_A=\text{id}_A\circ f=f$$
   • e. Thm 10.40 (Composition is associative) If $h\colon A\to B$, $g\colon B\to C$, and $f\colon C\to D$ then $$f\circ (g\circ h)=(f\circ g)\circ h$$
   • f. Thm 10.47 (Composition of injectives is injective)If $f\colon A\to B$ and $g\colon B\to C$ are both injective then $g\circ f$ is injective.

• Memorize the definitions of Basic Set Theory in the table on page 60 of the lecture notes for a short quiz at the start of class.
• Prove each of the following theorems and write up your proof twice once as a semi-formal proof and a second time at a traditional, informal, expository proof like the example I did in class. Write them all in a single LaTeX file project using the article style Overleaf homework template below (not the usual template). When you are done, download the pdf file from Overleaf and put it in your Dropbox folder in a subfolder named “Assignment #21”.
  • 1. Thm 10.48: The composition of surjective functions is surjective.
  • 2. Thm 10.61: If $\sim$ is a relation on $\mathbb{Z}$ such that for all $x,y\in\mathbb{Z}$, $$x\sim y\text{ if and only if } x=y \text{ or } x=\vphantom{y}^-{y}$$ then $\sim$ is an equivalence relation.

• Prove each of the following theorems and write up your proof twice once as a semi-formal proof and a second time at a traditional, informal, expository proof. Write them all in a single LaTeX file project using the article style Overleaf homework template below (not the usual template). When you are done, download the pdf file from Overleaf and put it in your Dropbox folder in a subfolder named “Assignment #22”.
  • 1. Thm (better late than never) If a function has an inverse function then it is bijective.
  • 2. Thm 10.30 (even more DeMorgan) For any sets $I$ and $A_i$ with $i\in I$, $$\displaystyle\left(\bigcup_{i\in I} A_i\right)’ = \bigcap_{j\in I} A_j’$$
  • 3. Thm 10.60 (not an equivalence relation) Suppose $\sim$ is the set $$\sim = \Set{ (1,1),(2,2),(3,3),(1,2),(2,1),(1,3),(3,1)}$$ Then $\sim$ is not an equivalence relation on the set $\Set{1,2,3}$.
  • 4. Thm 10.65 (congruence is an equivalence relation) Let $m$ be a positive integer. The relation $\underset{m}{\equiv}$ is an equivalence relation on any nonempty set of integers.

• 0. Memorize the definitions of Functions in the table on page 68 (section 10.4) of the lecture notes for a short quiz at the start of class.

• 1. Start working on your Take Home Final Exam. To help keep you on track, put a draft of your Take Home Final Exam pdf in Dropbox before class on Thursday. It should use the Homework Template – Article style linked to below, not the usual Homework Template – Handout style. Create all of the necessary sections and pieces (Title, Abstract, Introduction section, Proof section, Summary section, bibliography) and you can start to fill in the commentary. Put your pdf in a Final Exam subfolder of your Dropbox folder, and call it ‘Final Exam Draft 1.pdf’.

  You can start to pick out which of the six theorems you would like to prove in accordance with the instructions in your Dropbox folder, and you can include the theorem statements and even the proofs if you find some you like. You can always change your mind about which problems you want to answer at any time before the exam is due, and keep in mind that any problems that are assigned for homework or done in class are no longer eligible. So one good strategy would be to try to prove six easy one point proofs first, and then try to increase your score from there by upgrading some to two points or three points, or collect some of the bonus points for induction, or proof by cases, writing style, or diagrams. See the instructions for details.

• 2.  Write up and hand in a semiformal proof of the following. Use a separate LaTeX pdf from your draft of your final exam above, and put it in a subfolder of your Dropbox folder called ‘Assignment 23’.
  • a. Thm 10.71 (a partial order)  Let $A$ be a set and $\sim$ be the relation on $\mathcal{P}(A)$ such that for every $S,T\in\mathcal{P}(A)$, $$S\sim T \Leftrightarrow S\subseteq T$$ Then $\sim$ is a partial order.

• 0. Memorize the definitions of Functions in the table on page 68 (section 10.4) of the lecture notes for a short quiz at the start of class.

• 1. Continue working on your Take Home Final Exam. If you are having LaTeX problems with your current draft, send me an email and share your Overleaf project with me and I can help you get back on track. Put the new draft in your final exam folder of Dropbox labeled “Final Exam Draft 2.pdf”
• 2.  Write up and hand in a combinatorial proof for each of the following. Write your proofs in LaTeX using the Homework Article style and put your pdf file in Dropbox as usual.  You cannot use any algebra, arithmetic, substitution, or previous formulas derived in or out of class. Just 100% pure counting!
  • 1. Thm 12.10 (counting over computing) $$\binom{6}{2}\cdot\binom{4}{3}=\binom{6}{3}\cdot\binom{3}{2}$$
  • 2. Thm 12.13 (binomial complement) $$\binom{m+n}{m}=\binom{m+n}{n}$$
  • 3. Thm 12.15 (choose vs. permute) $$(n)_k=\binom{n}{k}\cdot k!$$
  • 4. Thm 12.17 (good things come in pairs) $$\binom{2n+2}{k} = \binom{2n}{k} + 2\cdot\binom{2n}{k-1} + \binom{2n}{k-2}$$
  • 5. Thm 12.26 (combination recursion) $$\binom{n+1}{k+1}=\binom{n}{k}+\binom{n}{k+1}$$

• 1. Continue working on your Take Home Final Exam. If you are having LaTeX problems with your current draft, send me an email and share your Overleaf project with me and I can help you get back on track. Put the new draft in your final exam folder of Dropbox labeled “Final Exam Draft 3.pdf”
• 2.  Write up and hand in a combinatorial proof for each of the following. Write your proofs in LaTeX using the Homework Article style and put your pdf file in Dropbox as usual.  You cannot use any algebra, arithmetic, substitution, or previous formulas derived in or out of class. Just 100% pure counting!
  • 1. Variant of 12.17 (good things come in triples) $$\binom{n+3}{k}=\binom{n}{k}+3\cdot\binom{n}{k-1}+3\cdot\binom{n}{k-2}+\binom{n}{k-3}$$
  • 2. Thm 12.30 (Gauss Redux) $$1+2+\cdots+n=\binom{n+1}{2}$$

• Finish working on the Term Paper Final Exam. Follow the instructions document in your Dropbox folder. Place the final copy in your Dropbox folder before 5:15pm on Thursday, May 18. Send any questions to the Homework Hotline as usual. Game on!