(adsbygoogle = window.adsbygoogle || []).push({}); "smallest set" proofs

From time to time I've seen proofs (to disprove some assertion) which are based on claiming that if the assertion P holds for some sets, there must be some set S which is the smallest set for which P holds, and then showing that if P holds for a set of size |n| it must hold for a set of size |n-1| thus contradicting the assumption that S is the smallest such set. (Or something along those lines.)

Unfortunately I can't seem to find one now, and even if I could, I'm not quite sure what is needed to make such a proof valid.

Would someone please point me to a valid example of this sort of proof, or better yet, an explanation as to how to construct one. In particular, what is needed to make a statement like "there must be a smallest set ... let S be that smallest set" a valid basis for proof by contradiction.

**Physics Forums - The Fusion of Science and Community**

# Smallest set proofs

Know someone interested in this topic? Share a link to this question via email,
Google+,
Twitter, or
Facebook

Have something to add?

- Similar discussions for: Smallest set proofs

Loading...

**Physics Forums - The Fusion of Science and Community**