- #1

PingPong

- 62

- 0

## Homework Statement

Prove that the set of all subsets of the natural numbers is uncountable.

## Homework Equations

All of the countability stuff - including Cantor's diagonal argument

## The Attempt at a Solution

I think I have this one figured out, but I was wondering if somebody would be willing to check it for me.

Suppose we have a subset of the natural numbers, A. Then I've defined a bijective function [tex]f:A\rightarrow \{s_k\}[/tex], where [tex]s_k=1[/tex] if [tex]k\in A[/tex] and 0 if [tex]k\notin A[/tex] (that is, convert A to a sequence of 0's and 1's, based on whether or not the kth natural number is in the subset A). Using Cantor's diagonal process (Theorem 2.14 in baby Rudin if anybody's interested), we can say that since the set of all sequences whose elements are 0's and 1's are uncountable, A is also uncountable.

Thanks in advance!