Conservation of energy in large systems can be proved reductively, from the properties of the subsystems.

Similarly, most true facts about decision problems can be proved from a model of what kind of structures can be decision problems.

It then becomes an empirical question whether other kinds of substructures or decision problems exist.

EDIT: Suppose you get in a conversation with a Cunning Philosopher. He comes up with a clever philosophical example designed to expose a flaw in your theory. You point out that the example doesn't work, there is some problem in it. He comes up with another example, dealing with that problem. You point out that .......

Why should you expect this process to terminate with him running out of ideas?

Now suppose you get in a conversation with the Cunning Perpetual Motion Machine Crank. He comes up with a clever machine designed to violate conservation of energy. You know, because of a proof, that he must be calculating as though one of the parts doesn't work the way physics said it does. You only need to find this part. There is no way for him to win - except by empirically proving one of the assumptions in the proof invalid.