Distinguishing sets according to more fine-grained notions than cardinality.

Question

I'm interested in distinguishing sets according to more fine-grained notions than cardinality. Now I don't know a thing about computability theory, but it seems to me that considering sets up to "computable bijection" is an inherently sensible way to achieve this.

To this end, I was thinking:

1. By an enumerated set, let us mean a pair $(X,x)$ such that $X$ is equipped with a bijection to $x : \mathbb{N} \rightarrow X$.
2. Study the category whose objects are enumerated sets, such that an arrow $f : (X,x) \rightarrow (Y,y)$ is just a function $U(f) : X \rightarrow Y$ with the property that $y^{-1} \circ U(f) \circ x$ is a computable function. Note that we're not requiring the diagram involving $x,y$ and $f$ to commute.

Are people talking about this sort of thing? If so, where can I learn more?

Answer 1

You may wish to extend your ordering range to the ordinals, which are in some senses more fine-grained than cardinals.

You may also wish to read about order-embeddings and the constellation of related ideas that are linked and referenced there.

Answer 2

For subsets of the natural numbers, and for sets naturally connected with such subsets via indexing, the subject has been studied for a very long time. The Wikipedia article on the Arithmetical Hierarchy will give a start. There has been particularly fine-grained analysis of r.e. degrees, huge literature.