Results 1 to 8 of 8

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

  1. #1
    Banned
    Joined
    Sep 2009
    Posts
    502

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

    I am reading the proof for the following theorem:

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

    I understood the part where the author proved the existence of the one-to-one function $\displaystyle 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 $\displaystyle g: P(\mathbb{N})\rightarrow (0,1)$.

    It says as follows :


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

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

    Thus $\displaystyle g(S)$ is a real number in (0,1), whose decimal expansion consists only of 1s and 2s.
    and it continues to show that $\displaystyle g$ is one-to-one.

    Question: Let's say $\displaystyle S=\{1,2,3,...,n\}$. What do the first two numbers look like? Please show examples.
    Last edited by novice; May 18th 2010 at 02:07 PM. Reason: Fix typo
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member
    Joined
    Aug 2009
    From
    Israel
    Posts
    976
    Quote Originally Posted by novice View Post
    I am reading the proof for the following theorem:

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

    I understood the part where the author proved the existence of the one-to-one function $\displaystyle 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 $\displaystyle g: P(\mathbb{N})\rightarrow (0,1)$.

    It says as follows :


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

    Question: Let's say $\displaystyle 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:

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

    with $\displaystyle 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 $\displaystyle S_0 = \{1,2,...,n\}$, then $\displaystyle g(S) = 0.\underbrace{11...1}_{\text{n times}}222...$
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Banned
    Joined
    Sep 2009
    Posts
    502
    Quote Originally Posted by Defunkt View Post
    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

    $\displaystyle S_n=\left\{ \begin{array}{rcl}
    1 & \mbox{if}&n\in S\\
    2&\mbox{if} & n \notin S
    \end{array}\right.$
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Banned
    Joined
    Sep 2009
    Posts
    502
    Quote Originally Posted by Defunkt View Post
    This function makes no sense. What is f? What is z???


    I am guessing the function you meant is this one:

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

    with $\displaystyle 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 $\displaystyle S_0 = \{1,2,...,n\}$, then $\displaystyle g(S) = 0.\underbrace{11...1}_{\text{n times}}222...$
    You guessed it right, sir. I understand it fully now.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor Drexel28's Avatar
    Joined
    Nov 2009
    From
    Berkeley, California
    Posts
    4,563
    Thanks
    22
    Quote Originally Posted by novice View Post
    I feel terribly sorry. It was very sloppy of me.
    It should have been

    $\displaystyle 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 $\displaystyle 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 $\displaystyle f:\mathcal{P}(\mathbb{N})\to(0,1):U\mapsto\sum_{n= 1}^{\infty}\frac{a_n}{10^n}$ where $\displaystyle a_n=\begin{cases} 1\quad\text{if}\quad n\in U\\ 2 \quad\text{if}\quad n\notin U\end{cases}$. So, if $\displaystyle U\ne V$ then we may assume WLOG that $\displaystyle m\in U\cap V'$ and thus $\displaystyle \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, $\displaystyle f(U)\ne f(V)$
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Banned
    Joined
    Sep 2009
    Posts
    502
    This part looks very interesting.
    Quote Originally Posted by Drexel28 View Post

    So, what we're really saying is that $\displaystyle f:\mathcal{P}(\mathbb{N})\to(0,1):U\mapsto\sum_{n= 1}^{\infty}\frac{a_n}{10^n} $ where $\displaystyle a_n=\begin{cases} 1\quad\text{if}\quad n\in U\\ 2 \quad\text{if}\quad n\notin U\end{cases}$. So, if $\displaystyle U\ne V$ then we may assume WLOG that $\displaystyle m\in U\cap V'$ and thus $\displaystyle \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, $\displaystyle f(U)\ne f(V)$
    In particular, $\displaystyle \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 $\displaystyle U,V,m$ and $\displaystyle b$?
    Follow Math Help Forum on Facebook and Google+

  7. #7
    MHF Contributor Drexel28's Avatar
    Joined
    Nov 2009
    From
    Berkeley, California
    Posts
    4,563
    Thanks
    22
    Quote Originally Posted by novice View Post
    This part looks very interesting.
    In particular, $\displaystyle \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 $\displaystyle U,V,m$ and $\displaystyle b$?
    $\displaystyle 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 $\displaystyle f$ isn't equal. I jused $\displaystyle b_n$ to mean the same thing as $\displaystyle a_n$ but to indicate that it was for $\displaystyle V$ and not $\displaystyle U$.

    $\displaystyle m$ is just some point that is in $\displaystyle U$ or $\displaystyle V$ (I assumed WLOG above that $\displaystyle m\in U$) which isn't in the other. We know there must be at least one since the two sets aren't equal.
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Banned
    Joined
    Oct 2009
    Posts
    4,261
    Thanks
    3
    Quote Originally Posted by novice View Post
    I am reading the proof for the following theorem:

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

    I understood the part where the author proved the existence of the one-to-one function $\displaystyle 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 $\displaystyle g: P(\mathbb{N})\rightarrow (0,1)$.

    It says as follows :


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

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

    ..
    Last edited by tonio; May 18th 2010 at 08:41 AM. Reason: Asking that was already answered...
    Follow Math Help Forum on Facebook and Google+

Search Tags


/mathhelpforum @mathhelpforum