Hierarchical Understanding of Proofs

Abstract – You know the student… comes by your office… says he or she understands everything you say but doesn’t seem able to do the homework or exams. What to do? At least one problem is that the proof (definition, algorithm) explained in class is just one of many levels in a kind of (proof) triangle. That rough triangle/hierarchy contains the merest hint of a proof at its apex, a strategy some level below that, an informal proof at midlevel, and a formal proof at the base. As teachers, we don’t supply the whole hierarchy (it would be boring) and indeed we shouldn’t (the hint that works for me may not work for you). It is the students’ obligation to create that hierarchy, to ask themselves how they should have been thinking to arrive at that (or a comparable) proof. This talk will give a detailed example of a proof hierarchy, and other less detailed examples as well. It will quote eminent computer scientists and mathematicians Robert Floyd, Leslie Lamport (author of Latex), and Terence Tao (Fields Medalist). Suggested hints for the apex of a triangle can be found in Georg Polya’s “mathematics and Plausible Reasoning” (Volume I).

In this talk, I argue that triangles can serve as templates for constructing proofs. Virtually all proofs, even very creative ones, are constructed through the use of templates. Furthermore, one can measure student understanding of a proof by the hierarchy each one creates, as some hierarchies are more useful (for proving different theorems) than others. A time-honored method for measuring student understanding of a proof is to change the theorem (or requirements) slightly and then see how well the student does in constructing a proof (or algorithm) for the modified problem. [Joint work with Dafna Shahaf and Ryan Williams]

Biography – Manuel Blum is a leader in the world of theoretical computing. He is one of the founders of computational complexity theory, work that has also had applications to cryptography and program checking. Among his many awards are the A.M. Turing Award, the highest honor in computing, and election to the National Academy of Sciences.