Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Does constantly removing elements from a set produce the null set?

  1. Jun 3, 2013 #1
    If you keep removing elements from a nonempty set, will you eventually get the null set? Some context below in a problem which I made myself and have been trying to solve:

    A set S having property P is smallest with respect to property P if S is an improper subset of any set having property P.

    A set S having property P is minimal with respect to property P if any proper subset of S fails to have property P.

    I am trying to prove/disprove the following: Let M be the only minimal set having property P. Then M is smallest with respect to property P, i.e. any set having property P is an improper superset of M.

    My proof:
    If M is the only set having property P, then the conjecture is trivially true. Otherwise suppose, on the contrary, that there is some set M' having property P, but which fails to be a superset of M.

    Then since M' is not minimal, there exists a proper subset of M', namely M'', having property P. But M'' is also not a minimal set, so there exists a proper subset of M'', namely M''', having property P. This process can continue indefinitely, since M is not a subset of M'. By repeatedly removing elements from M, we should obtain that the null set also has property P. This contradicts the fact that M is minimal with respect to property P. Thus M' must be the smallest set having property P.

    It is the part in bold whose rigor I do not completely trust. What can I do to improve the rigor, or what is the flaw in my reasoning? This is the first "difficult" problem I have ever made so I want to make sure I solve it correctly. All help is appreciated. Thanks!

  2. jcsd
  3. Jun 3, 2013 #2


    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    For example if [itex] M = \mathbb{R}[/itex] and you start removing one integer at a time?

    I could be wrong but I suspect you're going to need to use the axiom of choice here
  4. Jun 4, 2013 #3
    No, the proof is invalid. The part in bold should indeed be made more rigorous (and I doubt you can do that). Furthermore, you never really used that the set M is the unique minimal set with the property.

    I would start thinking of a counterexample.
  5. Jun 4, 2013 #4
    Also I would consider what it means to say that M is the "only" minimal set with property P. To know this you would have to consider every set possible but the set of all sets does not exist.

    Edit: I guess you could prove that the empty set is the only set with P = "has no elements".
  6. Jun 4, 2013 #5
    1) Why is the proof invalid?
    2) I did use the fact that M is the unique minimal set, since that allowed me to conclude that M' was not minimal. If M were not the only unique minimal set, there could be the possibility that M' were a minimal set.
    3) Could you help me with a counterexample? My knowledge of set theory is very limited.

  7. Jun 4, 2013 #6
    Depends how many times you're allowed to keep removing them. If you're asking what happens in the limit as n increases without limit in the natural numbers to a sequence of sets: S1, S2, S3...Sn..., with Sn+1 a proper subset of Sn for each n, then the answer is `no, you do not always get the null set.'

    This is clear if your starting set's cardinality is greater than Aleph zero -- say the cardinality of the real numbers.

    But even if S1 contains a countable number of elements, you will not necessarily get the null set in the limit. For instance, let S1 be {1, 2, 3, 4...}; To get S2, remove 2 from S1. To get S3, remove 4 from S2. To get S3, remove 6 from S2. Etc. The limit set will be {1, 3, 5...}, not the null set.

    If you have in mind some transfinite continuation of the process of removing an element, then by allowing one to take away an element a number of times greater than the cardinality of the set, you will get the empty set. But there is still a problem with your argument.

    Even if it were true that, at each stage of the process, the removing of an element from set Sn with property P implied that Sn+1 also had property P, it would not follow that the set that the set that results from the limit of the process has property P.

    For instance, take the set S1 = {1, 2, 3, 4...}; Let S2 be {2, 3, 4...}; Let S3 be {3, 4, 5...}; let Sn be {n, n+1, n+2...}. In the limit of this process, we do get the null set, because each element n of S1 is removed at stage n+1. However, it is also true that each Sn has the property 'contains infinitely many elements'. But the limit set, the null set, does not contain infinitely many elements.

    The following appears to me to be a counterexample to your hypothesis*:
    Consider two sets: A, the set of positive integers; B, the set of negative integers.

    Let P be defined in the following way: a set S possesses P iff S is either identical to A, *or* S is not identical to A and S contains an infinite subset of B.

    Clearly, A is a minimal set that possesses P. Is it uniquely minimal? Yes: For if S possesses P and is not identical to A, then by the definition of P, S must be an infinite subset of B; But any infinite subset of B itself contains another infinite subset of B; so S is not minimal.

    But A is not a smallest possessor of P. For B possesses P, but B does not contain A.

    *I didn't entirely understand all your uses of `improper' -- in particular your talk of improper subsets -- wouldn't an improper subset of A just be A?
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook