9
$\begingroup$

Proof: Assume it is countable. Then we can arrange the sets in order (an enumeration) $A_1, A_2, A_3, ... $. Now construct the set $ B = \{i \in \mathbb{N} \ | \ i \notin A_i \}$. Then $B=A_j$ for some $j$, a contradiction.

This was the proof given in class and feels off. Can anyone elaborate or tell me it's wrong?

$\endgroup$
3
  • $\begingroup$ This has nothing to do with measure theory, so I removed the tag. $\endgroup$
    – Pedro
    Apr 10, 2013 at 4:22
  • $\begingroup$ How do we know that B isn't empty as there is no such i? That would be the part that I'd want elaborated in a sense. $\endgroup$
    – JB King
    Apr 10, 2013 at 4:23
  • $\begingroup$ @JBKing It can't be empty because the empty set is a subset of $2^{\mathbb{N}}$. If this is countable, the empty set is then $A_j$ for some $j$. Certainly $j \not\in A_j$, so $j\in B$. The empty set is not different to any other set in this proof. $\endgroup$ Apr 10, 2013 at 4:26

1 Answer 1

14
$\begingroup$

It’s the standard argument; there’s nothing wrong with it, apart from the fact that there is no need to cast it as a proof by contradiction. The real idea is simply that if you take any list of subsets of $\Bbb N$ ordered by the positive integers $-$ i.e., a list of the form $A_1,A_2,A_3,\dots$ $-$ there is guaranteed to be a subset of $\Bbb N$ not in your list.

Suppose that we’ve proved that statement: then it follows immediately that it is impossible to list all subsets of $\Bbb N$ in a $1$-$2$-$3$ enumeration of this kind and hence that $\wp(\Bbb N)$ must be uncountable: there is no bijection from $\Bbb N$ to $\wp(\Bbb N)$, because there isn’t even a map from $\Bbb N$ onto $\wp(\Bbb N)$.

The proof of the statement is exactly what you were shown. I’m going to construct a set $B\subseteq\Bbb N$ by going through the positive integers one at a time and deciding whether to put it into $B$ or leave it out. If $k\notin A_k$, I’ll put $k$ into $B$; otherwise, if $k\in A_k$, I’ll leave $k$ out of $B$. In this way I make sure that the sets $B$ and $A_k$ disagree about $k$: exactly one of them contains $k$. In other words, one of them contains $k$, and the other does not. I don’t have to know which is which to recognize that this means that $B\ne A_k$: $B$ and $A_k$ definitely don’t have exactly the same elements, precisely because they disagree at $k$.

The argument that you were given just described this same set $B$ more concisely: $$B=\{k\in\Bbb N:k\notin A_k\}\;.\tag{1}$$

$(1)$ just says very briefly in symbols what I said at much greater length in words when I wrote this:

I’m going to construct a set $B\subseteq\Bbb N$ by going through the positive integers one at a time and deciding whether to put it into $B$ or leave it out. If $k\notin A_k$, I’ll put $k$ into $B$; otherwise, if $k\in A_k$, I’ll leave $k$ out of $B$.

$\endgroup$
3
  • $\begingroup$ Thanks, Professor Scott. This makes sense-- I guess there was just a lot of information packaged in that set construction. I do have a question that you sound like you may be able to answer. Are these problems addressed the same way with ZFC set theory as Cantor's original diagonalization arguments? This is a diagonal argument, isn't it? Isn't the problem with naive set theory that there are inherit contradictions when we only require sets to be elements such that a statement is true ($k \notin A_k$)? So even if it works in this particular case, it might be normal that is seems weird? $\endgroup$
    – Jared
    Apr 10, 2013 at 19:28
  • $\begingroup$ @Questioneer: You’re welcome. Yes, this a classic diagonalization argument. There is no problem here: the definition of $B$ is an instance of restricted comprehension, using some property to pick out a subset of something ($\Bbb N$) already known to be a set. Russell’s paradox arises from the use of unrestricted comprehension. It’s not unusual, I think, to find the argument a bit strange at first, but it’s not at all problematic. ‘[T]his particular case’ is normal, not unusual. $\endgroup$ Apr 10, 2013 at 19:38
  • $\begingroup$ I am a bit confused here. Can't B equal to some other $A_j$ ? Do you mean $B$ is a compliment of $A_k$ where the universe is natural numbers? $\endgroup$ Apr 16, 2014 at 12:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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