1
$\begingroup$

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.

  • 0
    @ThomasKlimpel: Hmm. But then what you're asking for is not to enumerate "definable subsets" but to enumerate "subset definitions". And the diagonalization argument I sketch seems to show that the set-of-subset-definitions you're trying to recognize is not _itself_ successfully definable. That means, among other things, that it cannot be r.e., because a Turing machine that enumerated it would by any reasonable definition constitute a successful definition. (There's no explicit self reference in the construction; I'm imagining that you insert the textual definition of wfd we assume exists).2012-08-25

3 Answers 3

4

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.

  • 1
    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$.2012-08-20
3

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.

-1

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.

  • 0
    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.2012-08-22