# Math 299 – Spring 2020: Training Workouts

Below are all of the Training Workouts for Math 299 – Spring 2020 to date. For the most recent Training Workout and additional information see the Math 299 Home Page.

Welcome!

Welcome to Math 299.  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 #0 – Thursday, Feb 3, 2020
• Try to solve completely the more challenging levels of Scrambler in the ToyProofs software.  You can try it online here. Note that it isn’t enough to just win the game once or twice by random clicking and luck… try to understand what is going on so you can explain exactly how to win.  I will ask you in class on Tuesday to explain how to beat the various levels.  We already covered level weeny and level easy in class on Thursday, so you should start with level Fun and work your way up from there. Note that the levels do gradually increase in difficulty, and the last few are quite challenging.  In fact, don’t even try to figure out the last level, Death!.  It’s way too difficult.  All of the other levels can be solved by a good math student with some hard work and careful thinking. They tend to get progressively more challenging as you go.
• Read the course syllabus (see below).  Let me know if you have any questions.
Assignment #1 – Thursday, Feb 6, 2020
• 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 documents in there. All must be handed in prior to class on the day they are due. Be sure to name your file 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. You can prove them all in one proof, and then print that web page to a PDF document and place that document in your Dropbox homework folder with the appropriate file name (see the syllabus). Also put a text file in that folder that says which lines in your proof correspond to each of the five problems below (so I don’t have to search through the entire thing). You can prove them in any order in your proof.
• a.  $\bigcirc\bigcirc\bigcirc$
• b.  $\bullet\bigcirc\bigcirc$
• c.  $\bullet\bullet\bigcirc\bigcirc\bullet\bullet$
• d.  $\bigcirc\bigcirc\bullet\bullet\bullet$
• e.  $\bigcirc\bullet\bigcirc\bullet\bigcirc\bullet$
• 2. (Bonus) Can you explain why every circle-dot expression can be proven in the Circle-Dot toy system, or if not, determine with absolute 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. Try to figure out how to beat Trix Game.  I’ll ask for volunteers in class.
Assignment #2 – Tuesday, Feb 11, 2020
• 1. Download and install Lurch.  Install it on the laptop you will bring to class and any other computer that you use to do your homework and have Dropbox installed.
• 2. Take the Lurch Tutorial.  Run Lurch.  Then choose Help>Lurch tutorial from the Lurch menu.  It is a ten step tutorial and you might not understand some of the later stuff, but you should be able to complete the exercises in the tutorial anyway.
• 3. Beat TriX Game twice at difficulty level ‘death’. Run TriX Game by clicking here. Change the difficulty level to ‘death’. Beat the game once, then print that to a pdf file (on Mac just choose print from your browser and then click on the pdf button to save the file) and save that pdf file to your Dropbox folder in a subfolder called ‘Assignment 2’. Then choose ‘New Game’ and beat it a second time, and save that pdf file to Dropbox as well.
Assignment #3 – Thursday, Feb 13, 2020
• 0. Memorize the rules inference for Propositional Logic in Section 4 of the lecture notes (in your Dropbox folder).  We will have a quiz in class on Thursday where you will be asked to write them down entirely from memory. (Memorize the template forms in the second table.)
• 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. For each theorem, first state the theorem, then give a proof of it directly below it as I did in the examples in class. 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.  You do not have to use Lurch to check your work on this assignment, but you can if you want to.  If you have questions, just let me know. Put your assignment in Dropbox in a folder for Assignment 3. Save it as a .lurch file (not a pdf) so I can type in it and leave comments and grades.
• a. $Q \Rightarrow Q \text{ and } Q$
• b. $Q \Rightarrow Q \text{ or } P$
• c. $Q \Rightarrow (P \Rightarrow Q)$
• d. $(\neg Q \Rightarrow \neg P) \Rightarrow (P \Rightarrow Q)$
• e. $P \Leftrightarrow \neg\neg P$
• f. $\neg ( \neg P \text{ and } P )$
Assignment #4 – Tuesday, Feb 18, 2020
• 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 4” and name your files “Assignment 4 – firstname.lurch”.
• a. Easy warm up: $R \Rightarrow (Q \Rightarrow (P \text{ or } Q))$
• b. Easy one with actual statements instead of P, Q:  $1\leq x \text{ and } 1\leq y \Rightarrow 1\leq y$
• c. Anything follows from a contradiction:  $\rightarrow\leftarrow \Rightarrow P$
• d. Associativity of ‘or’: $(P \text{ or } Q) \text{ or } R \Leftrightarrow P \text{ or } (Q \text{ or } R)$
• e. DeMorgan’s Law 2: $\neg (P \text{ or } Q) \Leftrightarrow \neg P \text{ and } \neg Q$
• f. Law of Excluded Middle: $P \text{ or } \neg P$ (Hint: Don’t use or+.  Try contradiction.)
Assignment #5 – Thursday, Feb 20, 2020
• 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.  No other rules and no other theorems.  Put your files in your Dropbox folder.  Use the appropriate filename as specified in the syllabus.
• a. Alternate definition of implies:  $P \Rightarrow Q \Leftrightarrow \neg P \text{ or } Q$
• b. Distributivity of ‘or’ over ‘and’:  $P \text{ or } (Q \text{ and } R) \Leftrightarrow (P \text{ or } Q) \text{ and } (P \text{ or } R)$
• c. Alternate OR- rule:  $(P \text{ or } Q) \text{ and } \neg P \Rightarrow Q$
• 2. Write down any two statements in English. Substitute the first statement for P and the second statement for Q in the Alternate OR- rule in 1f above and write down the resulting statement.  Then rewrite that resulting statement in English, replacing math symbols like $\neg$ and $\Rightarrow$ and parentheses ‘(‘, ‘)’ with appropriate words or phrases in English.  You might have to add punctuation or rephrase things for it to make grammatical sense in English (for example, parentheses means something completely different in English).  Does the resulting statement make sense in English? Write this in your Lurch file in Dropbox.
Assignment #6 – Tuesday, Feb 25, 2020
• 1. Memorize the rules for quantifiers ($\forall$, $\exists$), equality (reflexive and substitution), and unique existence ($\exists !$) in Template form from the lecture notes for a quiz in class on Tuesday.
• 2. Prove each of the following theorems. 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, predicate logic, equality, and the copy rule.  You should use the rules from Predicate Logic and Equality > Blank Document topic in Lurch in your lurch file.  No other rules and no other theorems are allowed.  Put your files in your Dropbox folder.  Use the appropriate filename as specified in the syllabus.  Make a subfolder called Assignment 6 and put them all in there.
• 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$
• a. Double fun:  $(\forall x, \forall y, P(x,y)) \Rightarrow (\forall y, \forall x, P(x,y))$
• b. Distributivity:  $(\exists x, P(x) \text{ or } Q(x)) \Leftrightarrow (\exists y, P(y)) \text{ or } (\exists z, Q(z))$
Assignment #7 – Thursday, February 27, 2020
• 1. Memorize the rules for quantifiers ($\forall$, $\exists$), equality (reflexive and substitution), and unique existence ($\exists !$) in Template form from the lecture notes for a 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 7’ and put them all in there.
• a. Transitivity of equality: $x=y \text{ and } y=z \Rightarrow x=z$
• b. Quantifier fun: $(\exists x,P(x) \Rightarrow Q(x)) \Leftrightarrow (\forall y,P(y)) \Rightarrow (\exists z,Q(z))$
• c. DeMorgan’s Law: $\neg (\exists x,P(x)) \Leftrightarrow (\forall x, \neg P(x))$
Assignment #8 – Tuesday, March 3, 2020
• 1. 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 and the Peano axioms (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. Note that the Peano axioms are not currently defined in Lurch so you can use them in your proofs but Lurch can’t check them for you.
• a. Easy warm up: $P \text{ and } \exists x, Q(x) \Leftrightarrow \exists x, P \text{ and }Q(x)$
• b. Quantifiers and implication: $$(\forall x, P(x)\Rightarrow Q) \Leftrightarrow (\exists x, P(x))\Rightarrow Q$$      (if $x$ is not free in $Q$)
• c. In your future: A function $f$ that maps the positive real numbers to other positive real numbers is said to be continuous if and only if $$\forall \varepsilon, \forall x,\exists \delta,\forall y, \left|x-y\right|<\delta \Rightarrow \left|f(x)-f(y)\right|< \varepsilon\tag{C}$$ Similarly, $f$ is said to be uniformly continuous if and only if $$\forall \varepsilon,\exists \delta, \forall x,\forall y, \left|x-y\right|<\delta \Rightarrow \left|f(x)-f(y)\right|< \varepsilon\tag{UC}$$ (all identifiers other than $f$ have type "positive real").

Give a formal proof that every uniformly continuous function is continuous, i.e., that ‘(UC)$\Rightarrow$(C)’.

Note: You don’t need to know what a function is, or what absolute value means or what a real number is, or any facts about real numbers, or anything from calculus or anything like that. You only need to know about logic and quantifiers to prove this. Also note that you can’t type $|x|$ in Lurch but you can use $abs(x)$ instead if you want Lurch to check your proofs.

• d. Kay’s theorem: Give a formal proof using the Peano postulates that $$1+1\neq 1$$
• e. Nonzero numbers are successors: Give a formal proof using the Peano postulates that $$\forall n,n\neq 0 \Rightarrow \exists m,n=\sigma(m)$$ (Hint: use induction with $P(k)$ replaced by “$k\neq 0\Rightarrow \exists m,k=\sigma(m)$”)
Assignment #9 – Thursday, March 5, 2020
• 1. Rewrite the rules of inference for $\Rightarrow-$, $\Leftrightarrow+$, and or$-$ by expanding them as much as possible using the substitutions in the table in section 6.9 of the lecture notes
• 2. Prove each of the following theorems. Type up your semiformal proofs in Lurch.  Use the semiformal style we have been using, one statement per line, and a reason stated for each line that needs one, with optional premises where you feel they would help the reader.  You can only use the rules of propositional logic, predicate logic, equality, unique existence, and the copy rule and the Peano axioms and definitions from Number Theory given in the notes, as well as the shortcuts we went over 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 9’ and put them all in there. Note that Lurch cannot easily check semi-formal proofs because it needs the line numbers for citing premises so it mostly cannot check your semi-formal proofs unless you explicitly label your premises and then give a reason and premises for a particular step of work. Note that you can use the results that are proved in the Mar 2.lurch file in your Dropbox folder.
• a. Associativity of addition $$\forall m,\forall n,\forall p,m+(n+p)=(m+n)+p$$
• b. Additive Identity $$\forall n, 0+n=n$$
Assignment #10 – Tuesday, March 10, 2020
• 1. Memorize the Deriving Rules from Definitions and Theorems table in section 6.9 of the lecture notes. We will have a quiz on it on Tuesday.

We have been proving the basic properties of natural numbers listed in the 26 theorems in section 7 of the lecture notes. We have already proven #2-#6. Prove the following theorems from that list of theorems. Note that if you are proving theorem number $n$ you can use any theorem that precedes it in the list as a rule of inference even if we didn’t prove it (but never a theorem that comes after it in the list).

• b. Zero sums
• c. Cancellation law of addition
• d. Left multiplication by zero
• e. Left distributive law
• f. Successors are bigger
Assignment #11 – Thursday, March 12, 2020
• 1. Study for the midterm exam that we will have in class on Thursday. You should memorize all of the rules of inference we have covered in the course for which there is an expanded template form rule in the notes, i.e., the rules of logic, the Peano axioms, and the definition of strong induction and those related to divisibility. Bring your computer to class as the test will be taken on your laptop.
• 2. Translate the following true statement from English into formal logical notation involving variables, quantifiers, propositional logic operators, and using $L(x,y)$ for the predicate “$x$ loves $y$. Put your translatio at the top of your pdf file created in LaTeX along with the proof of the next problem.

If nobody loves themself, and everyone loves anyone who is loved by someone they love, then nobody is ever loved by someone they love.

Bonus Assignment – Midterm Redux

In order to make your extended Spring Break more enjoyable, here is a bonus assignment you can work on optionally. Since this is for bonus points (I’ll count it as one in-class quiz) you don’t have to do it, and I’m making three different options you can choose from (sort of). You can only choose one option. Write them up in Lurch or Overleaf in a separate file, and put it in a folder called ‘Bonus Assignment’ in your Dropbox folder. I don’t want to set a particular due date, so send me an email when you are finished (but the offer expires after this week.)

• Option 1: Correct the proofs you got wrong on the midterm exam. This only refers to the last four questions on the exam. You cannot choose this option if you got at least three of the four proofs correct (or got two right and just lost one point on one for a typo).
• Option 2: Correct the proofs you got wrong on the midterm exam (from the last four questions) AND prove the Division algorithm – Existence theorem (problem 30 at the end of Chapter 7). You can use any of the theorems that precede it. You cannot choose this option if you got all of the four proofs correct, because … duh.
• Option 3: (hard core mathematicians only) Prove the Division algorithm – Existence theorem AND Division algorithm – Uniqueness theorem (problems 30, 31 at the end of Chapter 7). You can use any of the theorems that precede it. Anyone can chose this option if you really love math and want to go for the glory, but if you only got one proof correct on the midterm your time would be better spent on Option 1.
Assignment #12 – Thursday, April 2, 2020

Type up the following proofs in LaTeX.  Use the semiformal proof style we have been using, one statement per line, and a reason stated for each line that needs one, with optional comments where you feel they would help the reader.  You can do that by clicking on the Homework Template link below on this page. To hand in your document, download the pdf and put your pdf file in your Dropbox folder with the appropriate filename.

• 1. Translation  If $m, n$, and $p$ are natural numbers, then $m < n$ if and only if $m+p < n+p$
• 2. Suppose $n$ is a natural number, and $(a)_{k=0}^n$ and $(b)_{k=0}^n$ are finite sequences of natural numbers. Then $$\sum_{k=0}^n (a_k+b_k) = \sum_{k=0}^n a_k+\sum_{k=0}^n b_k$$
• 3. For any natural numbers $n$ and $m$, $$\binom{n+m}{n}=\binom{n+m}{m}$$.
Assignment #13 – Tuesday, April 7, 2020

Type up the following proofs in LaTeX.  Use the semiformal proof style we have been using, one statement per line, and a reason stated for each line that needs one, with optional comments where you feel they would help the reader.  You can do that by clicking on the Homework Template link below on this page. To hand in your document, download the pdf and put your pdf file in your Dropbox folder with the appropriate filename.

• 0. If $z$ is any natural number, then $z^1=z$.
• 1. The natural number $k!$ is always positive.
• 2. If $m,n,z$ are natural numbers then $(z^m)^n=z^{m\cdot n}$
• 3. For all natural numbers $n\geq 5$, $$n^2<2^n$$
• 4. If $x,y,z$ are real numbers and $x+y=x+z$, then $y=z$.
• 5. For all natural numbers $n$ and $m$, $$n!\cdot m!\cdot\binom{n+m}{n}=(n+m)!$$ (Note: You cannot use properties of real numbers on this problem yet.)
Assignment #14 – Tuesday, April 14, 2020
$\newcommand{\negative}{{\vphantom{#1}}^-{#1}}$

Type up the following proofs in LaTeX.  Use the semiformal proof style we have been using, one statement per line, and a reason stated for each line that needs one, with optional comments where you feel they would help the reader.  You can do that by clicking on the Homework Template link below on this page. To hand in your document, download the pdf and put your pdf file in your Dropbox folder with the appropriate filename. All variables and constants are assumed to be real numbers unless stated otherwise.

You can use any theorems prior to the chapter on real numbers (keeping in mind that theorems about the natural numbers do not automatically extend to theorems about the reals). Other than that you can only use the axioms and definitions about the real numbers, and any theorem you prove first to use in a later proof (of course). But you cannot use any theorems in the problem sections in Chapter 9 in the Lecture Notes.

• 0. A warm up  $\negative{1}\neq 1$.
• 1. One is positive  $0<1$
• 2. Double negative  For all real numbers $x$, $$\negative{\left(\negative{x}\right)}=x$$
• 3. Alternate additive inverse  $\negative{x}=\negative{1}\cdot x$
• 4. Signed products  $\negative{x}\cdot\negative{y}=x\cdot y$
• 5. Alternate multiplicative inverse  $x^-=\frac{1}{x}$
• 6. Trichotomy  For any real numbers $x,y$ exactly one of the following is true:
1. $x\lt y$
2. $x=y$
3. $y\lt x$
• 7. Product of negatives is positive  If $x\lt 0$ and $y\lt 0$ then $0\lt x\cdot y$
• 8. Some reals are natural  Consider the sequence of real numbers, $(N_k)_{k=0}^\infty$, defined at the beginning of section 9.4 in the notes. All of the Peano axioms hold for $(N_k)_{k=0}^\infty$. Let’s check a few.
1. Show Peano Axiom N3 holds for $(N_k)_{k=0}^\infty$.
2. Show Peano Axiom M1 holds for $(N_k)_{k=0}^\infty$.
3. Show Peano Axiom I holds for $(N_k)_{k=0}^\infty$.
Assignment #15 – Thursday, April 16, 2020
• Prove the following theorems. Type up your proofs in Lurch. Lurch can actually check these if you want, but it is not required. If you don’t want Lurch to check your proofs, you can use semiformal proofs and any shortcuts we have defined prior to the set theory topic.
If you want to check your proofs in Lurch you must start your assignment by choosing the topic Set Theory>Elementary Set Theory>Basics>Blank Document. You will have to use numbered lines and the rules of inference for the set theory definitions that are built-in to Lurch (CMD+SHIFT+R). You do not have to cite any premises which refer to the previous line or previous declaration. You can also use any theorem about Logic that is a built-in rule in Lurch in that same topic. All upper case variables represent sets.
• a. Theorem (too easy): $x\in\{a\} \text{ and } y\in\{a\} \Rightarrow x=y$
• b. Theorem (also too easy): $A\subseteq A$
• c. Theorem (order doesn’t matter):  $\{a,b\} = \{b,a\}$
• d. Theorem (double negative):  $A – (B – A) = A$
• e. Theorem (not a subset):  $\neg(A\subseteq B) \Leftrightarrow \exists x,x\in A\cap \overline{B}$
Assignment #16 – Tuesday, April 21, 2020
• Prove the following theorems. Type up your formal proofs in Lurch.  Use the semiformal style we have been using in class – omitting unnecesary premises where possible.  If the theorem is in “If … then” form instead of $\Rightarrow$ form, use the “Given” style of proof instead of using implies plus.
If you want to check your proofs in Lurch you must start your assignment by choosing the topic Set Theory>Elementary Set Theory>Basics>Blank Document. You can then use any of the definitions from Basic Set Theory that are built-in to Lurch (CMD+SHIFT+R). You can also use any theorem about Logic that is a built-in rule in Lurch in that same topic. All upper case variables represent sets. Note that Lurch writes ordered pairs and ordered $n$-tuples using angle brackets instead of parentheses, so that e.g., the ordered pair $(x,y)$ would be written $\langle x,y \rangle$. You can use either notation (the former is more standard, but I like the latter better). The $\LaTeX$ command for the angle brackets are \langle and \rangle.
• 1. Theorem (too easy): If $\langle x,y\rangle = \langle y,x\rangle$ then $x=y$.
• 2. Theorem (Cartesion calculation): $\{2,3\}\times\{5\}=\{\langle 2,5\rangle,\langle 3,5\rangle\}$
• 3. Theorem (Powerful): If $A\subseteq B$ then $\wp(A)\subseteq\wp(B)$.
• 4. Theorem (a set of sets):  $\{1,2\} \in \{A : \{1\} \subseteq A\}$
• 5. Theorem (always in the powerset):  $A\in \wp(A)$
• 6. Theorem (function fun):  Suppose $f\colon \mathbb{N}\to\mathbb{N}$ and $\forall n\in \mathbb{N},f(n)=3n+1$. Then $f$ is injective but not surjective.
• 7. Theorem (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$$ Hint: Use the rule for showing two functions are equal.
Assignment #17 – Thursday, April 23, 2020
• Prove the following theorems. You should give semiformal proofs for these, using any of the shortcuts we learned so far (using the shortcuts is not mandatory, but it is allowed). Type your proofs in either Lurch or LaTeX. Your choice. Upper case variables represent sets.
• 1. Theorem (relative complement is not associative):  If $x\in A\cap B \cap C$ then $x\in A – (B – C)$ and $x\notin (A – B) – C$
(Note: So it is not true that relative complement is associative, because there exists sets $A,B,C$ such that $A – (B – C)\neq (A – B) – C$.)
• 2. Theorem (images preserve subsets):  If $f\colon A \to B$ and $S\subseteq T$ and $T\subseteq A$ then $f(S)\subseteq f(T)$.
• 3. Theorem (identity maps are bijective):  For any set $A$, the function $\mathrm{id}_A$ is bijective.
Assignment #18 – Tuesday, April 28, 2020
$\newcommand{\negative}{{\vphantom{#1}}^-#1}$
• Prove the following theorems. You should give semiformal proofs for these, using any of the shortcuts we learned so far (using the shortcuts is not mandatory, but it is allowed). Type your proofs in either Lurch or LaTeX. Your choice. Upper case variables represent sets.
• 1. Theorem (another DeMorgan): $(A\cup B)’=A’ \cap B’$.
• 2. Theorem (composition preserves injectivity): The composition of injective functions is injective.
• 3. Theorem (inverse of a composition): If $f\colon A\to B$ and $g:B\to C$ are both invertible functions (i.e., $f^{-1}$ and $g^{-1}$ both exist) then $$f^{-1}\circ g^{-1} = (g\circ f)^{-1}$$
(Hint: show the function on the left is the inverse of $g\circ f$ using the Inverse function + recipe in the notes.)
• 4. Theorem (inverse image of a codomain is the domain): If $f\colon A\to B$ then $f^\mathrm{inv}(B)=A$.
• 5. Theorem (not an equivalence relation):  If $$\sim = \left\{(1,1),(2,2),(3,3),(1,2),(2,1),(1,3),(3,1)\right\}$$ then $\sim$ is not an equivalence relation on $\{1,2,3\}$.
• 6. Theorem (equivalence classes are disjoint):   If $\sim$ is an equivalence relation on a set $A$ and $x,y\in A$, then either $[x]=[y]$ or $[x]\cap[y]=\left\{\right\}$.
• 7. Theorem (not not an equivalence relation): If $\sim$ is a relation on $\mathbb{Z}$ such that for all $x,y\in\mathbb{Z}$, $$x\sim y \Leftrightarrow x=y\text{ or }x=\negative{y}$$ then $\sim$ is an equivalence relation.
Assignment #19 – Thursday, April 30, 2020
• Prove the following theorems. First write a semiformal proof using any of the shortcuts we learned so far (using the shortcuts is not mandatory, but it is allowed). Then convert that proof to an expository style proof. Type both of your proofs in LaTeX. Save the pdf to Dropbox as usual.
• 1. Theorem (bijection with a proper subset): Let $E=\{ n\in \mathbb{N} : n \text{ is even}\}$ and define $f\colon \mathbb{N}\to E$ by $f(n)=2n$. Then $f$ is a bijection.
Note: This is a bijective correspondence between the set of all natural number and the set of even natural numbers, which is a proper subset. Can that happen with finite sets?
• 2. Theorem (another DeMorgan, oh my!): Given an indexing set $I$ and a set $A_i$ for each $i\in I$, $$\left(\bigcup_{i \in I} A_i\right)’ = \bigcap_{i \in I} A_i’$$
Assignment #20 – Tuesday, May 5, 2020
$\newcommand{\negative}{{\vphantom{#1}}^-#1}$
• Prove the following theorems. You should give semiformal proofs for these, and then write up an expository version of any proof you successfully prove semiformally. Type your proofs in LaTeX. Upper case variables represent sets.
• 1. Theorem (sum of the first $n$ odd numbers): The sum of the first $n$ odd natural numbers is $n^2$, i.e., $$\sum_{k=0}^m (2k+1) = (m+1)^2$$
• 2. Theorem (not a subset): A set $A$ is not a subset of set $B$ if and only if the set $A\cap B’$ is nonempty.
• 3. Theorem (composition preserves surjectivity): The composition of surjective functions is surjective.
Note that in a previous assignment you showed that composition preserved injectivity. So combining these two results we see that the composition of bijections is also a bijection.
• 4. Theorem (complement is a bijection): Let $A$ be a set and define $f\colon \wp(A)\to\wp(A)$ by $f(X)=X’$. Then $f$ is a bijection.
Note: in such a situation, $X’$ refers to $A-X$.
• 5. Theorem (a partial ordering): Let $A$ be a set and $\sim$ be the relation on $\wp(A)$ such that for every $S,T\in\wp(A)$, $$S\sim T \Leftrightarrow S\subseteq T$$ Then $\sim$ is a partial order.
Assignment #21 – Thursday, May 7, 2020
• Write an Expository Combinatorial Proof for each of the following theorems, being sure to follow the rules of mathematical writing we went over in class from the handout in your Dropbox folder. Write up these problems in $\LaTeX$ in the Homework Article style linked to below. You must use a combinatorial argument, not a proof ‘by arithmetic’ or by using bijective functions or any previous theorems. We are starting with a clean slate. Pure counting arguments only! Just find something reasonable to count, and count it in two different ways, using only the definitions of the symbols involved.
• Theorem A (a shorter proof that this is still true!): The following combinatorial identity holds: $$1+1=2$$
• Theorem B: For any combinatorial expresions $n$, $m$, and $k$ with $m+k=n$, $$\binom{n}{k}=\binom{n}{m}$$
• Theorem C: Froggy Frog is at the bottom of a staircase with $n$ stairs and wants to get to the top. He can only jump $1$ or $2$ stairs at a time and never backtracks. Let $W_n$ be the number of ways Froggy can jump from the bottom of the stairs to the top. Then $$W_{n+2}=W_{n+1}+W_{n}$$
Assignment #22 – Tuesday, May 12, 2020
• 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 Tuesday. It should contain at least three of the six proofs. I won’t grade them for correctness until your final draft but I will give you a homework grade for making progress. It should be written in the Homework Article style linked to below. Be sure to make the entire assignment readable as an independent document (say, if you gave it to someone who isn’t registered for our course). In particular, list the theorem statements above each proof, and add a little commentary where necessary.
• 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, substitution, or previous formulas derived in class. Just 100% pure counting!
• Theorem A: $\binom{6}{2}\cdot\binom{4}{3}=\binom{6}{3}\cdot\binom{3}{2}$
• Theorem B: For all combinatorial expressions $n$, $k$ with $k\leq n$, $$(k+1)\cdot\binom{n+1}{k+1}=(n+1)\cdot \binom{n}{k}$$
• Theorem C: For all combinatorial expressions $n$ $$1+2+3+\cdots+n=\binom{n+1}{2}$$
• Theorem D: For all combinatorial expressions $n$ and $k$ with $k\leq n$ $$\binom{k}{k}+\binom{k+1}{k}+\cdots+\binom{n-1}{k}+\binom{n}{k}=\binom{n+1}{k+1}$$
Assignment #23 – Thursday, May 14, 2020
• 1. Keep working on the Term Paper portion of the Final Exam.To help keep you on track, put a draft of your Take Home Final Exam pdf in Dropbox before Thursday. It should contain a draft of at least four of the six proofs. I won’t grade them for correctness until your final draft but I will give you a homework grade for making progress.
• 2.  Write up and hand in a combinatorial proof for each of the following. Write your proofs in Homework Article style and put your pdf file in Dropbox as usual.  You cannot use any algebra or previous formulas derived in class. Just 100% pure counting!
• Theorem A: For all combinatorial expressions $n$ and $k$ with $2\leq k\leq n$ $$\binom{2n+2}{k}=\binom{2n}{k}+2\binom{2n}{k-1}+\binom{2n}{k-2}$$
• Theorem B: For all combinatorial expressions $n$ $$\binom{n}{0}+\binom{n}{1}+\binom{n}{2}+\cdots+\binom{n}{n}=2^n$$
Final Exam – Thursday, May 21, 2020, 5:15pm
• Finish working on the Term Paper Final Exam. Follow the instructions on the first page of the exam. Place the final copy in your Dropbox folder before 5:15pm on Thursday, May 21. We will meet in our Zoom classroom at 5:15pm on Thursday, May 21 for a course wrap up chat. Send any questions to the Homework Hotline as usual. Game on!