Consider computation with the integers $\mathbb{Q}$. The traditional theory of recursive functions on $\mathbb{N}$ applies to $\mathbb{Q}$ by the identification of $\frac{a}{b} \in \mathbb{Q}$ with $2^{a}3^{b} \in \mathbb{N}$. Similarly, if I have any similar unnamed structure I can proceed likewise, as follows:


First, note that in this process of "Gödel numbering" a given object may have more than one representative Gödel number in $\mathbb{N}$. However the set of valid Gödel numbers is primitive recursive and there is a primitive recursive equivalence relation that determines whether two numbers represent the same object.


This leads to the following category $\textsf{PRA}$: The objects of $\textsf{PRA}$ objects are pairs $(A, \sim \_{A})$ where $A \subseteq \mathbb{N}$ is a primitive recursive set and $\sim \_{A} \subseteq A \times A$ is a primitive recursive equivalence relation. The morphisms of $\textsf{PRA}$ are are functions $f: (A, \sim \_A) \rightarrow (B, \sim \_B)$ induced by primitive recursive functions $F: \mathbb{N} \rightarrow \mathbb{N}$ such that $x \sim \_{A} y \Rightarrow F(x) \sim \_{B} F(y)$.


This is all rather rudimentary and seems like the correct definition (to me) of a Gödel numbering and leads naturally to the category just described. However I have never seen this category described or studied. Is this category simply


1. Uninteresting, or perhaps
2. Unimportant?


Any references would be appreciated. [See comment below.]



Category of Gödel Codings? [Reference Request]
You are about to invent [realizability theory](http://ncatlab.org/nlab/show/realizability). The particular category you are suggesting is going to be some sort of a category of *numbered sets*, see [this answer](https://mathoverflow.net/questions/21947/why-is-kleenes-notion-of-computability-better-than-banach-mazurs/21979#21979) for a definition. Category-theoretic aspects of realizability are considered in Jaap van Oosten's book "Realizability - An Introduction to its Categorical Side". A less demanding text might be my PhD thesis, or some of the other links on the nLab realizability page, linked above.


