The ordered set with all even numbers first, followed by all odd numbers is a computable enumerable set

computabilityordinals

A set like for instance the ordered set with all even numbers first, followed by all odd numbers like ${\{0,2,4,…,1,3,5,…\}}$ is a computably enumerable set?

From wikipedia:

In computability theory, a set S of natural numbers is called computably enumerable >(c.e.), recursively enumerable (r.e.),
semidecidable, partially decidable, listable, provable or
Turing-recognizable if:
There is an algorithm such that the set of
input numbers for which the
algorithm halts is exactly S.

Or, equivalently,

There is an algorithm that enumerates the members of S. That means
that its output is simply a list of all the members of S: s1, s2, s3,
… . If S is infinite, this algorithm will run forever.

From a cardinal perspective is enumerable, in the sense there is a bijection between natural numbers and this particular set, so this particular bijection is a computation that enumerate their elements.

But can I provide a computation that outputs the numbers in the order I want? It seems that is not posible because the Turing machine would output even numbers forever, before having the opportunity to write an odd one…

Any countable ordinal is computably enumerable as a set?

Best Answer

As mentioned in the comments, due to the axiom of extensionality sets have no order, in this case $\{0,2,4,6,8,\ldots,1,3,5,7,\ldots\}$ is equal to $\mathbb N$ since it contains exactly the same members as $\mathbb N$. If we pick a linear order $\prec$ where $0\prec 2\prec 4\prec\ldots 1\prec 3\prec 5\prec\ldots$, this is indeed computably enumerable via the first definition. We can show this using the following algorithm, accepting a pair of numbers as input:

def ordering(a,b):
  if (a mod 2) == (b mod 2):
    if a < b:
      return true
    else:
      loop forever on this line
  else:
    if (a mod 2) < (b mod 2):
      return true
    else:
      loop forever on this line

If we input a pair $(a,b)$ into this program, it halts if and only if $a$ precedes $b$ in our ordering, otherwise it never halts. So this is a semi-decision procedure for our ordering.

A more pure application of this is using a pairing function $\pi:\mathbb N\times\mathbb N\to\mathbb N$: if we fix some (computable) pairing function, we may now input a pair of natural numbers in the form of one number, unpack the encoded input, and run the above algorithm. In fact, this also allows us to use the "enumeration" definition of recursive enumerability - there's a program that outputs all encodings of pairs $(a,b)$ where $a$ precedes $b$ in our ordering. In other words, this latter program outputs all naturals $x$ such that $\pi^{-1}(x)$, the unpacking of $x$, is a pair $(a,b)$ where $a\prec b$.

Edit: By request, here is more about a program outputting the encoded pairs:

def unpair(n): # Takes n and unpairs it, in terms of Cantor's pairing π : NxN -> N
  w = math.floor((math.sqrt(8*z+1)-1)/2)
  t = w*(w+1)/2
  return [w-n+t, n-t]
n = 0
while true: # Start enumerating numbers
  a = unpair(n)[0] # First entry
  b = unpair(n)[1] # Second entry
  if ordering(unpair(x)[0], unpair(n)[1]): # If n encodes pair:
    print(n)
  n += 1

The technical details of unpair don't matter that much, using any other bijective pairing function $\pi:\mathbb N\times\mathbb N\to\mathbb N$ also works, mainly then the answer to the question "what order does this program output pairs in?" changes. For this choice of $\pi$, these are some of the first numbers outputted along with the pairs they code:

  • 2, (0,1)
  • 5, (0,2)
  • 7, (2,1)
  • 9, (0,3)
  • 13, (1,3)
  • 14, (0,4)
  • 16, (4,1)
  • 18, (2,3)
  • ...
Related Question