# How to establish bijective between the set of rooted trees and natural numbers, using Godel numbering?

Consider the structure of a rooted tree independent of its underlying set, (i.e. in the sense of trees as combinatorial species). I know a number of ways which we can encode any such tree in natural numbers, but all of them fail to be a bijective, i.e. Some numbers can not be decoded into any sensible tree structure. I would be very pleased to see such concrete correspondence. Thank you.

-
If you can encode each structure as a natural number, and there are infinitely many different structures you can collapse the range of the encoding to have a bijection with $\mathbb N$. –  Asaf Karagila Nov 11 '12 at 23:49

Abstract. We define a natural one-to-one correspondence between the set of positive integers and the set of equivalence classes of isomorphic rooted trees. By this correspondence, one can translate number-theoric concepts or quantities of a positive integer into graph-theoretic ones of a rooted tree. For example, a positive integer is prime if and only if the corresponding rooted tree is planted, that is, the valency of the root is equal to $1$.