Is there a 'natural' bijection between the rational and the natural numbers? I've seen various bijections between the rationals and the naturals (the first being Cantor's Pairing function (the snake looking one) and another being the Calkin Wilf Tree) many times; but I can always remember being slightly disturbed by the lack of 'naturality' in the bijection (before I even knew formally how to express 'naturality'); in some sense the bijections always seemed a bit arbitrary and not inherently part of the structure of the rationals/the naturals.
Recently I've been exposed to some notion of 'naturality' in Category Theory, and loosely I have come to understand a 'natural' bijection as one that in some sense requires no choice of any kind, and arises inherently from the structures involved. Is there a way of talking about the 'naturality' of the bijections between the rationals and the naturals? I'm not even sure which Categories are at play in this scenario, or even if this is a well defined question or not.
 A: It is a common misconception that a natural isomorphism (in the categorical sense) is an isomorphism $A \to B$ between two single objects $A,B$ which is natural in some sense. This is not true. The concept of a natural isomorphism applies to functors between two categories. In other words, a natural isomorphism is really a bunch of isomorphisms $F(x) \to G(x)$, one for each object $x$ of the domain of $F$ and $G$. Of course, any object can be regarded as a constant functor, and then any isomorphism between two objects leads to a natural isomorphism between the associated functors, but this is rather boring and has nothing to do with naturality in the common sense.
Your question is about isomorphisms between $\mathbb{N}$ and $\mathbb{Q}$ in the category of sets. [At this point, let me mention that there is no isomorphism between these objects in more interesting categories such as commutative monoids, ordered sets, topological spaces, etc.] As I've said, it does not make much sense to speak of natural isomorphisms here, because we have no functors given. But it is possible to consider the following two functors:
Consider the category $\mathcal{C}$ of semirings with isomorphisms of semirings, and the category $\mathcal{D}$ of sets and isomorphisms of sets. There is a forgetful functor $F : \mathcal{C} \to \mathcal{D}$, and there is a functor $G : \mathcal{C} \to \mathcal{D}$ which maps a semiring to the underlying set of the total ring of fractions of its Grothendieck ring (given by adjoining additive inverses and then multiplicative inverses by regular elements). Thus, $F(\mathbb{N},+,\cdot)=\mathbb{N}$ and $G(\mathbb{N},+,\cdot)=\mathbb{Q}$. Now one might ask if there is a natural isomorphism $F \to G$. But this is not the case.
A: In an earlier post, I have described a bijection between $\mathbb{N}$ and $\mathbb{Q}$ which I consider somewhat less artificial than e.g. Cantor's pairing function. Perhaps it is something like this you are looking for?
