6.042J/18.062J Staff Notes
Week of Tues., Feb. 1 through Monday, Feb. 7.

----------------------------------------------------------------------
Reading: M&R Section 0.7; Sections 7.1-3 and 7.5-6; Chapter 2.

----------------------------------------------------------------------
Recitation 0

Course bureaucracy.  Have students fill out Information Sheet (H00).
Go over Course Information (H01) and Course Outline (H02).  Talk about
sloppy administration and teaching, since it's the first time.  Tell
them we'll do our best, but if students are having any academic
trouble, they would be advised to wait until next year.

----------------------------------------------------------------------
Lecture 1 -- Tuesday, Feb. 1

10    Course overview
(17)
10    What is a proof?
(8)	Ex: $-1 = 1$ fallacy
	Logical proof systems
	  Axioms (or axiom schemata)
	  Rules of inference
	  Theorems
	  Consistency, completeness (brief mention)

35    Rules of inference
(31)	Propositions
	  "This statement is false" is not a proposition
	  Well definedness
	Modus ponens
	Syllogism
	Modus tollens & contrapositive
	Indirect proof
	  Ex: 4=3 => pope
	Boolean algebra
	  Truth tables
	  Laws
	Quantifiers
	  Bound and unbound variables (Grimaldi, p. 77)
	  \forall, \exists
	  Simple laws ($~\exists x ~p(x) iff \forall x p(x)$, etc.)

15    Axioms
(11)	Peano's postulates
	(Real number axioms, set theory, etc.)
        Mathematical induction (weak)

(18)	Tiling $2^n$-by-$2^n$ area missing one tile with L-shaped 3-ominoes.

10    Discussion of rigor vs. formality



----------------------------------------------------------------------
Lecture 2 -- Thursday, Feb. 3

10    Weak induction
	Ex: $\sum_{i=1}^n i = n(n-1)/2.
	Fallacy: All horses are same color.

10    Inductive (recursive) definitions
	Ex: Binary trees

25    Strong induction
	Ex: Every binary tree on $n\geq 1$ nodes has $n-1$ edges.

15    Well ordering
	Ex: $\sqrt{2}$ is irrational
	Corollary: Set bounded above has largest element.

20    Equivalence of induction and well-ordering
	

----------------------------------------------------------------------
Recitation 1 -- Friday, Feb. 4

Correct bugs on problems set.  Hand out revised Problem W1-11.

10    Discuss how addition, $\leq$, etc. can be defined using
	Peano's Postulates.  Tell them that we don't need to prove
	everything from Peano, but that what we write down as proofs
	assume a level of sophistication.  Once we've seen a proof
	of a basic fact, we don't need to keep proving the fact in
	every context.  We focus on proving whatever is new.

15    Inductive definitions: Fibonacci numbers
	Ex: Every natural number representable as a sum of distinct Fibs.

15    Tiling problem: When can you tile mxn rectangle with 3x1 and 2x2
	tiles.  Grounding induction.  Salvaging buggy "theorems".


10    Other examples of induction and well ordering

----------------------------------------------------------------------
Tutorial 1 -- Monday, Feb. 7

Oral homework
    Fallacies:
	$a=b$ implies $2=1$
	"A ham sandwich is better than nothing, and nothing is better
	 than complete happiness, so a ham sandwich is better than complete
	 happiness."
	obtuse angle = right angle
	There exist two irrationals a and b such that a^b = rational.
	$\sum_{i=1}^n \leq $ a constant times $n$.
    Simple induction examples
	

Written homework
    Logical reasoning
    Induction examples