(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**

Join Physics Forums Today!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

# Smallest set proofs

Loading...

Similar Threads for Smallest proofs | Date |
---|---|

I An easy proof of Gödel's first incompleteness theorem? | Mar 6, 2018 |

B Least / Smallest / Minimum Detectable Difference | Jan 21, 2018 |

Largest and smallest possible values of a probability question | Feb 20, 2015 |

Smallest Sigma-algebra (and algebra) | Mar 29, 2009 |

Closure of A is the smallest closed set containing A | Jan 4, 2008 |

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