(adsbygoogle = window.adsbygoogle || []).push({}); 1. The problem statement, all variables and given/known data

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

2. Relevant equations

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

3. 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!

**Physics Forums | Science Articles, Homework Help, Discussion**

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

# Homework Help: Set of all Subsets of Natural Numbers

**Physics Forums | Science Articles, Homework Help, Discussion**