Exercise 1) **There was some seriously subtle logic hidden in the proof that an arbitrary infinite set can’t be put into a bijective correspondence with its power set. It’s very similar to the paradox of lesson 5. Namely, when we ask “is our new set T in the list?”, we’re really asking if there is some “a” in A such that F(a)=T. To show that there is no such “a”, we can suppose that there is such an “a”, and then arrive at a contradiction. But what happens when you suppose there is such an “a”?**

Solution: Recall where we were at this part of the argument. We had supposed the existence of a bijective function from A to , where A was any arbitrary infinite set. We then constructed a set T by putting each element in A into T only if it is **not** in the set that it maps to under F. Namely, we recall that for each element “a” in A, F(a) is a subset of A, and so we put “a” in T only if it’s **not** in F(a). Then we want to ask whether or not T, which is a perfectly good subset of A, is mapped to by F. It should be, since F is supposed to be bijective from A to . So let’s** suppose** it is. If it is mapped to by F, then there is some element, let’s call it “b”, in A such that F(b)=T.

Now, the contradiction that we’ll come to (and which will therefore prove that T is not mapped to by F), is that “b” is both in T and **not** in T. This is clearly impossible, since an element can’t be both in and not in a set. Recall how T was defined. We say that for any element “a” in A, “a” is in T if “a” is **not** in F(a), and “a” **is** in T if “a” is **not** in F(a). So suppose that “b” is in T. Then, by definition of T, “b” must **not** be in F(b). But F(b)=T! So “b” **is** in F(b), which is impossible because we supposed that it was in T. This is a contradiction, so let’s suppose that the other case is true. Namely, we’re forced to suppose that “b” is not in T. Then “b” must be in F(b), because that’s what the definition of T tells us. But again, F(b)=T, so “b” is in fact in T, which is a contradiction because we just supposed that it wasn’t! Thus, no matter what, if we suppose that there is a “b” such that F(b)=T, then “b” will be both in and not in T, which is impossible. Therefore we must **not be able to suppose** that there is such a “b”, and therefore we’re forced to conclude that T is not in our correspondence.

This was the detailed argument which I skipped over in the lesson simply because I think the main thrust of the argument gets through without going into these gory details, but it is a nice bit of careful logic that one should think through. It is **precisely** our desire to avoid these kinds of contradictions that **forces us** to accept the existence of all these new infinities!