Math 299: Introduction to Mathematical Proof

Assignment #18 – Tuesday, April 18, 2017
  • 0. Memorize the four Rules of Inference for Proof by Induction given in the table of the same name in lecture notes in section 7.2 (below the Theorem 19 about equivalent forms). We will have a quiz on those definitions.
  • 1. Prove the following theorems. Use semiformal proofs using any of the shortcuts we discussed, but for reasons you can only use the rules from Logic, the Peano Axioms, the definition of 1,2,3,… that I wrote on the board, and any theorems or lemmas we proved. You can use the results of an earlier assigned or proven problem in the proof of a later problem but not vice-versa. You cannot use “by arithmetic” as a reason. All quantiied variables are assumed to be natural numbers. Hint: You can use the Lemma we proved in class! It’s very helfpul!
    • (a) Theorem (addition is commutative): $$\forall n,\forall m, m+n=n+m$$
    • (b) Theorem (harder than $1+1$): $$2+2=2\cdot 2$$
    • (c) Theorem (associativity of addition): $$\forall m,\forall n,\forall p, m+(n+p)=(m+n)+p$$
    • (d) Theorem (multiplicative identity):  $\forall n, n\cdot 1=n$ and $1\cdot n=n$
      (Hint: you don’t need induction to prove the first equality but you need it for the second.)
    • (e) Theorem (good thing we have $1+1$): $$1\leq 2$$
    • (f) Theorem (just as we expected): $\forall n,\sigma(n)=n+1$
    • (g) Theorem (strong induction): Prove that part (a) implies part (c) in Theorem 19 of the Lecture Notes.

 Course Handouts

Proof Software

  • Lurch – a math word processor that can check your proofs! I designed and wrote this software with former Scranton math major Nathan Carter specifically with this course in mind.
  • Toy Proofs – a “toy” proof system I developed to introduce students to the concept of formal proofs.
  • Circle Dot Game – describing the definitions behind the game.
  • Toy Proof Talk Slides – slides from a talk I gave on Toy Proofs at the 2009 Joint Mathematics Meetings

Mathematical Writing and Typesetting

Overleaf
  • Overleaf – a free website where you can easily produce LaTeX math documents through a web browser
  • Homework Template – click this link to start a new assignment (chose ‘Clone this project’ after clicking on this link).
  • Sample Document – an example document using the assignment style above.

Mathematical Writing and Typesetting (cont.)

LaTeX
  • LaTeX Cheat Sheet – a quick reference that can be printed on one sheet of paper 
    (posted by winston at stdout.org)
  • Detexify – a quick way to look up the name of a math symbol in \LaTeX by drawing it by hand.
LaTeX for laptops
  • LyX – a free math word processor based on LaTeX
  • MikTeX – install this and TeXnicCenter for LaTeX on your Windows computer
  • TeXnicCenter – install this and MikTeX for LaTeX on your Windows computer
  • MacTeX – Install this for LaTeX on your Mac computer