Mathematics for Computer Science – “Top 10 Proof Techniques NOT Allowed” by Anastassia B. '16
6.042 has been a very engaging and entertaining class thus far.
After going through a quarter-life-crisis and switching a lot about my approach to MIT (more on that later), I’ve finally figured out my classes for junior fall. One of the classes I’m in this semester is 6.042, or in regular-speak: “Mathematics for Computer Science”.
It. Is. SUPER.
Actually, I didn’t 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 wasn’t stellar at it anymore, probably because I didn’t 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 definitions 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 syntactically 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 different 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 Theorem 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 first.
• Proof by metaproof: A method is given to construct the desired proof. The correctness 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 doesn’t 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 can’t recreate is the in-class atmosphere: the feeling of classmates cheering on peers to solve a problem against the TA’s, 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.