Results 1 to 8 of 8
Like Tree2Thanks
  • 1 Post By Plato
  • 1 Post By SlipEternal

Thread: Find an injective map

  1. #1
    Newbie
    Joined
    Aug 2018
    From
    Denmark
    Posts
    15

    Find an injective map

    Hey,

    I am considering the set $\displaystyle \mathcal{P}_{k}(\mathbb{N})$ which is the set of subsets of $\displaystyle \mathbb{N}$ with $\displaystyle k$ elements.

    I want to find a injective function $\displaystyle \phi_{k}:\mathcal{P}_{k}(\mathbb{N}) \rightarrow \mathbb{N}^{k}$.

    Suggestions ppreciated.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Aug 2006
    Posts
    22,034
    Thanks
    2946
    Awards
    1

    Re: Find an injective map

    Quote Originally Posted by detalosi View Post
    Hey,

    I am considering the set $\displaystyle \mathcal{P}_{k}(\mathbb{N})$ which is the set of subsets of $\displaystyle \mathbb{N}$ with $\displaystyle k$ elements.

    I want to find a injective function $\displaystyle \phi_{k}:\mathcal{P}_{k}(\mathbb{N}) \rightarrow \mathbb{N}^{k}$.

    Suggestions ppreciated.
    What does the notation $\mathbb{N}^{k}$ mean? I hate to guess and be wrong. That is a waste of effort.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Aug 2018
    From
    Denmark
    Posts
    15

    Re: Find an injective map

    I understand it to be the set of subsets of $\displaystyle \mathbb{N}$ with no more than $\displaystyle k$ elements.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor

    Joined
    Aug 2006
    Posts
    22,034
    Thanks
    2946
    Awards
    1

    Re: Find an injective map

    Quote Originally Posted by detalosi View Post
    I understand it to be the set of subsets of $\displaystyle \mathbb{N}$ with no more than $\displaystyle k$ elements.
    Well, I would never have guessed that. If that is correct then $\mathcal{P}_k(\mathbb{N})\subset \mathbb{N}^k$.
    So that the problem is trivial, use the identity mapping.

    BTW I doubt that is what the notation means.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Newbie
    Joined
    Aug 2018
    From
    Denmark
    Posts
    15

    Re: Find an injective map

    I have the following.

    Consider the set of k natural numbers $\displaystyle B= \left\{ 1,2,3,...,k \right\}$ where $\displaystyle x_{1}<x_{2}<x_{3}<...<x_{k}$.

    Then I define the function $\displaystyle \psi_{k}(B)= (x_{1},x_{2},x_{3},...,x_{3})$.

    This function is injective.

    Questions: what is the difference betjene the set $\displaystyle \mathcal{P}_{k}(\mathbb{N})$ and the set $\displaystyle \mathbb{N}^{k}$?
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor

    Joined
    Aug 2006
    Posts
    22,034
    Thanks
    2946
    Awards
    1

    Re: Find an injective map

    Quote Originally Posted by detalosi View Post
    Questions: what is the difference betjene the set $\displaystyle \mathcal{P}_{k}(\mathbb{N})$ and the set $\displaystyle \mathbb{N}^{k}$?
    I told you that I doubted that your understanding of that notation was correct.
    To get an answer you should ask your instructor or read the text closely.

    If I were guessing, $\prod\limits_{i = 1}^k \mathbb{N} $, i.e. the set of all k-tuples with natural number entries.
    Thanks from detalosi
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Newbie
    Joined
    Aug 2018
    From
    Denmark
    Posts
    15

    Re: Find an injective map

    Yes, I might have been wrong, but I searched the internet for the explanation. It is not possible for me to ask my instructor for the time being.

    I don't understand you answer. Allow me to state the problem in order to avoid any misunderstanding on my part.

    The exercise states the following:

    Q1)
    Explain that the set $\displaystyle \mathcal{P}(\mathbb{N})$ of all subsets of $\displaystyle \mathbb{N}$ is unacountable.

    A1)
    I have shown this using Cantor's diagonal method.

    Q2)
    Let $\displaystyle \mathcal{P}_{fin}(\mathbb{N})$ be the set of all finite subsets of $\displaystyle \mathbb{N}$. Furthermore let $\displaystyle \mathcal{P}_{k}(\mathbb{N})$ for $\displaystyle k>0$ be the set of subsets of $\displaystyle \mathbb{N}$ with exactly $\displaystyle k$ elements.
    Find an injective map $\displaystyle f_{k}: \mathcal{P}(\mathbb{N}) \rightarrow \mathbb{N}^{k} $ for every $\displaystyle k>0$

    A2)
    This is where I need help.
    You stated, that I could use the identity map. So if I consider a map which takes members of $\displaystyle \mathcal{P}_{fin}(\mathbb{N})$ (say a set with 3 subsets) then the map would give back the ordered triple $\displaystyle (x_{1}, x_{2}, x_{3})$. This would constitute an identity-map which is injective. By construction the map I presented above is injective.

    Would you agree with this?
    Follow Math Help Forum on Facebook and Google+

  8. #8
    MHF Contributor
    Joined
    Nov 2010
    Posts
    3,683
    Thanks
    1492

    Re: Find an injective map

    You have a set of $k$ elements. You are calling them $x_1<x_2<\cdots < x_k$. This is the set $\{x_1,x_2,\ldots, x_k\}$. Plato suggested the map:

    $$\{x_1,x_2,\ldots, x_k\} \mapsto (x_1,x_2,\ldots, x_k)$$

    The question is, is this function injective? You want to show that

    $$\{x_1,x_2,\ldots, x_k\} \mapsto (z_1,z_2,\ldots, z_k)$$

    and

    $$\{y_1,y_2,\ldots, y_k\} \mapsto (z_1,z_2,\ldots, z_k)$$

    Then

    $$\{x_1,x_2,\ldots, x_k\} = \{y_1,y_2,\ldots, y_k\}$$

    This is trivial because of the well-ordering principle of Natural Numbers. You can put any subset of natural numbers in order, and that ordering allows the mapping to be injective. Basically, the process takes the least element of the set and put it in the first position of the tuple. Then, you drop that element and consider the subset with one fewer elements. It will again have a least element, and that gets mapped to the second spot. Keep going until you get the $k$-th spot of the tuple to complete the mapping.
    Last edited by SlipEternal; Oct 4th 2018 at 08:19 AM.
    Thanks from detalosi
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Is f injective or not?
    Posted in the New Users Forum
    Replies: 9
    Last Post: Sep 15th 2012, 11:22 PM
  2. f: [0,1]-->]0,1[, f injective
    Posted in the Calculus Forum
    Replies: 5
    Last Post: Oct 1st 2010, 09:08 AM
  3. Injective
    Posted in the Differential Geometry Forum
    Replies: 1
    Last Post: Oct 1st 2010, 03:15 AM
  4. If gof is injective, then f is injective
    Posted in the Differential Geometry Forum
    Replies: 4
    Last Post: Oct 17th 2009, 11:10 PM
  5. g(f(x) is injective, is f injective?
    Posted in the Discrete Math Forum
    Replies: 11
    Last Post: Nov 9th 2008, 07:23 PM

/mathhelpforum @mathhelpforum