1
$\begingroup$

In the proof of the theorem "For any set A, there does not exist a function mapping A onto its power set P(A)", there's a sentence (highlighted) that I couldn't follow. Contrary to what the illustration says, clearly {1, 3} comes from elements of A. Was it a typo or I missing something?

enter image description here

$\endgroup$
7
  • $\begingroup$ This is really a math question and not stat, but write down every subset of $\{1,2,3\}$ and call each by a letter. (For example, $\{1,3\}$ could be called D.) Now rewrite all references to such subsets in terms of the letters. $\endgroup$
    – Dave
    Commented Nov 20, 2019 at 23:51
  • $\begingroup$ Thanks for your response @Dave. Just to clarify: you meant B = {1, 3} should be viewed as an element, not collection of elements, thus element {1, 3} doesn't come from A whose elements are 1, 2, and 3? $\endgroup$
    – Nemo
    Commented Nov 20, 2019 at 23:59
  • 1
    $\begingroup$ That’s exactly what I mean! $\endgroup$
    – Dave
    Commented Nov 21, 2019 at 0:15
  • 2
    $\begingroup$ $B=\{1,3\}$ is an element of the power set of $\{1,2,3\}$. As an exercise, write out that entire power set. $\endgroup$
    – Dave
    Commented Nov 21, 2019 at 0:36
  • 1
    $\begingroup$ Yes, $\{1,3\}$ is a subset of $\{1,2,3\}$, that has never been the issue. What matters is that it is not one of the subsets that has been hit by the function: call the function $f$, and note that $f(1),f(2),f(3)$ are all different from $\{1,3\}$. So: $\{1,3\}$ is a subset of $\{1,2,3\}$ that is not in the image of $f$. So $f$ is not a surjection. $\endgroup$
    – Andrés E. Caicedo
    Commented Nov 21, 2019 at 14:25

1 Answer 1

Reset to default
2
$\begingroup$

You are confusing what the author means by "come from".

The author means $f(1) = \{2\}$ so the output of the function, $\{2\}$ "comes from" the input of $1$.

$f(2) = \{2,3\}$ so the output of the function, $\{2,3\}$ "comes from" the input of $2$.

And $f(3) = \{1,2\}$ so the output of the function, $\{1,2\}$ "comes from" the input of $3$.

.... So what input, $x \subset A$ will give you $f(x) = \{1,3\}$?

The answer is: None! There are only three possible inputs: 1,2,3; but there are eight possible outputs: $\emptyset, \{1\}, \{2\}, \{3\}, \{1,2\}, \{1,3\},\{2,3\}, \{1,2,3\}$.

$5$ of them do not "come from" any element of $A$: $\emptyset, \{1\}, \{3\}, , \{1,3\}, \{1,2,3\}$.

====

This picture is if we define $B = \{$ then elements $a\in A$ so that $a \not \in f(a)\}$ then $1\not \in \{2\}= f(1)$ and $2\in \{2,3\}=f(2)$ and $3\not \in \{1,2\}$ so $B = \{1,3\}$.

Notice that $f(a) = B$ is impossible. If $a \in B = f(a)$ then by definition $a \not \in B$. But if $a \not \in f(a) = B$ then by definition $a \in B$.

So it is not possible to have have a function from $A\to P(A)$ where there is an $a \in A$ and $f(a) = B= \{$ then elements $a\in A$ so that $a \not \in f(a)\}$.

So $f$ can never be onto.

.....

You may think what if $B$ is empty and all elements are members of the sets they are mapped to.

Say $f(1) = \{1,2\}; f(2) = \{2,3\}, f(3)=\{1,2,3\}$.

Then $1 \in f(1); 2\in f(2); 3\in f(3)$ and $B= \{$ then elements $a\in A$ so that $a \not \in f(a)\}=\emptyset$

But .... what is $a$ where $f(a) = \emptyset$.

Nothing. There is not $f(a) = \emptyset$

And if you did have $f(a) = \emptyset$ then $a\in B$ because $a\not \in f(a) = \emptyset$. So $B\ne \emptyset$ because $a\in B$.

[Example: $f(1) = \emptyset$; $f(2)=\{2,3\}; f(3) =\{1,3\}$ then $1 \not \in \emptyset= f(1)$ but $2 \in \{2,3\}$ so $2 \in f(2)$ and $3 \in f(3) = \{1,3\}$ so $B = \{1\}\ne \emptyset=f(1)$.

And there $\{1\}$ doesn't "come from" $1$.

===

No matter what set $A$ is, even if it is infinite, having an $a\in A$ so that $f(a) = B$ is impossible by logic. If $f(a) = B$ and $a\in B$ then $a \in f(a)$ and $a\not \in B$. ANd if $a\not \in B$ then $a\not \in f(a)$ and $a \in B$.

$\endgroup$
1
  • $\begingroup$ Thanks @fleablood for your very detailed answer. Yes, I did misunderstand the phrase come from. Regarding the example of B = {empty}, I think it's only possible because the definition of power set includes it (the empty set), that is, without that concession, the example won't stand. Moreover, the whole proof is based on the constrain that B contains a such that a does not belong to f (a). What if that constrain was false (like a trick to our mind, not a true reality), so that we thought the theorem was true/correct. Just wondering. $\endgroup$
    – Nemo
    Commented Nov 21, 2019 at 23:19

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .