# Is the set of all definable subsets of the natural numbers recursively enumerable?

I asked myself similar questions before, for example "Are the definable real numbers countable"? It seemed to me that the set of all explicitly and unambiguously definable objects is "countable", because we could write down the text defining a specific object in the English language. (Or use the English language to define a formal language appropriate to write down the definition.) But English isn't unambiguous, and the meaning of "countable" depends on the used set theory.

Right now I'm thinking about second order logic. Assuming that the natural numbers exist and are well defined seems unproblematic to me. However, the question which subsets of the natural numbers (should we assume to) exist has no good answer. If we say that "all" subsets exist, we run into all sorts of set theoretic questions. If we resort to axiomatic set theory for these questions, we end up with the fact that the natural numbers can't be defined up to isomorphism. The alternative seems to be to assume that only the definable subsets of the natural numbers exist. But my guess is that this won't work out either, i.e. that the "set of all definable subsets of the natural numbers" turns out to be a very strange beast. But if it is a strange beast, I guess it won't be recursively enumerable.

Question Assuming the Church-Turing thesis (or a suitable analogue for definability, or some other sufficiently solid foundation), what can be said about the "set of all definable subsets of the natural numbers"? Is it well defined and recursively enumerable?

Edit It has been pointed out that my use of "recursively enumerable" is ambiguous without further clarifications, especially that I have to specify how a definable subset of the natural numbers is expected to be encoded as a natural number. Given a natural number, take its binary representation and interpret it as a document in the "OpenDocument" format (ODF). Assume that we can efficiently decide whether the document is valid ODF and whether its content is written sufficiently clear and tries to define a subset of the natural numbers. Let's call this a well formed definition. Assume further that each definable subset has at least one well formed definition which can be recognized to succeed in defining a subset of the natural numbers. Now the question is whether there exists a recursively enumerable subset $S$ of the natural numbers such that each number in $S$ corresponds to a well formed definition which succeeds, and that for each definable subset the set $S$ contains a corresponding definition.

-
Let me remember that the "Turing machine" model is a finitistic one; it only accepts finite inputs and it only produces finite outputs. How do you want to codify in a finitistic way a subset of natural numbers? The more natural way is to use a finitistic formula to describe the set, but then it is obvious which is the answer to your question (YES). If you do not want to use the natural way then you must add to the question what is the finitistic codification (for subsets of natural numbers) you want to use. – boumol Aug 20 '12 at 9:57
@boumol It's true that the "Turing machine" only accepts finite inputs, but what do you mean by "it only produces finite outputs"? One natural way to define a subset of the natural numbers by a Turing machine would be to take the set of input numbers for which the machine stops. It should be clear from the question that any unambiguous way to define a subset of the natural numbers is acceptable. Especially if $S_1$ and $S_2$ are definable, then $S_1 - S_2$ is also definable. However, this doesn't mean that it is also definable as the set of input numbers for which some Turing machine stops. – Thomas Klimpel Aug 20 '12 at 12:28
@boumol Assuming you're still sure the methods with a finitistic formula works (I'm not sure what this means exactly), can you expand your comment into an answer? – Thomas Klimpel Aug 20 '12 at 12:32
!Thomas Klimpel: you should consult the answers to this question from MathOverflow, which may be the question you had in mind: mathoverflow.net/questions/44102/… – Carl Mummert Aug 20 '12 at 13:58
I do not understand the downvote. – Arkamis Aug 20 '12 at 15:33

The question is somewhat ambiguous about exactly how the sets would be enumerated. The natural way to read it in computability theory is the following, which is the usual sense in which a sequence of sets can be r.e.:

Is there a computable double enumeration $\{ n_{i,j} : i,j \in \omega\}$ such that for each definable set $S \subseteq \omega$ there is an $i_0$ such that $S = \{ n_{i_0,j} : j \in \omega\}$.

The answer to that is certainly "no", because if it was true then every definable set would be r.e., which is not the case.

-
For those with some interest, I want to point out I have taken the weakest possible definition of "enumerable sequence of sets", in the sense that there may not be any effective way to tell which $i_0$ corresponds a particular $S$. Thus the enumeration has infinitely many chances to capture any particular $S$. – Carl Mummert Aug 20 '12 at 14:02

As long as every "definable" number may be defined using a finite string in some finite alphabet you may sort those strings by length and enumerate numbers using this sort.

-
The problem with that is that if "definable" means that there is some formula that is true for this number but false for all others, the relation between defining strings and actual numbers is not itself definable inside the system. There are models of ZFC in which every real number is definable in this way (but the relation between defining formulas and defined numbers is not a set), and we cannot be sure we're not living in such a world. – Henning Makholm Aug 22 '12 at 11:42

A short answer would be that the concept of "recursively enumerable" is only defined for subsets of some countable universe, where that universe has a ("reasonable") encoding as finite strings of symbols that can be input or output by a Turing machine. In your case the set of "subsets of $\mathbb N$ that are definable" (whatever exactly that means) doesn't satisfy that condition, becuase the natural universe to use would be $\mathcal P(\mathbb N)$, which is not countable.

So it doesn't even make sense to ask whether your set is r.e.

One could attempt to broaden the definitions by imagining a non-deterministic Turing machine that writes an infinite sequence of 0s and 1s to a write-only output tape, where that sequence can be interpreted as a subset of $\mathbb N$. One could then declare that some $A\subseteq 2^{\mathbb N}$ is "recursively enumerable"-ish iff it is the set of possible outputs of some non-deterministic machine.

However, though this can be argued to generalize the ordinary concept of recursive enumerability, it wouldn't be the ordinary concept of recursive enumerability.

-