Problem - Onto mapping with power set.

**aman_cc** · November 11th 2009, 07:29 AM

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

**nimon** · November 11th 2009, 08:14 AM

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.

**aman_cc** · November 11th 2009, 08:48 AM

Originally Posted by nimon

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

**Drexel28** · November 11th 2009, 10:49 AM

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?

**aman_cc** · November 12th 2009, 12:16 AM

Originally Posted by Drexel28

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?

**Drexel28** · November 12th 2009, 06:43 AM

Originally Posted by aman_cc

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.

**aman_cc** · November 12th 2009, 06:49 AM

Originally Posted by Drexel28

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

**aman_cc** · November 13th 2009, 03:23 AM

Originally Posted by Drexel28

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?

**Drexel28** · November 17th 2009, 08:09 PM

Originally Posted by aman_cc

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

!

Thread: Problem - Onto mapping with power set.

LinkBack

Thread Tools

Display

Problem - Onto mapping with power set.

Similar Math Help Forum Discussions

Contraction mapping problem in n-dimensional vector-valued function

Complex open mapping & conformal mapping problems.

Power Problem

power problem

Power problem

Search Tags