Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
1  
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
1  
@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
add comment

2 Answers

up vote 4 down vote accepted

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

share|improve this answer
    
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
add comment

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

share|improve this answer
    
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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.