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