Injective map $\phi _k :P_k (\mathbb{N})\rightarrow \mathbb{N}^k$

44 Views Asked by At

Let $\mathbb{P}_k (\mathbb{N})$ be the set of subsets of $\mathbb{N}$ with $k\geq 1$ elements.

Find an injective map $\phi _k :\mathbb{P}_k (\mathbb{N})\rightarrow \mathbb{N}^k$

(Beware, the sets $\{1,2\}$ and $\{2,1\}$ are identical so your map should be contructed such that $\phi _2 :(\{1,2\})=\phi _2 :(\{2,1\})$

1

There are 1 best solutions below

3
On BEST ANSWER

Given $S\subset\Bbb N$ of cardinality $k$, sort the elements in ascending order $a_1<a_2<\ldots <a_k$ and map to $(a_1,\ldots,a_k)$. This makes $\phi_2(\{1,2\})=\phi_2(\{2,1\})=(1,2)$.

Alternatively (i.e., without explicit sorting): Map to the elementary symmetric polynomials. In particular $\phi_2(\{x,y\})=(x+y,xy)$, $\phi_3(\{x,y,z\})=(x+y+z,yz+xz+xy,xyz)$, etc.