Home About
Canonical Bijections

Canonical Bijections

Idea

What are the most canonical bijections between two structures?

Binary

The most natural bijection $\phi:\mathbb{N}\mapsto \mathbb{B}$ where $\mathbb{B}=(\{1\}\times 2^*)\cup\{0\}$ [1][1] Note that the Kleene star in $2^*$ produces a set with an arbitrary amount of leading zeroes in each string, which, as binary expansions, are considered equivalent. Hence, by taking the cartesian product with $\{1\}$ we ensure a leading $1$. Because of this, we must append $0$ since it is the only expansion with no unit., is most certainly the base-2 expansion of natural numbers. This is due to the fact that all numbers can be uniquely decomposed into the sum of distinct powers of 2. In terms of our digit function, this is equivalent to $\phi_k(n)=D_2^k(n)$ (up to, perhaps, the reverse of the bits, depending on the situation). For example,

Generalizations

Properties

Applications

The utility of such a bijection is well known, for binary is apparent almost everywhere in computer science, information theory, and many other areas of mathematics.

Ackermann coding

One noteworthy nontrivial example is the use of Ackermann coding to enumerate all hereditarily finite sets (and with the generalizations, many infinite sets as well). As an alternative to von Neumann ordinals, we may define $0=\emptyset$, $1=\{0\}$, and $2=\{1\}$. Then, addition is defined recursively by $$A+B=2(A\cap B) + A \Delta B,$$ such that $0$ is the additive identity, where $A\Delta B$ is the symmetric difference. Multiplication is then simply defined by what is effectively the power rule $$\{a\}\{b\}=\{a+b\},$$ such that it distributes over addition. These minimal definitions are sufficient to prove the more general form of multiplication, $$AB=\sum_{a\in A}\{a+b:b\in b\}.$$ Metamathematically, our bijection serves as an indicator function, $$[k\in n]=\phi_k(n).$$

Positive integers to vectors of natural numbers

By the fundamental theorem of arithmetic, every natural number can be uniquely factored into a product of primes. Hence, we can construct the bijection $\phi:\mathbb{Z}^+\mapsto \mathbb{N}^{\mathbb{Z}^+}$[2][2] This is also isomorphic to $\mathbb{N}\mapsto \mathbb{N}^\mathbb{N}$, however due to the indexing of primes starting at $1$, and that $0$ does not have a unique factorization, it is more natural to use $\mathbb{Z}^+$ in these two instances. s.t. $$n=p_1^{e_1}p_2^{e_2}p_2^{e_2}\cdots\iff\phi(n)=(e_1,e_2,e_3,\dots),$$ where $p_k$ is the $k^\text{th}$ prime number. That is to say, if $\phi(n)=(\phi_1(n),\phi_2(n),\phi_3(n),\dots),$ then $\phi_k(n)$ is the largest power of $p_k$ dividing $n$. For example,

Properties

$\phi$ inherently shares a few properties with $\log$. Some other properties include

Generalizations

We may generalize the domain to $\mathbb{Q}^+$ by defining $$\phi\left(\frac{a}{b}\right)=\phi(a)-\phi(b),$$ which maintains all the above properties (with the extension $\Omega\left(\frac{a}{b}\right)=\Omega(a)-\Omega(b)$, and the extension to $T(m,n)$ as described in the comments of A297845).

Applications

As integer polynomials

Since we can consider polynomials (in one indeterminate) as a vector of their coefficients, we may assign a unique positive integer to every integer polynomial with no negative coefficients, or vice-versa, by the map $$P_n(x)=\sum_{k=1}^\infty \phi_k(n) x^{k-1}=\phi(n)\cdot (1,x,x^2,\dots).$$
$$\text{Graph 1. Interactive graph of $P_n(x)$.}$$ This bijection serves as a homomorphism between multiplication of natural numbers and addition of polynomials. $$\begin{align*} P_{mn}(x) &= \phi(mn)\cdot (1,x,x^2,\dots)\\ &= (\phi(m)+\phi(n))\cdot (1,x,x^2,\dots)\\ &= \phi(m)\cdot (1,x,x^2,\dots)+\phi(n)\cdot (1,x,x^2,\dots)\\ &= P_m(x)+P_n(x). \end{align*}$$ Additionally, since polynomial multiplication is equivalent to the convolution of its coefficients, we have $$ \begin{align*}P_m(x)P_n(x) &= (\phi(m)*\phi(n)) \cdot (1,x,x^2,\dots)\\ &= \phi(T(m,n)) \cdot (1,x,x^2,\dots)\\ &= P_{T(m,n)}(x). \end{align*}$$
This also nicely generalizes to assigning a unique positive rational to every integer polynomial, with our generalization to $\phi:\mathbb{Q}^+\mapsto \mathbb{N}^{\mathbb{Z}^+}$ outlined in the previous subsection, and thus serves as a step to enumerate the algebraic numbers. For instance, the golden ratios are the roots of $P_{1+\frac{1}{5}}(x)$

As integer multisets

We may instead consider $\mathbb{N}^{\mathbb{Z}^+}$ as isomorphic to the family of all positive-integer multisets. According to our bijection, let $\psi(n)=(A_n,m_n)$ denote the positive-integer multiset such that its underlying set and multiplicity function are given by $A_n=\{k\in \mathbb{Z}^+:\phi_k(n)>0\}$ and $m_n(k)=\phi_k(n)$, respectively. For example, $$\psi(140)=\{1, 1, 3, 4\}\text{ since }\phi(140)=(2,0,1,1,0,\dots).$$ This has the properties

As integer partitions

A specific use-case of positive-integer multisets are that of partitions. Hence, in terms of our bijection, $$p(n)=\#\{n\in\mathbb{Z}^+:\phi(n)\cdot\mathbb{Z}^+=n\},$$ where $p(\cdot)$ is the partition function and $\#(\cdot)$ denotes cardinality. Furthermore, if $\psi(n)$ and $\psi(m)$ are partitions of $a$ and $b$ respectively, then $\psi(mn)$ is a partition of $a+b$.

Natural numbers to integers

One rather elegant bijection $\phi:\mathbb{N}\mapsto\mathbb{Z}$ is that of $$\phi(n)=(-1)^n\left\lceil\frac{n}{2}\right\rceil.$$ Effectively, the parity acts as the sign bit. Alternatively, we may write this as $$\phi(n)=\frac{1}{4}((2n+1)\cos(\pi n)-1),$$ which has the added benefit of being analytic and thus $C^\omega$. For example,

Articles referencing here