g: P(N)-->(0,1)

**novice** · May 17th 2010, 05:03 PM

I am reading the proof for the following theorem:

The sets $P(\mathbb{N})$ and $\mathbb{R}$ are numerically equivalent.

I understood the part where the author proved the existence of the one-to-one function $f: (0,1) \rightarrow P(\mathbb{N})$ , but I find it hard to understand the converse; i.e., the proof of the existence of the one-to-one function $g: P(\mathbb{N})\rightarrow (0,1)$ .

It says as follows :

We define a function $g: P(\mathbb{N}) \rightarrow (0,1)$ . For $S\subseteq \mathbb{N}$ , define $g(S)=0.s_1s_2s_3\cdot\cdot\cdot$ , where

$S_n=\left\{ \begin{array}{rcl} 1 & \mbox{if}&n\in S\\ 2&\mbox{if} & n \notin S \end{array}\right.$

Thus $g(S)$ is a real number in (0,1), whose decimal expansion consists only of 1s and 2s.

and it continues to show that $g$ is one-to-one.

Question: Let's say $S=\{1,2,3,...,n\}$ . What do the first two numbers look like? Please show examples.

**Defunkt** · May 17th 2010, 05:27 PM

Originally Posted by novice

I am reading the proof for the following theorem:

The sets $P(\mathbb{N})$ and $\mathbb{R}$ are numerically equivalent.

I understood the part where the author proved the existence of the one-to-one function $f: (0,1) \rightarrow P(\mathbb{N})$ , but I find it hard to understand the converse; i.e., the proof of the existence of the one-to-one function $g: P(\mathbb{N})\rightarrow (0,1)$ .

It says as follows :

and it continues to show that $g$ is one-to-one.

Question: Let's say $S=\{1,2,3,...,n\}$ . What do the first two numbers look like? Please show examples.

This function makes no sense. What is f? What is z???

I am guessing the function you meant is this one:

$g:P(\mathbb{N}) \to (0,1)$ defined by $g(S) = 0.g_1g_2...g_ng_{n+1}...$

with $g_i=\left\{ \begin{array}{rcl} 1 & \mbox{if}&i\in S\\ 2&\mbox{if} & i \notin S \end{array}\right.$

And so if we have $S_0 = \{1,2,...,n\}$ , then $g(S) = 0.\underbrace{11...1}_{\text{n times}}222...$

**novice** · May 17th 2010, 06:20 PM

Originally Posted by Defunkt

This function makes no sense. What is f? What is z???

I feel terribly sorry. It was very sloppy of me.
It should have been

$S_n=\left\{ \begin{array}{rcl} 1 & \mbox{if}&n\in S\\ 2&\mbox{if} & n \notin S \end{array}\right.$

**novice** · May 17th 2010, 06:26 PM

Originally Posted by Defunkt

This function makes no sense. What is f? What is z???

I am guessing the function you meant is this one:

$g:P(\mathbb{N}) \to (0,1)$ defined by $g(S) = 0.g_1g_2...g_ng_{n+1}...$

with $g_i=\left\{ \begin{array}{rcl} 1 & \mbox{if}&i\in S\\ 2&\mbox{if} & i \notin S \end{array}\right.$

And so if we have $S_0 = \{1,2,...,n\}$ , then $g(S) = 0.\underbrace{11...1}_{\text{n times}}222...$

You guessed it right, sir. I understand it fully now.

**Drexel28** · May 17th 2010, 06:31 PM

Originally Posted by novice

I feel terribly sorry. It was very sloppy of me.
It should have been

$S_n=\left\{ \begin{array}{rcl} 1 & \mbox{if}&n\in S\\ 2&\mbox{if} & n \notin S \end{array}\right.$

What's wrong? The idea is to map a set $U\subseteq\mathbb{N}$ to a decimal where each decimal place indicates whether the number is in there or not.

So, what we're really saying is that $f:\mathcal{P}(\mathbb{N})\to(0,1):U\mapsto\sum_{n= 1}^{\infty}\frac{a_n}{10^n}$ where $a_n=\begin{cases} 1\quad\text{if}\quad n\in U\\ 2 \quad\text{if}\quad n\notin U\end{cases}$ . So, if $U\ne V$ then we may assume WLOG that $m\in U\cap V'$ and thus $\left|f(U)-f(V)\right|=\left|\sum_{n=1}^{\infty}\frac{a_n}{10 ^n}-\sum_{n=1}^{\infty}\frac{b_n}{10^n}\right|\geqslan t |a_m-b_m|\geqslant\frac{1}{10^m}$ . Thus, $f(U)\ne f(V)$

**novice** · May 18th 2010, 06:44 AM

This part looks very interesting.

Originally Posted by Drexel28

So, what we're really saying is that $f:\mathcal{P}(\mathbb{N})\to(0,1):U\mapsto\sum_{n= 1}^{\infty}\frac{a_n}{10^n}$ where $a_n=\begin{cases} 1\quad\text{if}\quad n\in U\\ 2 \quad\text{if}\quad n\notin U\end{cases}$ . So, if $U\ne V$ then we may assume WLOG that $m\in U\cap V'$ and thus $\left|f(U)-f(V)\right|=\left|\sum_{n=1}^{\infty}\frac{a_n}{10 ^n}-\sum_{n=1}^{\infty}\frac{b_n}{10^n}\right|\geqslan t |a_m-b_m|\geqslant\frac{1}{10^m}$ . Thus, $f(U)\ne f(V)$

In particular, $\sum_{n=1}^{\infty}\frac{a_n}{10^n}$ . Had the author of my book showed it as you did, I would not have trouble understanding it.
What are the $U,V,m$ and $b$ ?

**Drexel28** · May 18th 2010, 07:44 AM

Originally Posted by novice

This part looks very interesting.
In particular, $\sum_{n=1}^{\infty}\frac{a_n}{10^n}$ . Had the author of my book showed it as you did, I would not have trouble understanding it.
What are the $U,V,m$ and $b$ ?

$U,V\in\mathcal{P}(\mathbb{N})$ are jus arbitrary subsets of the naturals. We are trying to show that if two subsets of the naturals aren't equal that their image under $f$ isn't equal. I jused $b_n$ to mean the same thing as $a_n$ but to indicate that it was for $V$ and not $U$ .

$m$ is just some point that is in $U$ or $V$ (I assumed WLOG above that $m\in U$ ) which isn't in the other. We know there must be at least one since the two sets aren't equal.

**tonio** · May 18th 2010, 08:40 AM

Originally Posted by novice

I am reading the proof for the following theorem:

The sets $P(\mathbb{N})$ and $\mathbb{R}$ are numerically equivalent.

I understood the part where the author proved the existence of the one-to-one function $f: (0,1) \rightarrow P(\mathbb{N})$ , but I find it hard to understand the converse; i.e., the proof of the existence of the one-to-one function $g: P(\mathbb{N})\rightarrow (0,1)$ .

It says as follows :

and it continues to show that $g$ is one-to-one.

Question: Let's say $S=\{1,2,3,...,n\}$ . What do the first two numbers look like? Please show examples.

..

Thread: g: P(N)-->(0,1)

LinkBack

Thread Tools

Display

g: P(N)-->(0,1)

Search Tags