Structural induction... with cake

comicsfoodinfographicslogicmathresourcesstructural-inductionprogramming

How do I prove that all slices of cake are tasty using structural induction? Step 1. Define a set of cake slices recursively. X is cake. If X and Y are both cake, then both of them put together is still cake. Step 2. Prove that a single piece of cake is tasty. (Person, with cake crumbs all over their face: OH GOD! THIS IS THE BEST THING I'VE EVER EATEN!) Step 3. Use the recursive definition of the set to prove that all slices are tasty. (Person, still with cake crumbs on their face: By definition, two slices of cake put together is still cake. THEN THESE LARGER PIECES MUST ALSO BE TASTY!) Step 4: Conclude that all slices of cake are tasty. (Person, rejoicing: LET'S HAVE CAKE!)

Structural induction is a way of proving something is true, for everything in a set. You can use it to prove mathematical equations, things about Fibonacci numbers, or the efficiency of programs. That’s all fine and dandy, but I’d much rather prove how tasty cake is for now.

Fetching comments...