# 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. Sep 7, 2011 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 ..." Sep 7, 2011 at 23:13
• Not exactly on topic, but the OP's Gold badge to Reputation ratio must be the highest on the website! Sep 8, 2011 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? Sep 7, 2011 at 23:26
• by the way I hope that $f(A)$ is the correct notation for the range of the function. Sep 7, 2011 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... Sep 7, 2011 at 23:04