What is a possible algorithm for enumerating over all possible pairs, by size, between two enumerable, countably-infinte sets, $ X$ and$ Y$ , of words $ w$ ? Aka, starting with $ |x|min + |Y|min$ as the first element in the enumeration and then carrying on upwards?
Part B (more the question I’m after)
Is there a way to enumerate over all pairs $ (x,y)$ so that there is one element (in the enumeration) of each size and no more? And, as an extra condition, the enumerator needs to be able to do this encoding of the pairs it enumerates in a way such that it doesn’t "mangle" the pairs. To define mangle: I need to be able to extract (read) $ X$ and $ Y$ back out of any string in the enumeration in poly time (measured in length of string in the enumeration (aka $ |X|+|Y|+or -|bits|$ (depending on encoding used by enumerator)). So, whatever encoding the enumerator uses for its representation of the pairs…one needs to be able to decode that string back into $ (x,y)$ in poly time and there has to be at least one string of each length representing some valid pair. So, given a natural number $ b$ , there is an element of the enumeration that is of length $ b$ and we can decode that string of length $ b$ back into ($ x,y$ ) in less than $ b^k$ time (just as an aside, this also means that $ |x,y|<b^k$ ).