# What is the explanation for the elements of this set?

From Stephen Abbott's Understanding Analysis (some parts omitted):

Exercise 1:

(a) Using the particular set $A = \{a,b,c\}$, exhibit two different $1-1$ mappings from $A$ into $P(A)$.

(b) Letting $B = \{1,2,3,4\}$, produce an example of a $1-1$ map $g: B \to P(B)$.

Exercise 2:

Construct $B$ using the following rule. For each element $a \in A$, consider the subset $f(a)$. This subset of $A$ may contain the element $a$ or it may not. This depends on the function $f$. If $f(a)$ does not contain $a$, then we include $a$ in our set $B$. More precisely, let $B = \{a \in A: a \notin f(a) \}$.

Return to the particular functions constructed in Exercise 1 and construct the subset $B$ that results using the preceding rule. In each case, note that $B$ is not in the range of the function used.

Solution Exercise 1:

(a) Given set $A = \{a,b,c\}$, $A$ can be mapped in a $1-1$ fashion into $P(A)$ in many ways. For example, we could write (i) $a \to \{a\}$, $b \to \{ a,c\}$, $c \to \{a,b,c\}$.

As another example we might say (ii) $a \to \{b,c\}$, $b \to \emptyset$, $c \to \{a,c\}$.

(b) An example of a $1-1$ mapping from $B$ to $P(B)$ is: $1 \to \{1\}$, $2 \to \{ 2,3,4\}$, $3 \to \{1,2,4\}$, $4 \to \{2,3\}$.

Solution Exercise 2:

For the example in (a) (i), the set $B = \{b\}$. For example (ii) we get $B=\{a,b\}$. In part (b) we find $B = \{3,4\}$. In every case, the set $B$ fails to be in the range of the function that we defined.

Question(s):

Could someone please help me understand what I am missing? I don't think I had any trouble with the first exercise, but my answer to the second was different. For (a) (i), I would have thought that $B = \{b,c\}$. For (a) (ii), I had $B = \{ a,b,c\}$. For (b), I had $\{ 2,3,4\}$.

I can't really seem to find a pattern, or figure out what I am doing wrong. I thought I might be getting confused with distinctions between elements and "the sets containing" elements, but I am not sure. For instance, with (a) (i) is the image $\{ \{ a\}, \{ a,c\} \{ a,b,c\}\}$ ? Is $a$ getting mapped to $a$ or to "the set containing $a$" which is written as $\{ a\}$? If it were the latter, I would think $B = \{ a,b,c\}$ instead, but this doesn't seem to make much sense...

So, as I said, if someone could help explain it all to me, I would really appreciate it. Thanks!

Edit: The solutions in the block-text are not my own, they were those provided by the author...

-
It was poor choice of notation by the authors to use $B$ in 2 related ways like this. – Srivatsan Sep 7 '11 at 23:00
@Sriv: Yes, the notation is awful. Not only is $B$ overloaded, $a$ is too. So an explanation has to contain "... To find out whether $b\in B$, we let $a=b$ and ask whether $a\in f(a)$. Now, $f(a)$, which is $f(b)$, is $\{a,c\}$, and that does not contain $a$ (because $a$ is $b$ and $b$ is not a member) -- yes yes it does contain $a$, but $a$ is not the value of $a$ anymore, so that doesn't matter ..." – Henning Makholm Sep 7 '11 at 23:13
Not exactly on topic, but the OP's Gold badge to Reputation ratio must be the highest on the website! – Ragib Zaman Sep 8 '11 at 4:12

To calculate $B$ systematically, I would recommend you to forget about the complete description for $f$; instead focus on one element $x$ and its image $f(x)$ at a time. One important thing to keep in mind is that $x$ is an element of the set $A = \{ a, b, c\}$, whereas $f(x)$ is a subset of $A$. So it is perfectly legitimate to ask whether $x \in f(x)$ or not.

Let me do the example (a)(i) in full.

• Take the element $a$. How do I know whether $a \in B$? The definition says it belongs to $B$ if and only if $a \not\in f(a)$. Now, consulting the function, we find that $f(a) = \{ a \}$. So we are interested in knowing if $a \in \{ a \}$ holds or not. This statement is indeed true; hence $a \in f(a)$ is also true. Therefore, from the definition of $B$, we conclude that $a$ is not present in $B$.
• Now, for the element $b$, we have $f(b) = \{ a, c\}$. Now, the question is whether or not $b \in \{ a,c\} = f(b)$. This time, we have $b \not\in f(b)$. Hence $b \in B$.
• Finally, for the element $c$, the image $f(c)$ is $\{ a,b,c \}$. Notice that $c$ is present in $\{ a,b,c \} = f(c)$. What does this tell you about the membership of $c$ in $B$?

The remaining exercises involve a similar reasoning; can you take it from here?

You are also asked to note that $B$ is not in the range $f$ in each case. Here, $f(A)$, the range of $f$, is a set containing subsets of $A$. For the above example, $$f(A) = \{ \{a\}, \{ a,c \}, \{ a,b,c \} \}.$$ Also $B$ is just a subset of $A$ (this is actually even more evident). So the exercise asks you to check that $B$ is not an element of $f(A)$. In the above example, $B = \{ b \}$, and it is easy to verify that $b \not\in f(A)$.

-
thank you, that definitely helps a lot. I still have to ask: in order to "note that $B$ is not in the range of the function" we then need to consider the range of the function to be $\{ \{ a\}, \{ a,c\} \{ a,b,c\}\}$ as I wrote in the question? And that's why $B = \{b\} \notin f(A)$? Is that correct? In other words $B$ is a set, but the important observation is that it is not an element of the range of the function? – ghshtalt Sep 7 '11 at 23:26
by the way I hope that $f(A)$ is the correct notation for the range of the function. – ghshtalt Sep 7 '11 at 23:27

Your solutions to exercise 1 are fine. You have the image of $A$ correct in 2 and yes, in the first function $a$ is getting mapped to $\{a\}$. Using your first function $A \to P(A), a \in f(a), b \not \in f(b), c \in f(c), \text{ so } B=\{b\}$. Then you are asked to notice that there is no $d \in A$ such that $f(d)=\{b\}$. You can check your other function the same way. This is setting up for Cantor's diagonal proof that $|A| \lt |P(A)|$

Added: for Exercise 2 it is true that $f$ goes from elements of $A$ to subsets of $A$. So $a \to \{a\}$, which is why we can ask if $a \in f(a)$. referring to the function in Example (a)(i), $c$ is an element of $\{a,b,c\}=f(c)$, which is why $c$ is not an element of $B$. For example (a)(ii), $c \in \{a,c\}$, so $c \not \in B$ but the other two are in $B$.

-
Sorry, those weren't actually my solutions, I've updated the question to hopefully make that more clear... – ghshtalt Sep 7 '11 at 23:04