Is this a bijection between $V_{\omega+1}$ and the 2-adic numbers?

231 Views Asked by At

There exists the nice bijection by Ackermann from the set of hereditarily finite sets ($V_\omega$ in the von-Neumann hierarchy) to the natural numbers, $$f:V_\omega\to\mathbb N, M \mapsto f(M) = \sum_{X\in M} 2^{f(X)} \tag 1$$ (note that the function above is the inverse of the function given on the Wikipedia page).

Now I thought about whether that would be extensible to infinite sets. The next step in the von-Neumann hierarchy is, of course, $V_{\omega+1}$. Now if one naively applies the above formula to sets in $V_{\omega+1}$, one notices that one still gets sums of powers of $2$ (because their elements are all hereditarily finite), but there may be infinitely many of them in the sum.

But there happens to be a theory where exactly such sums appear: The 2-adic numbers. Therefore I conclude that the same formula, applied to elements of $V_{\omega+1}$ instead of $V_\omega$, gives a mapping to the $2$-adic numbers (of course the sum has to be interpreted as 2-adic sum instead of natural number sum in that case). It seems obvious that this mapping is surjective (as all possible sums of powers of $2$ occur). However I wonder: Is it also injective (and thus bijective), just as in the case of $V_\omega$?

1

There are 1 best solutions below

1
On

Actually, the mapping is not surjective for the $p$-adic numbers, but on the $p$-adic integers (back then, I overlooked that $p$-adic numbers can have negative exponents, which obviously cannot occur for the Ackermann numbering.

That the map to the $p$-adic integers is indeed a bijection can be seen as follows:

Be $A_k = \{x\in V_\omega: \max\{f(y):y\in x\}<k\}$. That is, the set of all hereditary finite sets all of whose elements have an Ackermann number less than $k$. Be further $\phi_{kl}:A_l\to A_k$ defined as $f_{kl}(x) = \{y\in x: .f(y)<k\}$. Then obviously the inverse limit of $A_k$ is $V_{\omega+1}$, with the projections $\pi_k:V_{\omega+1}\to A_k,x\mapsto\{y\in x:f(y)<k\}$.

On the other hand, it is not hard to check that $B_n:=\{f(x):x\in A_n\} = \{n\in\mathbb N:n<2^k\}$ and $\chi(n):=f(\phi_kl(f^{-1}(n)))\equiv n \pmod{2^k}$. That is, for each set $x$, the sequence $f(\pi_k(x))$ defines a sequence that in the inverse limit for $B_n$ gives, by definition, a $p$-adic integer.

Obviously different sets give different sequences, and therefore different $p$-adic integers. On the other hand, it is easily seen that every sequence of valid integers can be reached, since the finite sets ultimately correspond to the binary representation of the integers, and taking a number modulo $2^k$ just means taking the last $k$ binary digits.