Let $\mathbb{N} = \{0,1,2,3,...\}$ be the set of natural numbers (with $0$) and $\mathbb{F}$ the set of finite parts of $\mathbb{N}$. I want to find a bijection, as simple as possible, between $\mathbb{N}$ and $\mathbb{F}$. One that I have is $$f : \mathbb{F} \to \mathbb{N}, s \mapsto \sum_{i\in s} 2^i$$ with the convention that the sum over $\emptyset$ is $0$. Do you have other examples which are perhaps more elementary ?
$\begingroup$
$\endgroup$
2
-
7$\begingroup$ I find your example extremely elementary. The opposite map is, of course, write the number $n\in\mathbb N$ in binary and then pick the subset of those numbers in $\mathbb N$ that correspond to the positions of the digits "$1$" (from the right). Say, the number $23_{10}=10111_2$ corresponds to the subset $\{0,1,2,4\}$. $\endgroup$– user700480Commented Jun 20, 2023 at 12:55
-
1$\begingroup$ @user700974 Could you explain the phrase "finite parts of $\mathbb{N}$"? I don't think I have ever came across such a terminology. By any chance do you mean the set of all finite subsets of $\mathbb{N}$? $\endgroup$– KaleBhodreCommented Jun 22, 2023 at 23:07
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
The example you give is very elementary. In fact, it is, in a way, “as simple as possible.”
For all $n$, there are $2^{n}$ subsets of $\{0,1,\dots, n-1\}$. Your bijection maps these $2^{n}$ subsets precisely onto the numbers in the set $\{0,1, \dots, 2^{n}-1\}$.
So, we can informally say that your bijection never sends any subsets to numbers larger than it needs to.
