Techniques that prove there is no method or no proof

Question

I want to learn about proving undecidability and proving that there is no algorithm. I read that Alonzo Church proved that there is no algorithm for second-order predicate logic while there is an algorithm for first-order logic. I don't understand how. I wonder if there could be a method or technique that proves that there is no method and no technique or if the proof was more similar to proving a mathematical impossibility or a false hypothesis.

There were also proofs that there is algorithm to solve 4th degree polynomials and then there was a proof that it stops at 5th degree polynomials and that there is no method for higher order equations.

I wonder if the proof techniques in these cases, where you prove that there is no method, is different or more the same as proving a classical true or false hypothesis or statement?

I understand that in general there are two methods, you either find a counterexample (proof by contradiction) or you try to find a proof that covers all possible cases (induction).

It is also sometime possible to reduce a problem to another that we know in undecidable e.g. reduce the problem to the halting problem and then we know that it is undecidable.

Answer 1

One very common type of these "proofs of impossibility" is showing that the set of objects that you want to handle with your method is strictly larger than the set of objects you can handle (see the polynomials of degree $5$ comment above), so there's obviously at least one object that you'd want to handle but that you don't.

A useful technique for these "too big too handle" impossibility proofs is called diagonalization (this is how you produce proofs for the halting problem and various undecidability problems), and it's essentially the same type of proof by which you show that the set of real numbers has cardinality strictly larger than that of the naturals:

1. you imagine an arbitrary order of all the objects you can handle and
2. you show that there is one object you'd want to handle that differs from the first object you can handle in its first "point", from the second in the second "point", and so on (hence the name diagonalization, the difference points form a "diagonal")... so this object you'd want to handle has no place among those you can handle.

Another type of "impossibility proof" technique is called relativization, and, in a nutshell, disqualifies all methods that would remain correct regardless of whether a specific fact is true or false; and it does so by showing that the result you want to find necessarily changes based on the truth or falsity of that specific fact.

Ultimately, these techniques are many and varied, and they do not follow all a common theme. Each is a precious finding on its own!