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.4: $\forall n, n\neq \sigma(n)$
     Hint: Try induction.
   • b. Problem 7.5: $\forall n, \sigma(n)=n+1$
     Hint: You don’t need induction for this one.
   • c. Problem 7.6: $\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.