I like to think that what the “can’t prove a negative” phrase originated from was someone grasping at the difference between Pi_1 and Sigma_1 statements . For a Pi_1 statement, one needs only a single counterexample to refute it, but to verify it by considering individual cases, one has to consider all of them and show that they all work (which, if there are infinitely many, it is impossible to handle them all individually, and if there are just a lot, it may still be infeasible) . Conversely, for a Sigma_1 statement, a single example is sufficient to verify the claim, but refuting it by checking individual cases would require checking every case.