- #1
gnome
- 1,041
- 1
"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.
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.