# Thread: Find an injective map

1. ## 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.

2. ## Re: Find an injective map

Originally Posted by detalosi
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.

3. ## 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.

4. ## Re: Find an injective map

Originally Posted by detalosi
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.

5. ## 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}$?

6. ## Re: Find an injective map

Originally Posted by detalosi
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.

If I were guessing, $\prod\limits_{i = 1}^k \mathbb{N}$, i.e. the set of all k-tuples with natural number entries.

7. ## 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?

8. ## 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.