Lesson 14 Solutions

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 $P(A)$ , 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 $P(A)$ . 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!

Back to Lesson 14

On to Lesson 15