Mathematics for Computer Science Top 10 Proof Techniques NOT Allowed

Mathematics for Computer Science “Top 10 Proof Techniques NOT Allowed” After going through a quarter-life-crisis  and switching a lot about my approach to MIT (more on that later), Ive finally figured out my classes for junior fall. One of the classes Im in this semester is 6.042, or in regular-speak: Mathematics for Computer Science. It. Is. SUPER. Actually, I didnt expect it to be this great at all. Even though I loved math in high school, when I came to MIT, I became disillusioned both with math and my own abilities. After taking 18.02 and 18.03, I just wasnt stellar at it anymore, probably because I didnt study enough, and mostly because of cyclical reinforcing feelings that math became uninteresting and difficult. But when I was teaching Probability and Combinatorics in Italy, passion for problem solving, mathematical exploration, and experimentative curiosity revived in me. I remembered that I love puzzles and thinking unconventionally to solve cool problems. And that is exactly what 6.042 is about. The actual topics covered are Proofs and Number Theory, Structures (Graph Theory, Relations and Partial Orders), Counting, and Probability. If any of those words gave you a giddy feeling, you should absolutely check out the OCW course here or the current course here. In fact, the entire textbook is online! The instructor in the OCW lecture videos is the famous Tom Leighton, who only teaches it every two years. The last time he taught it, Fall 2012, he earned a 6.8/7.0 teaching score in the end of term evaluations. Wow. I can see why the class is very entertaining and engaging.     In fact, I can prove it to you by sharing what we started off our third lecture with today. Behold: Top 10 Proof Techniques NOT Allowed in 6.042 10. Proof by throwing in the kitchen sink: The author writes down every theorem  or result known to mankind and then adds a few more just for good measure. When  questioned later, the author correctly observes that the proof contains all the key facts  needed to actually prove the result. Very popular strategy on 6.042 exams. Known to  result in extra credit with sufficient whining. 9. Proof by example: The author gives only the case n = 2 and suggests that it contains  most of the ideas of the general proof. 8. Proof by vigorous handwaving: A faculty favorite. Works well in any classroom or  seminar setting. 7. Proof by cumbersome notation: Best done with access to at least four alphabets and  special symbols. Helps to speak several foreign languages. 6. Proof by exhaustion: An issue or two of a journal devoted to your proof is useful.  Works well in combination with proof by throwing in the kitchen sink and proof by  cumbersome notation. 5. Proof by omission:  â€œThe reader may easily supply the details.” “The other 253 cases are analogous.” “” 4. Proof by picture: A more convincing form of proof by example. Combines well with proof by omission. 3. Proof by vehement assertion: It is useful to have some kind of authority in relation  to the audience. 2. Proof by appeal to intuition: Cloud-shaped drawings frequently help here. Can be  seen on 6.042 exams when there was not time to include a complete proof by throwing  in the kitchen sink. 1. Proof by reference to eminent authority:  â€œI saw Fermat in the elevator and he said he had a proof . . .” Here are some other common proof techniques that can be very useful, but which are not  recommended for this class. • Proof by intimidation: Can involve phrases such as: “Any moron knows that”  or “You know the Zorac Theorem of Hyperbolic Manifold Theory, right?” Sometimes  seen in 6.042 tutorials. • Proof by intimidation (alternate form): Consists of a single word: “Trivial.”  Often used by faculty who don’t know the proof. • Proof by reference to inaccessible literature: The author cites a simple corollary  of a theorem to be found in a privately circulated memoir of the Slovenian Philological  Society, 1883. It helps if the issue has not been translated. • Proof by semantic shift: Some standard but inconvenient de?nitions are changed  for the statement of the result. • Proof by cosmology: The negation of the proposition is unimaginable or meaning ­  less. Popular for proofs of the existence of God. • Proof by obfuscation: A long plotless sequence of true and/or meaningless syntac ­tically related statements. • Proof by wishful citation: The author cites the negation, converse, or generalization  of a theorem from the literature to support his claims. • Proof by funding: How could three di?erent government agencies be wrong? • Proof by personal communication:  â€œxn + yn = zn for n 2” [Fermat, personal communication]. • Proof by importance: A large body of useful consequences all follow from the  proposition in question. • Proof by accumulated evidence: Long and diligent search has not revealed a  counterexample. • Proof by mutual reference: In reference A, Theorem 5 is said to follow from The ­orem 3 in reference B, which is shown from Corollary 6.2 in reference C, which is an  easy consequence of Theorem 5 in reference A. • Proof by ghost reference: Nothing even remotely resembling the cited theorem  appears in the reference given. • Proof by forward reference: Reference is usually to a forthcoming paper of the  author, which is often not as forthcoming as the ?rst. • Proof by metaproof: A method is given to construct the desired proof. The cor ­rectness of the method is proved by any of the above techniques. The pdf of all this can be found here. This leads to the point that a lot of the parts of an MIT Education are available for free, online. It doesnt mean that the parts add up to the whole, but they sure do make something. There are people like Scott Young who earn the full MIT Computer Science education for free in only a year by dedicating themselves to online resources (reddit link, TEDx video, opinion). You can experience a lot about classes online, and I highly recommend it. But one thing you cant recreate is the in-class atmosphere: the feeling of classmates cheering on peers to solve a problem against the TAs, and the elation when said peers toss the winning candy out at the audience. Times like these, I feel like I Have Truly Found Paradise.