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

A Paradox ?

  1. Jan 23, 2008 #1
    A Paradox ???

    Consider the following set - ( P(Y) denotes the power set of Y) :

    U = { X | There exists a set Y such that X = P(Y)
    Clearly , U exists :) & is non-empty. Hence, P(U) belongs to U (by the very definition of U).
    This contradicts the result by Cantor that the power set always has a higher cardinality than the set - P(U) is a proper subset of U & its cardinality can't exceed that of U.
    Is there a flaw in the above argument ? ( I earnestly hope there is !!!).
    The above U is not the only set that has this infernal property
    - there are others ( consider, for instance, G ={A | A is a set}. P(G) belongs to G.).
  2. jcsd
  3. Jan 23, 2008 #2


    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    How is that clear?

    Incidentally, what set theory are you using?
  4. Jan 23, 2008 #3


    User Avatar

    Even if U did exist, it isn't a set. Also this doesn't contradict Cantor's result because, even if it existed, you just showed that P(U) an element of U, not a proper subset.
    How about X ={Y: Y is not an element of Y}. Then, is X an element of X :)
  5. Jan 24, 2008 #4
    U is the set of all power sets in the world - it contains, for instance, P(R) (where R is the set of real numbers) ,P(P(R)) &c.
    U contains elements other than P(U) - P(R),P(The set of all continuous functions) to mention some of the innumerable possibilities.This makes P(U) a proper subset.
    ( Even if P(U) were not a proper subset of U i.e., U =P(U), this is not in keeping with Cantor's result).

    May I know if the definition of U is legetimate under some of the standard set theories ? That's the very qualm I had.
  6. Jan 24, 2008 #5


    User Avatar

    Is OP taking of the power set of the universal set of power sets!
    Obviously then, it is some thing of circular logic. Which may not be used for authentic proof.
    Last edited: Jan 24, 2008
  7. Jan 24, 2008 #6
    Let X = { P(X) } then
    P(X) = {0 , P(X)}
    |X| = 1
    |P(X)| = 2 in agreement with Cantors thereom.
    Then either by induction or otherwise you can extend this to any set containing it power set, because that set will only contain its power set as an element.
  8. Jan 24, 2008 #7


    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    I'm only familiar with Zermelo set theory (and some additions and variants). Its method for avoiding the paradoxes of 'naïve set theory' is restricted comprehension, as well as a few other basic operations to one started.

    In Zermelo set theory, set-builder notation is only allowed for selecting a subset of an existing set:

    [tex]\{ x \in A \mid \Phi(x) \}[/tex]

    Zermelo-Fraenkel set theory also allows replacement:

    [tex]\{ f(x) \mid x \in A \}[/tex]

    In von Neumann–Bernays–Gödel set theory, you are allowed to use unrestricted comprehension to define a class:

    [tex]\{x \mid \Phi(x) \}[/tex]

    but you have no guarantee that such an class is actually a set.
    Last edited: Jan 24, 2008
  9. Jan 25, 2008 #8
    So, is U a class according to Neumann–Bernays–Gödel set theory ?
    I reckon it is.
    How about G={ X | X is a set } ? Does it fit in with the Zermelo-Fraenkel set theory?
    Here ,too, P(G) belongs to G & also, every element of P(G) belongs to G. Unlike with U , we have obvious injections from P(G) to G & vice verca. This is incompatible with Cantor's result since the Cantor-Schroder-Bernstein lets us find a bijection using the two injections.
    I am, with great respect,
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook