As long as you can clearly define your starting axioms you can mathematically prove or disprove anything. The physical example would be to just say, suppose a universe with the same properties of ours exist but where the gravitational constant is twice as large prove whether X can occur in that universe.

As far as how randomness is defined I believe that might be field dependent but this is me getting out of my depth (I've only taken a few courses on combinatorics).

Randomness is usually defined in terms of a probability distribution, which is just a measure where the total mass assigned to all elements adds up to 1.

You can actually only prove unreal things because you impose limitations. Real things can not be proven, but only disproved.