Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It only takes a minute to sign up.
Sign up to join this community
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?
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$.
