Proofs of Invalidity