How can {rational x where x > C} set be substantially different from {rational x where x < C} set?

50 Views Asked by At

In the Wikipedia article about Chaitin's_constant it is stated:

  • The set of rational numbers q such that q < Ω is computably enumerable;
  • The set of rational numbers q such that q > Ω is not computably enumerable.

As far as I understand, it also means that the set of q such as $-q < Ω$ is also not enumerable, which implies that negating a rational number changes its semantic somehow or that positive and negative "ends" of the number "pole" are substantially different.

Definition of computational enumerability seems not to depend on ordering of numbers inside a set...

Please explain this paradox. For example, why it's not the other way (<Ω not enumerable, >Ω enumerable)?

1

There are 1 best solutions below

4
On

The problem is in the sentence that begins "As far as I understand it, it also means $\dots$"; it does not mean that. The set of rational numbers $q$ such that $-q<\Omega$ is computably enumerable. Just run a sub routine that enumerates computably the $q$'s with $q<\Omega$ (according to the first bullet item in the question) and, whenever a number appears in that enumeration, reverse its sign and output the result.