What explains the Inventor’s Paradox? Why can more general problems, paradoxically, be easier to solve or prove?
Whenever I teach
many students raise their hand, and asks for the reasons behind the Inventor’s Paradox. Most students reasonably reckon that a broader problem is knottier, thornier than a more specific, narrower problem – multivariable calculus is broader, thornier than single variable calculus, abstract algebra broader, more complex than linear algebra that’s broader, more esoteric than high school algebra.
These lists beneath just instantiate problems that become more easily solvable when generalized, but none of them explain why.
Particular problem solved by solving a more general problem
Generalizing a problem to make it easier
When was the generalization easier to prove than the specific case?
Examples where adding complexity made a problem simpler
1 answer
There are many reasons why generalizing a problem can make finding a solution simpler. Of course, this is just a heuristic. Generalizing a problem can easily make it much harder or even impossible to find a solution.
Here are several reasons why this is the case in decreasing order of objectivity.
First, and I feel this is often overlooked, the process of constructing a proof is a process of searching the space of proofs and generalizing restricts the moves that are available to you. This both shrinks the total search space and makes it less likely you'll make a move that leads to a dead end. Of course, the risk is that you'll remove a move that could have gotten to the answer quicker.
Second, generalizing tends to abstract and remove details. Ideally, these details are unimportant. This makes it easier to keep all the relevant parts in your head at once. Even when the details do matter, this often helps split the proof into a part that is generally true for abstract reasons and a part that depends on the details. This is just good proof design generally as this, among other techniques, is what is necessary to scale up to larger proofs.
Third, more general problems often suggests bringing different tools to bear. If I turn a 2-dimensional problem into an $n$-dimensional problem, I'm very likely to be forced to turn to matrix notation and general linear algebraic concepts. This might emphasize certain properties of the matrices and suggest relevant linear algebra theorems. It is also often easier to see a pattern than a fact divorced from context.
Fourth, the exercise of formulating a more general statement is often not trivial and requires careful thought about the problem which is, by itself, often useful. This often leads to reformulations and/or changes of perspective that often simplify even the original problem statement. For example, this CS.SE question asks for an intuitive proof of the statement "any binary tree with $n$ nodes has $n-1$ edges". The homotopical perspective I take in my answer, which one might be motivated to take when asking about not necessarily binary trees or graphs in general, rephrases this problem as "any binary tree has Euler characteristic $1$".
0 comment threads
0 comment threads