Results 1 to 8 of 8

Math Help - 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 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}<br />
1 & \mbox{if}&n\in S\\<br />
2&\mbox{if} & n \notin S<br />
\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.
    Last edited by novice; May 18th 2010 at 03: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 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}<br />
1 & \mbox{if}&i\in S\\<br />
2&\mbox{if} & i \notin S<br />
\end{array}\right.

    And so if we have S_0 = \{1,2,...,n\}, then 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

    S_n=\left\{ \begin{array}{rcl}<br />
1 & \mbox{if}&n\in S\\<br />
2&\mbox{if} & n \notin S<br />
\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:

    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}<br />
1 & \mbox{if}&i\in S\\<br />
2&\mbox{if} & i \notin S<br />
\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.
    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
    21
    Quote Originally Posted by novice View Post
    I feel terribly sorry. It was very sloppy of me.
    It should have been

    S_n=\left\{ \begin{array}{rcl}<br />
1 & \mbox{if}&n\in S\\<br />
2&\mbox{if} & n \notin S<br />
\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)
    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 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?
    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
    21
    Quote Originally Posted by novice View Post
    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.
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Banned
    Joined
    Oct 2009
    Posts
    4,261
    Thanks
    2
    Quote Originally Posted by novice View Post
    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.

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

Search Tags


/mathhelpforum @mathhelpforum