proof are important: you don’t understand something until you proof it. We want to come up with the right level of proof—this is a challenge. good proofs should be clear good proofs should be correct and convincing good proofs has layers: “cover the ‘hot’ technical details with various levels of intuition” Typically, in writing proofs, it could be helpful to write three levels of detail: “hint” of the proof - “proof by contradiction, proof by induction, follows from…” “sketch” of the proof - a one-paragraph of the description of the main ideas the proofy proof lecture proof are usually very scant of the third-level details you should think about how to fill in the details! methods of proof construction contradiction induction / strong induction most powerful type of proof—reductions, connecting problems together interactive proof systems We have two parties of a game, the proves and verifier. Something is a well-formed proof system IF BOTH: the prover can convience the verifier of the truthfulness the prover cannot make a statement to the verifier that is false under this system