Results 1 to 9 of 9

Math Help - Problem - Onto mapping with power set.

  1. #1
    Super Member
    Joined
    Apr 2009
    Posts
    677

    Problem - Onto mapping with power set.

    Let S be a set. S* is the power set of S. Prove there can't be any onto mapping from S->S*

    My approach:
    1. Let f be a onto mapping from S->S*
    2. Define a set X as follows:
    X={s| s belong to S AND s doesn't belong to f(s)}
    3. Claim X is not in the image of 'f'
    Let X=f(s) for some s in S.
    It is easy to show element 's' will belong exactly to ONE of X or f(s)
    Hence X =/= f(s)

    Question - Is my proof rigorous enough? For all types of sets - finite, infinite, non-countable etc?

    Thanks
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Junior Member nimon's Avatar
    Joined
    Sep 2009
    From
    Edinburgh, UK
    Posts
    64
    The proposition is true for any set, and this proof is valid for any set, whether it be uncountable, infinite or whatever else you can think of. The crucial fact is that
    X=\{s\in S | s\notin f(s)\}
    is a valid subset of S for any set S. A good question to ask youself is "why wouldn't this be true for an uncountabe set?" You should eventually be convinced that there is no reason.

    N.b. It is the stipulation that  s \in S in the definition of X which rescues us from paradoxes such as Russel's Paradox.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Super Member
    Joined
    Apr 2009
    Posts
    677
    Quote Originally Posted by nimon View Post
    The proposition is true for any set, and this proof is valid for any set, whether it be uncountable, infinite or whatever else you can think of. The crucial fact is that
    X=\{s\in S | s\notin f(s)\}
    is a valid subset of S for any set S. A good question to ask youself is "why wouldn't this be true for an uncountabe set?" You should eventually be convinced that there is no reason.

    N.b. It is the stipulation that  s \in S in the definition of X which rescues us from paradoxes such as Russel's Paradox.
    Thanks Nimon. Yes - I too find my proof pretty convincing. But I'm still a novice at all this - so wanted to be sure.

    Initially I constructed X by defining it in terms of s1,s2,,,,sn,.... where each si was in S. This, I felt, somehow limits the proof to countable sets. So, I modified the definition of X.

    I want to be sure I understand your comments well.

    "A good question to ask youself is "why wouldn't this be true for an uncountabe set?" You should eventually be convinced that there is no reason."

    Is there more to it than what I stated in pt 3 of my post ? -
    3. Claim X is not in the image of 'f'
    Let X=f(s) for some s in S.
    It is easy to show element 's' will belong exactly to ONE of X or f(s)
    Hence X =/= f(s)

    Also, haven't understood your comment -
    "N.b. It is the stipulation that in the definition of which rescues us from paradoxes such as Russel's Paradox. "
    Would you please mind explaining a bit or letting me know the pointers where I can read further. Thanks
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor Drexel28's Avatar
    Joined
    Nov 2009
    From
    Berkeley, California
    Posts
    4,563
    Thanks
    21
    There is a slightly easier way.

    It is not to difficult to prove that the mapping \Phi:\wp\left(X\right)\mapsto \left\{0,1\right\}^X given by E\mapsto f_{E}(x)=\begin{cases} 1 & \mbox{if} \quad x\in E \\ 0 & \mbox{if} \quad x\notin E \end{cases} is a bijection. Therefore \wp\left(X\right)\simeq\left\{0,1\right\}^X. Therefore you must show that X and \left\{0,1\right\}^X cannot be equipotent. Can you see a slightly easier way to proceed now?
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Super Member
    Joined
    Apr 2009
    Posts
    677
    Quote Originally Posted by Drexel28 View Post
    There is a slightly easier way.

    It is not to difficult to prove that the mapping \Phi:\wp\left(X\right)\mapsto \left\{0,1\right\}^X given by E\mapsto f_{E}(x)=\begin{cases} 1 & \mbox{if} \quad x\in E \\ 0 & \mbox{if} \quad x\notin E \end{cases} is a bijection. Therefore \wp\left(X\right)\simeq\left\{0,1\right\}^X. Therefore you must show that X and \left\{0,1\right\}^X cannot be equipotent. Can you see a slightly easier way to proceed now?
    Thanks Drexel28m for your post. Please forgive my ignorance, I have not understood a few things here.

    1. \Phi:\wp\left(X\right)\mapsto \left\{0,1\right\}^X - What does this mean, I mean I don't understand the definitions here? Please feel free to point me where I can read it up.

    2. <br />
E\mapsto f_{E}(x)=\begin{cases} 1 & \mbox{if} \quad x\in E \\ 0 & \mbox{if} \quad x\notin E \end{cases}<br />

    This is also not clear to me

    3. What is equipotent?
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor Drexel28's Avatar
    Joined
    Nov 2009
    From
    Berkeley, California
    Posts
    4,563
    Thanks
    21
    Quote Originally Posted by aman_cc View Post
    Thanks Drexel28m for your post. Please forgive my ignorance, I have not understood a few things here.

    1. \Phi:\wp\left(X\right)\mapsto \left\{0,1\right\}^X - What does this mean, I mean I don't understand the definitions here? Please feel free to point me where I can read it up.

    2. <br />
E\mapsto f_{E}(x)=\begin{cases} 1 & \mbox{if} \quad x\in E \\ 0 & \mbox{if} \quad x\notin E \end{cases}<br />

    This is also not clear to me

    3. What is equipotent?
    Don't feel ignorant. Just a difference in notation.

    Definitions:

    \wp\left(X\right)- power set of X

    \left\{0,1\right\}^X=\left\{f:f:X\mapsto\{0,1\}\ri  ght\}. In other words it is the set of all functions that map from X into \{0,1\}.


    E\mapsto f_{E}(x)=\begin{cases} 1 & \mbox{if} \quad x\in E \\ 0 & \mbox{if} \quad x\notin E \end{cases}- This is just the charceristic function of E. It equals 1 if x\in E and 0 if not.

    equipotent- Two sets X,Y are equipotent (denoted X\simeq Y) if there exists a bijection between the two, i.e. \text{card }X=\text{card }Y.

    Therefore what one means when they say " \Phi:\wp\left(X\right)\mapsto\left\{0,1\right\}^X given by E\mapsto f_{E}(x)=\begin{cases} 1 & \mbox{if} \quad x\in E \\ 0 & \mbox{if} \quad x\notin E \end{cases}" what they are really saying is "define a mapping between the power set of X and the set of all functions that map X into \{0,1\} by a subset of X (lets say E) is mapped to the charceristic function of that subset ( E\mapsto f_{E}(x)=\begin{cases} 1 & \mbox{if} \quad x\in E \\ 0 & \mbox{if} \quad x\notin E \end{cases}). Doing this we can easily prove that \wp\left(X\right)\simeq\left\{0,1\right\}^X. Therefore instead of proving that X and \wp\left(X\right) aren't equipotent you merely need to show that X and \left\{0,1\right\}^X aren't equipotent (this is because equipotence is an equivalance relation). This is actually an easier task.

    Here is how. I will give you the outline and you fill in the "why?" in the last step.

    Let \phi be some injective mapping from X to \left\{0,1\right\}^X. Then \phi(x)=\phi_x, and since \phi_x \in\left\{0,1\right\}^X we see that \phi_x:X\mapsto\{0,1\}. Now define a second mapping \sigma:X\mapsto \{0,1\} by \sigma(x')=\begin{cases} 1 & \mbox{if} \quad \phi_x(x')=0 \\ 0 & \mbox{if} \quad \phi_x(x')=1 \end{cases}. Then clearly \sigma\in\left\{0,1\right\}^X but \sigma\notin \text{Im }\phi (why?). Therefore we may conclude that there is no surjection between \left\{0,1\right\}^X and X. Consequently, there is no surjection between \wp\left(X\right) and X. Therefore \text{card }X\ne\text{card }\wp\left(X\right)

    Remark: Realizing that f:X\mapsto\wp\left(X\right) given by x\mapsto\{x\} is an injection, we may conclude that \text{card }X\le\text{card }\wp\left(X\right). Combining this with teh above we may definitively say that \text{card }X<\text{card }\wp\left(X\right)


    I hope that helps.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Super Member
    Joined
    Apr 2009
    Posts
    677
    Quote Originally Posted by Drexel28 View Post
    Don't feel ignorant. Just a difference in notation.

    Definitions:

    \wp\left(X\right)- power set of X

    \left\{0,1\right\}^X=\left\{f:f:X\mapsto\{0,1\}\ri  ght\}. In other words it is the set of all functions that map from X into \{0,1\}.


    E\mapsto f_{E}(x)=\begin{cases} 1 & \mbox{if} \quad x\in E \\ 0 & \mbox{if} \quad x\notin E \end{cases}- This is just the charceristic function of E. It equals 1 if x\in E and 0 if not.

    equipotent- Two sets X,Y are equipotent (denoted X\simeq Y) if there exists a bijection between the two, i.e. \text{card }X=\text{card }Y.

    Therefore what one means when they say " \Phi:\wp\left(X\right)\mapsto\left\{0,1\right\}^X given by E\mapsto f_{E}(x)=\begin{cases} 1 & \mbox{if} \quad x\in E \\ 0 & \mbox{if} \quad x\notin E \end{cases}" what they are really saying is "define a mapping between the power set of X and the set of all functions that map X into \{0,1\} by a subset of X (lets say E) is mapped to the charceristic function of that subset ( E\mapsto f_{E}(x)=\begin{cases} 1 & \mbox{if} \quad x\in E \\ 0 & \mbox{if} \quad x\notin E \end{cases}). Doing this we can easily prove that \wp\left(X\right)\simeq\left\{0,1\right\}^X. Therefore instead of proving that X and \wp\left(X\right) aren't equipotent you merely need to show that X and \left\{0,1\right\}^X aren't equipotent (this is because equipotence is an equivalance relation). This is actually an easier task.

    Here is how. I will give you the outline and you fill in the "why?" in the last step.

    Let \phi be some injective mapping from X to \left\{0,1\right\}^X. Then \phi(x)=\phi_x, and since \phi_x \in\left\{0,1\right\}^X we see that \phi_x:X\mapsto\{0,1\}. Now define a second mapping \sigma:X\mapsto \{0,1\} by \sigma(x')=\begin{cases} 1 & \mbox{if} \quad \phi_x(x')=0 \\ 0 & \mbox{if} \quad \phi_x(x')=1 \end{cases}. Then clearly \sigma\in\left\{0,1\right\}^X but \sigma\notin \text{Im }\phi (why?). Therefore we may conclude that there is no surjection between \left\{0,1\right\}^X and X. Consequently, there is no surjection between \wp\left(X\right) and X. Therefore \text{card }X\ne\text{card }\wp\left(X\right)

    Remark: Realizing that f:X\mapsto\wp\left(X\right) given by x\mapsto\{x\} is an injection, we may conclude that \text{card }X\le\text{card }\wp\left(X\right). Combining this with teh above we may definitively say that \text{card }X<\text{card }\wp\left(X\right)


    I hope that helps.
    Really appreciate your help and effort. I will read your response carefully and get back for any further questions. Thanks
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Super Member
    Joined
    Apr 2009
    Posts
    677
    Quote Originally Posted by Drexel28 View Post
    Don't feel ignorant. Just a difference in notation.

    Definitions:

    \wp\left(X\right)- power set of X

    \left\{0,1\right\}^X=\left\{f:f:X\mapsto\{0,1\}\ri  ght\}. In other words it is the set of all functions that map from X into \{0,1\}.


    E\mapsto f_{E}(x)=\begin{cases} 1 & \mbox{if} \quad x\in E \\ 0 & \mbox{if} \quad x\notin E \end{cases}- This is just the charceristic function of E. It equals 1 if x\in E and 0 if not.

    equipotent- Two sets X,Y are equipotent (denoted X\simeq Y) if there exists a bijection between the two, i.e. \text{card }X=\text{card }Y.

    Therefore what one means when they say " \Phi:\wp\left(X\right)\mapsto\left\{0,1\right\}^X given by E\mapsto f_{E}(x)=\begin{cases} 1 & \mbox{if} \quad x\in E \\ 0 & \mbox{if} \quad x\notin E \end{cases}" what they are really saying is "define a mapping between the power set of X and the set of all functions that map X into \{0,1\} by a subset of X (lets say E) is mapped to the charceristic function of that subset ( E\mapsto f_{E}(x)=\begin{cases} 1 & \mbox{if} \quad x\in E \\ 0 & \mbox{if} \quad x\notin E \end{cases}). Doing this we can easily prove that \wp\left(X\right)\simeq\left\{0,1\right\}^X. Therefore instead of proving that X and \wp\left(X\right) aren't equipotent you merely need to show that X and \left\{0,1\right\}^X aren't equipotent (this is because equipotence is an equivalance relation). This is actually an easier task.

    Here is how. I will give you the outline and you fill in the "why?" in the last step.

    Let \phi be some injective mapping from X to \left\{0,1\right\}^X. Then \phi(x)=\phi_x, and since \phi_x \in\left\{0,1\right\}^X we see that \phi_x:X\mapsto\{0,1\}. Now define a second mapping \sigma:X\mapsto \{0,1\} by \sigma(x')=\begin{cases} 1 & \mbox{if} \quad \phi_x(x')=0 \\ 0 & \mbox{if} \quad \phi_x(x')=1 \end{cases}. Then clearly \sigma\in\left\{0,1\right\}^X but \sigma\notin \text{Im }\phi (why?). Therefore we may conclude that there is no surjection between \left\{0,1\right\}^X and X. Consequently, there is no surjection between \wp\left(X\right) and X. Therefore \text{card }X\ne\text{card }\wp\left(X\right)

    Remark: Realizing that f:X\mapsto\wp\left(X\right) given by x\mapsto\{x\} is an injection, we may conclude that \text{card }X\le\text{card }\wp\left(X\right). Combining this with teh above we may definitively say that \text{card }X<\text{card }\wp\left(X\right)


    I hope that helps.
    Let me try to answer your 'why' part. Most of your proof is clear to me. However, I'm trouble understanding the way \sigma:X\mapsto \{0,1\} is defined. I think this is due to the way you have used x' and x in the definition.
    So I'm gonna define it the way I have understood and you can tell me if I got it correct.

    \sigma(x)=\begin{cases} 1 & \mbox{if} \quad \phi_x(x)=0 \\ 0 & \mbox{if} \quad \phi_x(x)=1 \end{cases} \forall x \in X

    I would also assume \phi is a bijection and thus a surjection from  X\mapsto\{0,1\}^X. You I guess assumed that \phi is an injection. I have a dis-connect here as well.


    Now \sigma (as defined by me) , definitely \in \{0,1\}^X

    As \phi is a surjection so \exists x_0 \in X such that \phi(x_0)=\phi_{x0}=\sigma.

    But consider \phi_{x0}(x_0) and \sigma(x_0). Obviously if one is 1 the other is 0. Hence \sigma\notin \text{Im }\phi. Thus \phi can't be a surjection and thus can't be a bijection.

    Am I correct?
    Last edited by aman_cc; November 13th 2009 at 03:33 AM.
    Follow Math Help Forum on Facebook and Google+

  9. #9
    MHF Contributor Drexel28's Avatar
    Joined
    Nov 2009
    From
    Berkeley, California
    Posts
    4,563
    Thanks
    21
    Quote Originally Posted by aman_cc View Post
    Let me try to answer your 'why' part. Most of your proof is clear to me. However, I'm trouble understanding the way \sigma:X\mapsto \{0,1\} is defined. I think this is due to the way you have used x' and x in the definition.
    So I'm gonna define it the way I have understood and you can tell me if I got it correct.

    \sigma(x)=\begin{cases} 1 & \mbox{if} \quad \phi_x(x)=0 \\ 0 & \mbox{if} \quad \phi_x(x)=1 \end{cases} \forall x \in X

    I would also assume \phi is a bijection and thus a surjection from  X\mapsto\{0,1\}^X. You I guess assumed that \phi is an injection. I have a dis-connect here as well.


    Now \sigma (as defined by me) , definitely \in \{0,1\}^X

    As \phi is a surjection so \exists x_0 \in X such that \phi(x_0)=\phi_{x0}=\sigma.

    But consider \phi_{x0}(x_0) and \sigma(x_0). Obviously if one is 1 the other is 0. Hence \sigma\notin \text{Im }\phi. Thus \phi can't be a surjection and thus can't be a bijection.

    Am I correct?
    If I am understanding what you are saying !
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 5
    Last Post: March 16th 2011, 07:11 PM
  2. Complex open mapping & conformal mapping problems.
    Posted in the Differential Geometry Forum
    Replies: 1
    Last Post: February 22nd 2011, 07:26 AM
  3. Power Problem
    Posted in the Pre-Calculus Forum
    Replies: 5
    Last Post: December 24th 2008, 12:01 AM
  4. power problem
    Posted in the Discrete Math Forum
    Replies: 9
    Last Post: March 6th 2008, 10:24 PM
  5. Power problem
    Posted in the Algebra Forum
    Replies: 1
    Last Post: December 21st 2005, 02:02 AM

Search Tags


/mathhelpforum @mathhelpforum