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.
 A: 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. 
A: 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.
A: 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.
