[Math] the explanation for the elements of this set

elementary-set-theory

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…

Best Answer

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)$.

Related Question