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

On P(X) > X

  1. Oct 26, 2003 #1
    An edited version:

    General:

    We say that B > A if A not= B but there is an injection between A and subset of B .


    Theorem: P(X) > X

    Proof:


    Step 1 (injection between set A and subset of set B ):

    Let us define injection between each member of X to each member of P(X), which includes a singleton as its content.

    We define f(x) where f(x)={x}, for example: 1 <--> {1} , 2 <--> {2} , 3 <--> {3},… and so on.

    At this stage we can say that P(X) >= X .


    Step 2:

    Suppose there exists a bijection between P(X) and X .

    We will show that this assumption leads us to contradiction.

    There exists member S in P(X) which includes ALL members of X that have no image Included in the P(X) members which they are mapped with, for example:

    1 <--> {2,3} , 2 <--> {2,3,4} , 3 <-->{6,7} , 4 <--> {4,5,6} , 5 <--> {8,9}, …

    In this example S ={1,3,5,…}.

    -----------------------------------------------------------------------------
    A proof that a non empty member S exists:

    2^0=P({})={ {} }=1
    2^1=P({0})={ {},{0} }=2
    2^2=P({0,1})={ {},{0},{1},{0,1} }=4
    2^3=P({0,1,2})={ {},{0},{1},{2},{0,1},{0,2},{1,2},{0,1,2} }=8
    ...

    Therefore {} not in N but {} in P(N)

    N members are the natural numbers.

    P(N) members are the empty set + subsets of N + N itself.

    It is easy to show an injection between any n of N to any singleton member {n} of P(N).

    When we define this injection than P(|N|)>=|N|.

    If P(|N|)=|N| then D is the member in P(N) includes the members of
    N, that have no image in the member of P(N), which they are mapped with.

    n in D because {} not in N, therefore D is not empty.

    Q.E.D

    t=n
    X=N
    S=D

    -----------------------------------------------------------------------------


    Now, let us say that there exist some member in X (let us call it t ) which is mapped with S (t <--> S ).

    In this case we can ask: is t in S or t not in S ?

    Options:

    1) t in S , but by S definition t cannot be in S .
    2) t not in S , in this case by S definition, t must be in S , but by (1) t can’t be in S .

    and so on, and so on.

    As we can see, both options lead us to logical contradiction.

    Therefore, there cannot be a bijection between P(X) and X and we can conclude that P(X) > S .

    Q.E.D

    =================================================
    =================================================

    Let us look at this proof from another point of view.

    As we all know, any set includes only unique members or no members at all.

    Now, let us examine options 1 and 2 again.

    Option 1:

    All the members which included in S , are different from each other.

    Any member of X can be mapped with some member of P(X), once and only once.

    Therefore t is different from each member in S , therefore t MUST BE INCLUDED in S .

    Therefore S cannot be defined BEFORE we check our assumption in step 2 of Cantor's proof.

    Option 2:

    If we want to keep S as an existing member, we MUST NOT INCLUDE t in S .

    In this case we also find that S cannot be defined BEFORE we check our assumption in step 2 of Cantor's proof.


    Therefore we cannot ask nor answer to anything that is connected to member S .


    The general idea behind this point of view is the power of existence of member t and member S .

    Member t is simpler than member S .

    Member S existence depends on objects like t , therefore we have to check S by t as we did here, and not t by S as Cantor did.


    Organic
     
    Last edited: Oct 30, 2003
  2. jcsd
  3. Oct 26, 2003 #2

    HallsofIvy

    User Avatar
    Staff Emeritus
    Science Advisor

    No, that's exactly backwards but I imagine it was a typo. A is larger than B is there is a bijection between B and a subset of A. And it is the same as saying "the cardinality of A is greater than or equal to the cardinality of B".

    Actually, your proof uses a different statement which may be what you intended to say: A> B is A not= B AND there is NOT a bijection between A and a subset of B.

    Why should we say that? Do you have any reason to believe that such a subset does exist? If there doesn't exist such a set your proof fails. You need to prove that set's existence, not just "say" it.
     
  4. Oct 26, 2003 #3
    tricks of the trade

    P(X)>X is equivalent to saying there is no function that maps X onto P(X).

    we will show that every function which maps X to P(X) is not onto. let f be any function mapping X to P(X). consider the set
    D:={x in X such that x is not an element of f(x)}.

    (D is for diagonal as in the diagonal argument. note that D is a subset of X and is therefore an element of P(X).)

    D is not in the image of f because if it was, then we could say that
    f(y)=D for some y in X which would imply that y is an element of
    f(y) if and only if y is not an element of f(y).

    since D is not in the image of f, f is not onto. since f was arbitrary, this shows that no function from X to P(X) is onto.
     
  5. Oct 27, 2003 #4
    Hi phoenixthoth,

    Thank you for your correction.

    I wrote:
    It is my mistake, and it has to be:

    I have a simple question:


    The power of aleph0 is 2^aleph0, so if we construct a list of X subsets, then
    by Cantor's diagonal second argument we can find maps between only aleph0 X
    members and aleph0 X subsets, and always there is some subset (the diagonal subset) which is out of the map range.

    Is this the idea that stands behind the proof that P(X) > X ?




    Organic
     
    Last edited: Oct 27, 2003
  6. Oct 27, 2003 #5
    yes. D is always out of the range of any function from X to P(X).

    if you look at random examples of X's and P(X)'s and D's and maps f from X to P(X), you can see what D is in particular to see what the example f misses.

    example. of course, the proposition is clear for finite sets, but let's say X={1,2}. then P(X)={Ø,{1},{2},X}. let f be defined so that f(1)=Ø and f(2)={1}. as you can see, f is not onto P(X) since {2} and X are out of the range but let's see what D would be in this case.
    D:={x in X such that x is not an element of f(x)}. one by one, lets go through elements in X and see if x is not an element of f(x). if so, then x is an element of D. let's start with 1. is 1 not an element of f(1)? yes, since 1 is not an element of Ø=f(1). then 1 is an element of D. is 2 not an element of f(2)? yes, since 2 is not an element of {1}=f(2); so 2 is an element of D. in this case, D=X. and, as we know, X is not in the range of f. but this was automatic from the beginning.

    perhaps this is like fitting a carpet into a room where if we just fix the problem, fit the carpet in one corner, then it will fit the room. alas, no, if we pull the carpet to this corner by making sure X is in the range of f, the carpet will pull out of another corner.

    let's say f(1)=Ø and now that f(2)=X. maybe this will fix things since now that X is in the range of f. lets see what D is. i can guarantee you that it will either be {1} or {2} because neither of those are in the range of our new f even though X is. is 1 not an element of f(1)? yes, because 1 is not an element of Ø=f(1); so 1 is in D. is 2 not an element of f(2)? no, because 2 is an element of X=f(2); so 2 is not an element of D. therefore, D={1}. D is not in the range of f.

    the carpet will not fit the room no matter which corner we force it to fit in. whenever we fit it into one corner, it will always come up in another corner.

    an example with infinite sets? ok. let X=R and P(X) is the power set of R. define f to be the following function:
    for x in R, f(x)=(-infinity, x].
    this f is an injection from X into P(X). as you can already see, f is hopelessly not onto. but let's see if we can get a handle on what is automatically out of the range of f, ie, what D is. let's follow our noses. x is an element of D if and only if x is not an element of f(x); therefore, x is an element of D if and only if x is not an element of (-infinity, x]. but wait, x is an element of (-infinity,x]; therefore, D is the empty set. and as you can see from the definition of f, Ø=D is not in the range of f.

    here's an amusing exercise: let A and B be sets. prove there is no function from A onto B if and only if there is a bijection between A and a proper subset of B. (B is the only nonproper subset of B.) thus, either definition will suffice to mean A<B. i hope that's right...
     
    Last edited: Oct 27, 2003
  7. Oct 28, 2003 #6
    Hi phoenixthoth,

    You wrote:
    I will try to write it in a short way, please tell me if I do it right, thank you:

    x in X such as f(x)=(-[oo],x]

    x in D iff x not in (-[oo],x] --> D={}

    D not in (-[oo],x] therefore D is out of the range of f.


    Organic
     
  8. Oct 28, 2003 #7
    since D = Ø != (-oo,x] = f(x) for any x, D is not in the range of f.
     
  9. Oct 28, 2003 #8
    Sorry I can't follow it.

    Can you please write it again in simple english?

    Thank you.
     
  10. Oct 28, 2003 #9
    for x in R, f(x):={z in R : z <= x}.

    in other words, f(x)=(-oo,x].

    D={x in R such that x is not an element of f(x)}.

    f(x)={z in R : z <= x}, so this means that

    D={x in R such that x is not an element of {z in R : z <= x}}.

    note that for all x in R, x *is* an element of {z in R : z <= x}.

    therefore, the set of x in R such that x is *not* an element of
    {z in R : z <= x} is empty.

    since D is the set of x in R such that x is not an element of
    {z in R : z <= x}, D=Ø.

    in the argument i wrote about in "tricks of the trade," D is an element of P(X) automatically not in the range of any function from X to P(X). this last bit was an investigation into what various versions of D are for particular cases. in the last example, D=Ø and so Ø is not in the range of f. another way to say that is that for no x in R is the set {z in R : z <= x} empty. {z in R : z <= x}=f(x), so this is saying that f(x) != Ø for any x in R which means that Ø is not in the range of f. the central argument gives us a set, D, which is automatically not in the range of f and we can see what D looks like in this case; D=Ø.

    triva question: true or false? if m and n are positive integers and A is any infinite set, then the set of funtions from A to a set of m elements is in 1-1 correspondance with the set of functions from A to a set of n elements; i.e., m^A = n^A.
     
  11. Oct 28, 2003 #10
    phoenixthoth,phoenixthoth,

    Please hold your horses.

    I'll give a number to each line that is written below.
    Please just answer by yes(if ok) or no(if not ok) to each line.
    And if your answer is no, then please explain it in a simple and not formal way. Thank you.

    1) x in X such as f(x)=(-[oo],x]

    2) x in D iff x not in (-[oo],x] --> D={}

    3) D not in (-[oo],x] therefore D is not in the range of f.


    Organic
     
  12. Oct 28, 2003 #11
    i'm not sure what "such as" means. for x in R, f(x) is defined to equal (-oo,x].

    yes since x *is* in (-oo,x] for all x in R.

    no. D != (-oo,x] (for all x in R) therefore D is not in the range of f. in other words, D != f(x) (for all x in R) therefore D is not in the range of f.
     
  13. Oct 29, 2003 #12
    An edited version:


    General:

    We say that B > A if A not= B but there is an injection between A and subset of B .


    Theorem: P(X) > X

    Proof:


    Step 1 (injection between set A and subset of set B ):

    Let us define injection between each member of X to each member of P(X), which includes a singleton as its content.

    We define f(x) where f(x)={x}, for example: 1 <--> {1} , 2 <--> {2} , 3 <--> {3},… and so on.

    At this stage we can say that P(X) >= X .


    Step 2:

    Suppose there exists a bijection between P(X) and X .

    We will show that this assumption leads us to contradiction.

    There exists member S in P(X) which includes ALL members of X that have no image Included in the P(X) members which they are mapped with, for example:

    1 <--> {2,3} , 2 <--> {2,3,4} , 3 <-->{6,7} , 4 <--> {4,5,6} , 5 <--> {8,9}, …

    In this example S ={1,3,5,…}.

    -----------------------------------------------------------------------------
    A proof that a non empty member S exists:

    2^0=P({})={ {} }=1
    2^1=P({0})={ {},{0} }=2
    2^2=P({0,1})={ {},{0},{1},{0,1} }=4
    2^3=P({0,1,2})={ {},{0},{1},{2},{0,1},{0,2},{1,2},{0,1,2} }=8
    ...

    Therefore {} not in N but {} in P(N)

    N members are the natural numbers.

    P(N) members are the empty set + subsets of N + N itself.

    It is easy to show an injection between any n of N to any singleton member {n} of P(N).

    When we define this injection than P(|N|)>=|N|.

    If P(|N|)=|N| then D is the member in P(N) includes the members of
    N, that have no image in the member of P(N), which they are mapped with.

    n in D because {} not in N, therefore D is not empty.

    Q.E.D

    t=n
    X=N
    S=D

    -----------------------------------------------------------------------------


    Now, let us say that there exist some member in X (let us call it t ) which is mapped with S (t <--> S ).

    In this case we can ask: is t in S or t not in S ?

    Options:

    1) t in S , but by S definition t cannot be in S .
    2) t not in S , in this case by S definition, t must be in S , but by (1) t can’t be in S .

    and so on, and so on.

    As we can see, both options lead us to logical contradiction.

    Therefore, there cannot be a bijection between P(X) and X and we can conclude that P(X) > S .

    Q.E.D

    =================================================
    =================================================

    Let us look at this proof from another point of view.

    As we all know, any set includes only unique members or no members at all.

    Now, let us examine options 1 and 2 again.

    Option 1:

    All the members which included in S , are different from each other.

    Any member of X can be mapped with some member of P(X), once and only once.

    Therefore t is different from each member in S , therefore t MUST BE INCLUDED in S .

    Therefore S cannot be defined BEFORE we check our assumption in step 2 of Cantor's proof.

    Option 2:

    If we want to keep S as an existing member, we MUST NOT INCLUDE t in S .

    In this case we also find that S cannot be defined BEFORE we check our assumption in step 2 of Cantor's proof.


    Therefore we cannot ask nor answer to anything that is connected to member S .


    The general idea behind this point of view is the power of existence of member t and member S .

    Member t is simpler than member S .

    Member S existence depends on objects like t , therefore we have to check S by t as we did here, and not t by S as Cantor did.


    Organic
     
    Last edited: Oct 30, 2003
  14. Oct 29, 2003 #13
    i think it should be B > A and A not= B but there is a bijection between A and proper subset of B, where S is a proper subset of B if S is a subset of B and S != B.

    with this in mind, let's prove X<P(X):
    at least when X!=Ø, your map f(x)={x} will do the trick, but we have to show that the image of f is a proper subset of P(X). the image of f is precisely the set of all elements of P(X) that are singletons. therefore, Ø is not in the image of f but is in P(X), so the image of f is a proper subset of P(X). this proof doesn't work for X=Ø, but X=Ø<{Ø}=P(X) via the empty function which is a bijection (by vacuous truth) between Ø and Ø, a proper subset of {Ø}.

    in some sense, this proof is "better" because it doesn't use a trick like the set D. note that the above definition of B>A is equivalent to the following: there is a function from B onto A and there is no function from A onto B. in this definition of B>A, i think one needs the trick set D.

    this is related to the thread
    https://www.physicsforums.com/showthread.php?s=&threadid=7924
    though it doesn't look like it because that thread is analysis related and not set theory related. here's what i'm trying to accomplish in that thread. we know that P(A)=2^A. i'm trying to find a function f such that f(f(x))=2^x that is as well-behaved as possible. then the next step is to determine if a set B exists such that f(A)=B for any infinite A. (let's let all subsequently mentioned sets be infinite.) then we would have
    P(A)=2^A=f(f(A))=f(B). the hope is that f is strictly increasing on sets; i.e., there is a bijection between X and a proper subset of f(X) for all sets X. thus, we would have a set B such that A<B<P(A) for any set A. since, i believe, this would prove the continuum hypothesis, i think i will fail. the idea then would be to analyze what the failure implies. perhaps it implies that there is no such well-behaved f. or it may be that the existence of a set with cardinality f(A) is equivalent to the continuum hypothesis. in that case, if we assume the continuum hypothesis, we would then be closer to actually finding a set B such that A<B<P(A). we gots to find the f first, though.

    if A=N, then aleph_0=A and aleph_1=P(A). we'd then have fractional cardinals. for example, aleph_(1/2)=f(A). if we let h(x)=2^x, then aleph_(m/n) would be equal to g(A) where g is some function such that
    g^n(x)=h^m(x) and by g^n, i mean the nth iterate of g. (this will also potentially work for negative m.) having defined what aleph_x means for rational x, one wonders if it can be defined for real x.
     
    Last edited: Oct 29, 2003
  15. Oct 29, 2003 #14
    Hi phoenixthoth,


    Please look again at my previous post, and please tell what
    do you think about what I wrote after
    this
    |
    |
    |
    V
    =================================================
    =================================================
     
  16. Oct 29, 2003 #15
    you define D to be "the subset in P(N) [that] includes the members of N that have no image in the subset of P(N)." what do you mean by "the subset of P(N)"? which subset are you talking about? did you mean, "...no image in P(N)?" if that's what you mean, then D is automatically empty because for any map f from N to P(N), all members of N have an image in the set P(N), namely f(n). if f(N) is the image (or range) of f, are you defining D to be P(N)\f(N), the set of elements in P(N) not in the image of f? when you define D that way, there doesn't seem to be a guarantee that D will or won't be empty.

    it's kinda confusing to be reusing the letter D in this thread because D has been refered to as something different, namely D used to be the set of elements n of N such that n is not an element of f(n).
     
  17. Oct 29, 2003 #16
    No, I mean please read this part, which is another point of view on Cantor's proof.

    =================================================
    =================================================

    Let us look at this proof from another point of view.

    As we all know, any set includes only unique members or no members at all.

    Now, let us examine options 1 and 2 again.

    Option 1:

    All the members which included in S , are different from each other.

    Any member of X can be mapped with some member of P(X), once and only once.

    Therefore t is different from each member in S , therefore t MUST BE INCLUDED in S .

    Therefore S cannot be defined BEFORE we check our assumption in step 2 of Cantor's proof.

    Option 2:

    If we want to keep S as an existing subset, we MUST NOT INCLUDE t in S .

    In this case we also find that S cannot be defined BEFORE we check our assumption in step 2 of Cantor's proof.


    Therefore we cannot ask nor answer to anything that is connected to subset S .


    The general idea behind this point of view is the power of existence of member t and subset S .

    Member t is simpler than subset S .

    Subset S existence depends on objects like t , therefore we have to check S by t as we did here, and not t by S as Cantor did.


    Organic
     
    Last edited: Oct 30, 2003
  18. Oct 29, 2003 #17
    i'll just start with the first thing i don't understand.

    do you mean put in a map or mapped to?

    do you really mean "some subset of P(X)" or really an element of P(X)? if you're talking about subsets of P(X), it sounds like we're dicussing the relationship between X and P(P(X)) since subsets of P(X) are elements of P(P(X)).
     
  19. Oct 30, 2003 #18
    Hi phoenixthoth,

    Well, I am a bad formalist.

    What I mean is this: no object in X is a set, all objects in p(X) are sets.


    An example of X objects is: 23,5,17,...

    An example of P(X) objects is: {23},{5},{17},{12,67},{},{2,4,6,...),...


    So, I'll correct it to:

    Any member of X can be mapped with some member of P(X), once and only once.

    I'll write this corrected part again.

    =================================================
    =================================================

    Let us look at this proof from another point of view.

    As we all know, any set includes only unique members or no members at all.

    Now, let us examine options 1 and 2 again.

    Option 1:

    All the members which included in S , are different from each other.

    Any member of X can be mapped with some member of P(X), once and only once.

    Therefore t is different from each member in S , therefore t MUST BE INCLUDED in S .

    Therefore S cannot be defined BEFORE we check our assumption in step 2 of Cantor's proof.

    Option 2:

    If we want to keep S as an existing member, we MUST NOT INCLUDE t in S .

    In this case we also find that S cannot be defined BEFORE we check our assumption in step 2 of Cantor's proof.


    Therefore we cannot ask nor answer to anything that is connected to member S .


    The general idea behind this point of view is the power of existence of member t and member S .

    Member t is simpler than member S .

    Member S existence depends on objects like t , therefore we have to check S by t as we did here, and not t by S as Cantor did.


    Organic
     
    Last edited: Oct 30, 2003
  20. Oct 30, 2003 #19
    actually, every element of a set is also a set. that's why if you look in a set theory book, most sets are denoted by lower case letters rather than lower case for "elements" and upper case for "sets." there is *no* distinction, fundamentally, between a group of things called "elements" (which are not sets) and a group of things called "sets." for example, natural numbers are even sets:
    1={Ø}
    2={Ø,1}
    3={Ø,1,2}
    ...
    23={Ø,1,2,...,21,22}. note that "23" is a set with 23 elements.

    it's clear now that you mean "can be mapped to some member of P(X)" and not a subset of P(X).

    i'm assuming that t is an arbitrary element of X and S is "a set in P(X) which includes ALL members of X that have no image Included in the P(X) members which they are mapped with."

    "includes" should be "consists of," i think. for example, if i say S is a set including the empty set, it's ambiguous because S could be {Ø} or it could be {Ø,1}. i'll assume you mean "consists of." let me try to symbolize the definition of S:

    actually, do you mean "a set in P(X)," which would mean that S is a set that is an element of P(X) so that S would be a subset of X, or "a subset of P(X)" which would mean that S consists of subsets of X? i'll assume you mean the latter. f is our arbitrary function from X to P(X).

    S={x in X such that f(x) is not an element of f(x)}.

    "the image of x" is f(x) and "members which they are mapped [to]" is also f(x). to put the word "no" in front of "image" is what lead me to put "not" in front of "an." let me know if this is the definition of S and then i'll be able to read the rest. if this isn't what you mean by S, then please write it down using symbols like the italycized ones above because that tends to be less ambiguous.
     
  21. Oct 30, 2003 #20

    Hurkyl

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    For the record, some set theories permit there to be objects that are not sets, and that list of natural numbers as sets is merely a model; natural numbers don't have to be those sets. (and, in general, they don't have to be sets at all, though in ZFC they do)
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?



Similar Discussions: On P(X) > X
  1. Derivative x^x^x (Replies: 7)

  2. Solve x^x=x (Replies: 7)

  3. Curve-fitting y=x^p+C (Replies: 23)

  4. X+(∞)+(-∞) = x? (Replies: 5)

Loading...