How can a math problem be unsolvable?
In: Mathematics
The object the problem ask you to find doesn’t exist. Generally only applies when the form of solutions you’re looking for is so general that it seems like it should exist.
That, in the most general sense, cover pretty much most sense of “unsolvable” problem. It includes:
– A solution doesn’t exist.
– An algorithm doesn’t exist.
– A proof doesn’t exist.
———————
First, let me explain how it is conceivable that there are unsolvable problems.
As a very basic example, imagine someone ask you to solve n^2 =3 where n is an integer. It’s easy to check that there are no solutions, so you just say there are no solutions.
What if the problem is slightly harder. Maybe they ask for rational n instead? Or maybe they ask for n being Gaussian rational? In each case, the question become harder and harder but you can eventually show that there are no solutions. All you need to do is to write down the form of n (say n=p/q or n=p/q+ir/s for p,q,r,s integers), then check the equations in these variables, and finally confirm that these equations have no solutions.
But now let’s up the difficulty. Supposed you’re asked to find a solution to x^5 -x+1=0 that can be written using rational numbers, arithmetic operations, and radical. What now?
It takes a lot more work, but it can eventually be solved that once again there are no solutions. That is, if you write down any numbers using rational numbers, arithmetic operations, and radical, then plug it in to x, you won’t get equality. But at this point, people generally said that the equation can’t be solved, unsolvable. Instead of saying it has no solutions. Why? Because the conditions “rational numbers, arithmetic operations, and radical” permits you to write out numbers with limitless complexity so people expected there to be a solution, so the fact that there is none put a damper to an entire approach. It’s hard to imagine how such a number even look like, much less how to prove none of them solve the equation, but the fact that x^5 -x+1=0 has no such solutions is as certain as certain n^2 =3 has no integer solutions. As an analogy, imagine you’re a bishop in chess standing on a black tile, you can make a lot of moves in very complicated manner, but no matter what you do you will never stand on a white tile.
But that isn’t the only type of solutions out there. Another well-known example is straightedge and compass construction. Once again, certain construction problem will ask for a construction procedure to produce a specific figure. The definition of a “construction procedure” also permit you to write very complicated procedure that it’s a bit unexpected when it turns out no matter how complicated they can be there are figure they can’t construct. Which is why those problems are also considered to be unsolvable.
Now, moving on to modern time. An “algorithm” is basically some program that can be programmed on a computer and always stop. Just a more complicated version of a construction procedure. And of course, certain problem ask for an algorithm: the problem want an algorithm such that for any input I the algorithm produce output O such that O satisfies some specific condition related to I. And once again, that endless potential complexity doesn’t mean there are problem they can’t solve. For certain problems, no matter what algorithm you try, it will always produce the wrong O, one that doesn’t satisfy the condition.
Now let’s go even more meta. Most math problem is basically a statement, and the problem is produce a proof that the statement is true, or the statement is false. But at a meta level, a proof is also an object with very specific form. A proof is just a string of logical symbol, arranged in a way that satisfy logical rule, start with a list of axioms, and end with the statement you want to prove. Proof can be extremely complicated, sure, but it still have limitation. Sometimes, it just so happen that there are no strings of logical symbols arranged according to logical rule that start at a list of axioms can end at either the statement nor its negation.
——————–
Second, let me explain how one can prove there are no solutions/problem is unsolvable.
For the simple example I provided at the beginning, it’s a matter of writing out the form of the solution, plug in and check. That seems easy enough.
For solving x^5 -x+1=0, what you need is an invariant. The bishop analogy is really good here. The color of the tile of the bishop is an invariant, something that can’t be change with a move. This is why, no matter how complicated the bishop move, it never changes its tile color, and so you can prove that there are tiles the bishop can’t move to. Similarly, here, you can show that there is an invariant associated with a number that can’t change by taking roots or doing arithmetic operations. That way, no matter what complicated number you get, this invariant holds. And solutions to x^5 -x+1=0 doesn’t satisfy this invariant.
The same method also works on straightedge and compass construction. If you want to look into it, it’s Galois group.
Next, we go to algorithm. As we allow our solution to have even more complexity, things get even more difficult, and the invariant method don’t work. In fact, we know very little about what algorithm are capable of, but luckily enough, this very fact allow us to know certain limitation of algorithm, by allowing an algorithm to defeat itself! Imagine yourself in the shoe of an oracle from Delta. If you tell some guy that he will fall into a river and die, he will just not come near a river, defeating your prophecy. Back to algorithm, this reason is why predicting what an algorithm do is difficult, but it’s also why there are no algorithms to predict what other algorithm do.
Next, onto proof. Proof is just as terrible as algorithm. They can potentially be too complicated for us to understand. In fact, this is why we never fully know if a proof doesn’t exist, instead we settle for “equiconsistency”, the idea that if we assume certain proof doesn’t exist, then some other proof can’t either.
Latest Answers