1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Set which contains all of it's subsets

  1. Feb 1, 2012 #1
    1. The problem statement, all variables and given/known data
    Prove a set which contains all of it's subsets doesn't exist.

    3. The attempt at a solution
    Suppose such a set P exists. P := {x | x [itex]\in[/itex] [itex]\wp[/itex](x)}.
    P [itex]\in[/itex] [itex]\wp[/itex](x), so P [itex]\in[/itex] P.
    This seems like a paradox to me, so all I have to prove is that a set can't contain itself. But how? I've got a gut feeling it's closely related with Russels paradox, but I can't get it.
     
  2. jcsd
  3. Feb 1, 2012 #2
    Have you proven that the power set of a set is always strictly larger?

    There's no need to get involved with fundamental things like Russell's paradox. This is more basic.
     
  4. Feb 1, 2012 #3
    Yes I've proven that there doesn't exist a surjection f: S [itex]\rightarrow[/itex] [itex]\wp[/itex](S), but there exists an injection.
     
  5. Feb 1, 2012 #4
    Say X is the set in your problem, the one that contains all its subsets.

    How do X and its power set relate in this case?
     
  6. Feb 1, 2012 #5

    Fredrik

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    I don't know if the axioms rule out the possibility of a set that is a member of itself. I'm guessing that they don't.

    I would avoid constructions of the form {x|x has property P}, because that's what's gets us into trouble in the case of Russell's paradox. The axiom schema of comprehension says that {x∈A|x has property P} is allowed when A is a set, but not that {x|x has property P} is allowed. So I would start in a different way, specifically with the sentence "Suppose that there's a set A such that ##x\subset A\Rightarrow x\in A##.", and then try to derive a contradiction from that.

    Hint: Cardinality. (I think that's a good hint, but I haven't made absolutely sure that my idea works).
     
  7. Feb 1, 2012 #6
    X would be it's power set, and thus there would be a bijection between them. However I've proven there doesn't exist a bijection. In other words, X and it's power set have the same cardinality (if X exists), but i've proven the power set is bigger than X, so there is a contradiction and thus X doesn't exist.

    Is this correct?
     
  8. Feb 1, 2012 #7
    Yes :) but as you don't seem to be sure of yourself, let me say it more succinctly: there is no surjective function from X to its power set, which there would be if X equaled its power set.
     
  9. Feb 1, 2012 #8

    Deveno

    User Avatar
    Science Advisor

    yes, they do. this is a consequnce of the axiom of regularity, and the axiom of pairing:

    let A be a set. then {A,A} = {A} is a set, by the axiom of pairing.

    by the axiom of regularity, {A} contains an element B such that {A} and B are disjoint. but the only element of {A} is A. therefore, A and {A} are disjoint.

    since A is in {A}, A cannot be in A (by the definition of "disjoint").

    (if a set could be a member of itself, we could form "the set of all sets", which is a problemmatic construction, and quite similar to, but not quite the same as, Russell's paradox).
     
  10. Feb 1, 2012 #9

    Fredrik

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    Thanks, that proof was very clear. I've been wondering about this.

    I don't see how this implication is true. Because of your proof, it's clear that we can't introduce a set that's a member of itself without first dropping (or weakening) some of the ZF axioms, so suppose that we drop enough of them to make your proof invalid, and then add an axiom that says "there's an A such that A∈A". Does this really imply that there's a set that contains all sets?
     
  11. Feb 1, 2012 #10

    micromass

    User Avatar
    Staff Emeritus
    Science Advisor
    Education Advisor
    2016 Award

    ZF with the axiom of regularity is just as consistent as ZF without the axiom. So the axiom of regularity is not the one that prevents problematic constructions. Rather, it is the limited comprehension scheme that prevents a set of all sets, not the regularity axiom.

    Furthermore, not all people consider the axiom of regularity as a basic axiom.
     
  12. Feb 2, 2012 #11

    Deveno

    User Avatar
    Science Advisor

    yes, many people see regularity as a "useless axiom" (and some people don't even include it, choosing to use the axiom of infinity instead).

    and, regularity does not "solve" Russell's paradox. what regularity says is:

    all sets are "well-founded". that is, no set is "infinitely recursively defined in terms of smaller sets". every set "starts somewhere". now there are some good reasons for considering "non-well-founded" set theories (just as the natural numbers are (often) defined impredicatively, but this doesn't really lead to any problems), merging data streams is a good example.

    you and Fredrik are correct, however, the "absence of regularity" doesn't imply that there is a "set of all sets". i don't know what i was thinking...probably something along the lines of:

    if A∈A is allowable, then for all subsets of the class V of all sets, we could have V∈V...but that doesn't even make sense in NGB, because a∈b is undefined if a is not a set.

    *****

    however, just because two theories are "equi-consistent" is not, in itself, a reason to favor one or the other. ZFC+CH is equi-consistent with ZFC+(¬CH), which leads one to wonder...should we think of the CH as true, untrue, or both/neither? moreover, sometimes a "minimal axiom system" is less useful than a redundant one: classical logic can be reduced entirely to "nands" or "nors", but doing so obscures the ways we think and speak about things we feel are true (although logical circuits don't seem to mind...).
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook