Uniquely identify any finite subset of an infinite set

Question

Let $U$ be an unbounded subset of $\mathbb{N}$.

Let $D = \mathcal{P}_{<\omega}(U)$ (the set of all finite subsets of $U$).

Let $f$ be an injection such that: $f: D \rightarrow \mathbb{N} $

Intuitively: let $f$ be a function that uniquely assigns a natural number to an arbitrarily long set.

I can think of three interesting examples of $f$:

Prime products

Let $U$ be the set of all prime numbers. Let $f$ be a function that outputs a product of all elements of the argument.

For example: $f(\{2, 3, 11\}) = 2\times3\times11 = 66$

No two distinct prime sets may ever produce duplicate numbers, due to the fundamental theorem of arithmetic. Therefore, $f$ is injective.

Power sums

Let $U = \mathbb{N}$

Let $b\in\mathbb{N}, b > 1 $

Let $A\in{D}$

$$f_{b}(A) = \sum_{a \in A} b^{a} $$

For example: $f_{2}(\{4, 5, 8\}) = 2^4 + 2^5 + 2^8 = 304$

We can treat any argument of $f_{b}$ as a number in base $b$ such that each element of the argument signifies the position at which we place digit $1$. Therefore:

$f_{2}(\{4, 5, 8\}) = 100110000_{2} = 304_{10}$

As such, $f_{b}$ is injective for every specified $b$.

Factorial sums

Let $U = \mathbb{N}$ and let $f$ be a function that outputs a sum of factorials of all elements of the argument.

For example: $f(\{4, 5, 8\}) = 4! + 5! + 8! = 40464$

Since the factorial number system uniquely represents any positive integer, we can treat any argument of $f$ as a number such that each element of the argument signifies the position at which we place digit $1$. So:

$f(\{4, 5, 8\}) = 1_{9}0_{8}0_{7}1_{6}1_{5}0_{4}0_{3}0_{2}0_{1} = 40464_{10}$

As such, $f$ is injective. (Note that the place value is one less than the radix position)

First question: What other interesting examples of $f$ do we know that are not necessarily sums of powers? Is there a way to describe what such a function can and cannot be? Is it any easier should we extend the codomain of $f$ to $\mathbb{R}$?

Second question: If we define $D$ as the set of all possible multisets (instead of subsets) such that every element of the multiset is inside $U$, has mankind discovered any working example of $f$ apart from the prime products example?

Answer 1

Yes, there is indeed a bijection $R$ ("Ranking function") from the set of all finite multisubsets of $\mathbb{N^{+}}$ to $\mathbb{N^{+}}$.

To show this we will prove that its inverse $R^{-1}$ ("Unranking function") is bijective. Here's what it looks like by the way:

R^-1(1) = { 1 }
R^-1(2) = { 2 }
R^-1(3) = { 1 1 }
R^-1(4) = { 3 }
R^-1(5) = { 1 2 }
R^-1(6) = { 2 2 }
R^-1(7) = { 1 1 1 }
R^-1(8) = { 4 }
R^-1(9) = { 1 3 }
R^-1(10) = { 2 3 }
R^-1(11) = { 3 3 }
R^-1(12) = { 1 1 2 }
R^-1(13) = { 1 2 2 }
R^-1(14) = { 2 2 2 }
R^-1(15) = { 1 1 1 1 }
R^-1(16) = { 5 }
R^-1(17) = { 1 4 }
R^-1(18) = { 2 4 }
R^-1(19) = { 3 4 }
R^-1(20) = { 4 4 }
R^-1(21) = { 1 1 3 }
R^-1(22) = { 1 2 3 }
R^-1(23) = { 1 3 3 }
R^-1(24) = { 2 2 3 }
R^-1(25) = { 2 3 3 }
R^-1(26) = { 3 3 3 }
R^-1(27) = { 1 1 1 2 }
R^-1(28) = { 1 1 2 2 }
R^-1(29) = { 1 2 2 2 }
R^-1(30) = { 2 2 2 2 }
R^-1(31) = { 1 1 1 1 1 }
R^-1(32) = { 6 }
R^-1(33) = { 1 5 }
R^-1(34) = { 2 5 }
R^-1(35) = { 3 5 }
R^-1(36) = { 4 5 }
R^-1(37) = { 5 5 }
R^-1(38) = { 1 1 4 }
R^-1(39) = { 1 2 4 }
R^-1(40) = { 1 3 4 }
R^-1(41) = { 1 4 4 }
R^-1(42) = { 2 2 4 }
R^-1(43) = { 2 3 4 }
R^-1(44) = { 2 4 4 }
R^-1(45) = { 3 3 4 }
R^-1(46) = { 3 4 4 }
R^-1(47) = { 4 4 4 }
R^-1(48) = { 1 1 1 3 }
R^-1(49) = { 1 1 2 3 }
R^-1(50) = { 1 1 3 3 }
R^-1(51) = { 1 2 2 3 }
R^-1(52) = { 1 2 3 3 }
R^-1(53) = { 1 3 3 3 }
R^-1(54) = { 2 2 2 3 }
R^-1(55) = { 2 2 3 3 }
R^-1(56) = { 2 3 3 3 }
R^-1(57) = { 3 3 3 3 }
R^-1(58) = { 1 1 1 1 2 }
R^-1(59) = { 1 1 1 2 2 }
R^-1(60) = { 1 1 2 2 2 }
R^-1(61) = { 1 2 2 2 2 }
R^-1(62) = { 2 2 2 2 2 }
R^-1(63) = { 1 1 1 1 1 1 }
R^-1(64) = { 7 }
R^-1(65) = { 1 6 }
R^-1(66) = { 2 6 }
R^-1(67) = { 3 6 }
R^-1(68) = { 4 6 }
R^-1(69) = { 5 6 }
R^-1(70) = { 6 6 }
R^-1(71) = { 1 1 5 }
R^-1(72) = { 1 2 5 }
R^-1(73) = { 1 3 5 }
R^-1(74) = { 1 4 5 }
R^-1(75) = { 1 5 5 }
R^-1(76) = { 2 2 5 }
R^-1(77) = { 2 3 5 }
R^-1(78) = { 2 4 5 }
R^-1(79) = { 2 5 5 }
R^-1(80) = { 3 3 5 }
R^-1(81) = { 3 4 5 }
R^-1(82) = { 3 5 5 }
R^-1(83) = { 4 4 5 }
R^-1(84) = { 4 5 5 }
R^-1(85) = { 5 5 5 }
R^-1(86) = { 1 1 1 4 }
R^-1(87) = { 1 1 2 4 }
R^-1(88) = { 1 1 3 4 }
R^-1(89) = { 1 1 4 4 }
R^-1(90) = { 1 2 2 4 }
R^-1(91) = { 1 2 3 4 }
R^-1(92) = { 1 2 4 4 }
R^-1(93) = { 1 3 3 4 }
R^-1(94) = { 1 3 4 4 }
R^-1(95) = { 1 4 4 4 }
R^-1(96) = { 2 2 2 4 }
R^-1(97) = { 2 2 3 4 }
R^-1(98) = { 2 2 4 4 }
R^-1(99) = { 2 3 3 4 }
R^-1(100) = { 2 3 4 4 }
R^-1(101) = { 2 4 4 4 }
R^-1(102) = { 3 3 3 4 }
R^-1(103) = { 3 3 4 4 }
R^-1(104) = { 3 4 4 4 }
R^-1(105) = { 4 4 4 4 }
R^-1(106) = { 1 1 1 1 3 }
R^-1(107) = { 1 1 1 2 3 }
R^-1(108) = { 1 1 1 3 3 }
R^-1(109) = { 1 1 2 2 3 }
R^-1(110) = { 1 1 2 3 3 }
R^-1(111) = { 1 1 3 3 3 }
R^-1(112) = { 1 2 2 2 3 }
R^-1(113) = { 1 2 2 3 3 }
R^-1(114) = { 1 2 3 3 3 }
R^-1(115) = { 1 3 3 3 3 }
R^-1(116) = { 2 2 2 2 3 }
R^-1(117) = { 2 2 2 3 3 }
R^-1(118) = { 2 2 3 3 3 }
R^-1(119) = { 2 3 3 3 3 }
R^-1(120) = { 3 3 3 3 3 }
R^-1(121) = { 1 1 1 1 1 2 }
R^-1(122) = { 1 1 1 1 2 2 }
R^-1(123) = { 1 1 1 2 2 2 }
R^-1(124) = { 1 1 2 2 2 2 }
R^-1(125) = { 1 2 2 2 2 2 }
R^-1(126) = { 2 2 2 2 2 2 }
R^-1(127) = { 1 1 1 1 1 1 1 }
R^-1(128) = { 8 }
R^-1(129) = { 1 7 }
R^-1(130) = { 2 7 }
R^-1(131) = { 3 7 }
R^-1(132) = { 4 7 }
R^-1(133) = { 5 7 }
R^-1(134) = { 6 7 }
R^-1(135) = { 7 7 }
R^-1(136) = { 1 1 6 }
R^-1(137) = { 1 2 6 }
R^-1(138) = { 1 3 6 }
R^-1(139) = { 1 4 6 }
R^-1(140) = { 1 5 6 }

Can you already spot the rule? If not, read on!

Indexed collections of multisets

Let $m, n, l \in \mathbb{N^{+}}.$

Let $$F(n, l) = \{M: |M| = l \wedge m \in M \Rightarrow m \leq n \wedge n \in M \} $$ Intuitively: let $F(n, l) $ be a collection of multisets $M$ of length $l$ where every element is less than or equal to $n$ and there's at least one $n$ inside $M$ (simply: $F(n, l) = $ multisets of length $l$ whose maximal element is $n$).

Examples: $$F(2, 3) = \{\{1, 1, 2\}, \{1, 2, 2\}, \{2, 2, 2\}\}$$ $$F(4, 2) = \{\{1, 4\},\{2, 4\},\{3, 4\},\{4, 4\}\}$$

Let $\mathbb{M}$ denote the set of all finite multisubsets of $\mathbb{N^{+}}$.

Notice that for every $M \in \mathbb{M}$ we can find a collection $F(n, l)$ that it belongs to.

We find $n, l$ as follows:

• $l$ is simply the length of $M$;
• $n$ is simply the maximal element of $M$.

This way all three conditions for $F(n, l)$ hold.

Now notice that every $M \in \mathbb{M}$ belongs to exactly one collection $F(n, l)$.

It's because if $M$, for which we've found some working $n, l$, could belong to some other $F(a, b), a \neq n \vee b \neq l $, it would mean that either

• it can have some other length $b$ at the same time, which obviously cannot be, or
• $a < n$ which cannot be because $n$ being inside $M$ breaks the other collection's rule $m \in M \Rightarrow m \leq a$, or
• $a > n$ which cannot be because (tautologically) $M$ contains no bigger element than its maximal element $n$ - thus it can't contain such $a$. If it can't contain $a$, it doesn't fulfill the other collection's condition $a \in M$.

Concatenating all collections

Now, consider an infinite sequence of collections $$C = (F(1, 1), F(2, 1), F(1, 2), F(3, 1), F(2, 2), F(1, 3), F(4, 1), F(3, 2)...)$$

To obtain $C_{n}$, which is the $nth$ element of this sequence, we construct $F(x, y)$ such that:

1. We list terms of consecutive arithmetic progressions in decreasing order and $x$ is the $nth$ element of such a list.
2. We do the same but with arithmetic progressions in increasing order and $y$ is the $nth$ element of such a list.

Notice that for any $a, b \in \mathbb{N^{+}}$, there is exactly one occurence of $F(a, b)$ in $C$.

Now if $S$ is some set of some multisets, let $L(S, k)$ denote the $kth$ element (that is a multiset) taken from $S$ in lexicographical order.

Let us define a helper function $g$:

$$g(n, i) = \begin{equation} \begin{cases} L(C_{i}, n) & \text{if}\ n \leq |C_{i}| \\ g(n - |C_{i}|, i+1) & \text{otherwise} \end{cases} \end{equation} $$

We can then define our multiset unranking function (the one whose values I've listed at the beginning): $$R^{-1}: \mathbb{N^{+}} \rightarrow \mathbb{M} $$ $$R^{-1}(n) = g(n, 1)$$

Intuitively: we list all multisets of all collections in order specified by $C$ in a single row and we take the $nth$ multiset from the list. Example: if the first four collections have $1$ multiset each and the fifth one has $2$, then $R^{-1}(4)$ maps to the only element of the fourth collection, $R^{-1}(5)$ maps to lexicographically first element of the fifth collection and $R^{-1}(6)$ maps to lexicographically second element of the fifth collection.

As we increase $n$, we eventually obtain every element of every $F(a, b)$ for every possible pair of positive integers $(a, b)$.

Since we've proven that every $M \in \mathbb{M}$ belongs to some $F(a, b)$, we see that $R^{-1}$ is onto, because we will eventually find this $M$ by increasing $n$.

Since we've proven that every $M \in \mathbb{M}$ belongs to one $F(a, b)$ and elements of a particular $F(a, b)$ cannot repeat (by definition of set), $R^{-1}$ is injective, because two inequal arguments of $R^{-1}$ map to either different elements of different collections or different elements of the same collection.

It follows immediately that there exists a function $R: \mathbb{M} \rightarrow \mathbb{N^{+}} $ which is obviously injective as well and whose existence answers the original question.

Curio: comparing $R^{-1}$ with prime factorizations

Let $D = \mathbb{N^{+}} \setminus \{1\}$

We can trivially observe that a function $f^{-1}$ that takes some $n$ and outputs a multiset with ordinals of primes that factorize $n$ is a bijection $$f^{-1}: D \rightarrow \mathbb{M} $$

Examples: $$f^{-1}(10) = f^{-1}(2 \times 5) = \{1,3\}$$ $$f^{-1}(18) = f^{-1}(2 \times 3 \times 3) = \{1,2,2\}$$

It kind of unranks an integer into a finite multisubset of $\mathbb{N^{+}}$.

Sounds familiar? Now what if we compare results of $f^{-1}$ and $R^{-1}$? Could there finally be some order in factorizations? To see this, let us define $f$: $$f: \mathbb{M} \rightarrow D $$ $$f(M) = \prod_{m \in M} p_{m} $$

Obviously, $f(f^{-1}(n)) = n$, for $n \in D$.

How about $f(R^{-1}(n))$ for $n \in \mathbb{N^{+}}$?

Here's the plot of this:

Notable properties:

1. $f(R^{-1}(n)) = n + 1$ for $1 \leq n \leq 5$
2. $f(R^{-1}(n)) = n + 1$ for $n + 1$ being a positive power of $2$.

Otherwise chaos, unfortunately. Or maybe we do not yet have eyes to see order?