Can i prove the |P(Z+)}=|(0,1)| list like that?

Question

First of all,in diagonalization prove,we can always generate the a real number that not in the list by adding one to the value of the diagonal.

In power set of positive integer,if we use the real number as domain,the power set of positive integer be the codomim,lets r1,r2,r3.... is real number,then we will have:

we can always generate subset of positive integer that not in list by {x∈Z+|x∉f(x)}

Since they both generate the infinity of element,there always have real number map to subset of positive integer,so their cardinality are the same.Can i prove like that?Why or why not?

Answer 1

In the diagonal argument, what you actually prove is that if $f$ is a map $\Bbb N \to S$, where $S$ is $\mathscr P(\Bbb N)$ or $[0,1]\subset \Bbb R$, then $f$ cannot be surjective.

This implies that $\mathscr P(\Bbb N)$ and $[0,1]$ (and therefore $\Bbb R$) are uncountable, since countability means that there is a bijection between the set and $\Bbb N$, and any bijection must be a surjection.

It does not in any way give a mapping of real numbers to $\mathscr P(\Bbb N)$.

The most common constructive way to prove that $|\mathscr P(\Bbb N)| = |\Bbb R|$ is to show

• $$2^\Bbb N \to \mathscr P(\Bbb N) : \{b_n\}_n^{\infty} \mapsto \{n\in \Bbb N \mid b_n = 1\}$$ is a bijection (where $2^\Bbb N$ is the set of all sequences in $\{0,1\}$ - that is, the set of all maps from $\Bbb N \to \{0,1\}$).
• The map $$ \Bbb R \to (0,1) : x \to \frac 12 + \frac x{2+2|x|}$$ is a bijection (actually, any strictly increasing map with horizontal asymptotes at $y = 0$ and $y = 1$ will work for this bijection).
• Let $S = \{ b = \{b_n\}_n^{\infty} \in 2^\Bbb N \mid (\exists N \in \Bbb N)(n > N \implies b_n = 1)\}$, let $\mathbf 0 \in 2^\Bbb N$ be the constant-zero sequence, and let $T = \{ t = \{t_n\}_n^{\infty} \in 2^\Bbb N \mid t \notin S \text{ and }t \ne \mathbf 0\}.$ Then the map $$T \to (0,1) : \{t_n\}_n^{\infty} \to \sum_{n=0}^\infty \frac {t_n}{2^{n+1}}$$ is a bijection. (This is just treating $\{t_n\}$ as the binary expansion of a real number in $(0,1)$. $\mathbf 0$ is removed because $0\notin (0,1)$, and the elements of $S$ give the alternate binary expansions of real numbers with terminating binary expansions, so they are removed to make the map injective.)
• There is a bijection between $2^\Bbb N$ and $T$.

The first three maps should be easy to see are bijections. The last one requires some chicanery.

First, note that $S$ is countable. In fact, if you define $$S_N = \{ \{s_n\}_n \in S \mid s_N = 0\text{ and }s_n =1\text{ for all }n > N\}$$ Then each $S_N$ is finite, and $S = \bigcup_N S_N$. Since $S$ is countable, there is bijection $f : \Bbb N \to S$.

Second, identify a sequence in $T$. For example $b = \{b_N\}_{N=0}^\infty$ where $$(b_N)_n = \begin{cases}1,&n = N\\0,&n \ne N\end{cases}$$ Define $g : 2^\Bbb N \to T$ by $$g(t) = \begin{cases}t,& t\in T, t \notin b\\ b_{2N},& t = b_N\\ b_1,& t = \mathbf 0\\ b_{2N + 3},& t = f(N)\end{cases}$$ $g$ is the desired bijection.