Prove that the set consisting of all subsets(both finite and infinite) of set , P, of positive integers is uncountable using the following approach. First clearly P is countable so we can list all the integers in P and clearly map each element in this list into a subscript of its location in this list. Write down the first 10 elements in this list. Now suppose we can list all subsets of the set, P in another list. Write down an example first 10 elements of this list. Now neatly complete the argument to prove uncountability using both list.
[Math] finite and infinite subsets of positive integers
elementary-set-theory
Best Answer
Firstly show that there exists a bijection between $\mathscr P(P\text{ or }\Bbb N)$ and some uncountable set. This would mean that they have the same cardianality.
Take the set $[0,1]\subset\Bbb R$ it is uncountable. Now every real number in between $0$ and $1$ can be shown to be equivalent to a subset of $\Bbb N$ eg your $P$. This is easier to visualize in binary. We can construct a bijective function $\varphi:[0,1]\to\mathscr P(\Bbb N)$ such that $\varphi(0)=\varnothing$ and $\varphi(1\text{ or }0.1111\cdots)=\Bbb N$. Now represent$[0,1]\ni x=\sum^\infty_{n=1}\frac{b_n}{2^n}$ where $b_n$ repersents the nth binary digit now we can define $\varphi:0.b_1b_2b_3\cdots\mapsto\{n\in\Bbb N : b_n=1\}$ therefore for every binary number there is a corresponding subset of $\Bbb N$. You can rigorously show the bijectivity of $\varphi$ if you want. An example to make it clear would be $\varphi(0.010101\cdots)=\{2, 4, 6\cdots\}\tag*{$\square$}$