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.

  • 1
    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.2012-08-20
  • 0
    @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.2012-08-20
  • 0
    @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?2012-08-20
  • 0
    As Carl Mummert says in his answer, your question is ambiguous (I disagree with his interpretation of the question, but what he says is completely fine). Problems about decidability (and recursive enumerability) must be presented in the form of a subset of natural numbers (another option is to consider a subset of the set $\{0,1\}^*$ of finite binary strings). Thus, your question must be rewritten saying which is the subset of natural numbers you are wondering whether is recursively enumerable. Notice for instance that in Carl's answer he has considered the subset $\{ n_{i,j}:i,j\in\omega\}$.2012-08-20
  • 0
    @boumol I will have to think about it. The question was intended to mean "is the set of all definable subsets of the natural numbers countable in the way I interpreted countable before I learned about axiomatic set theory, ordinals, and all the other subtleties". However, I guess the answer of Carl Mummert will remain valid, even if I succeed to formulate the question in a more rigorous way.2012-08-20
  • 2
    !Thomas Klimpel: you should consult the answers to this question from MathOverflow, which may be the question you had in mind: http://mathoverflow.net/questions/44102/is-the-analysis-as-taught-in-universities-in-fact-the-analysis-of-definable-numbe2012-08-20
  • 2
    I do not understand the downvote.2012-08-20
  • 0
    @Thomas: I do not follow your last edition, it has the same troubles. I can understand what you mean by a natural number which is well formed (although I dislike your terminology and proposal), but I do not understand your definition for subsets of natural numbers. Let me do some concrete questions: how do you codify the subset of odd numbers? how do you codify the subset of even numbers? how do you codify the subset of prime numbers? etc.2012-08-21
  • 0
    @boumol If I just have to specify a recursively enumerable set like the odd numbers or the prime numbers, I could copy the important parts from the specification of a suitable programming language like Haskell into the ODF document, and then write a function in that language which enumerates all elements of that set. The intention of my last edition was to give a more rigorous meaning to "recursively enumerable" in the context of the question. It's OK that "definable" also got narrowed down a bit on the way, but it basically still means "define it however you like, if it is clear enough".2012-08-21
  • 0
    @ThomasKlimpel: The problem is that your proposed concept of "well-formed definition" cannot be made rigorous -- and this is a _fundamental_ problem, not just one of tweaking the deails of the approach. Namely: we could write an ODF document saying: "Let a _well-formed definition_ mean such-and-such. Then consider the set of all numbers $n$ such that $n$ encodes an ODF that is a well-formed definitions of a set that $n$ is _not_ a member of". That would recreate Russell's paradox, so something has to give -- the assumption that "such-and-such" well-defines your idea of wfd must be rejected.2012-08-25
  • 0
    @HenningMakholm Note that being a *well formed definition* is only a prerequisite for being a *well formed definition* which *succeeds*. The intention of the concept *well formed definition* is to allow using human languages for the definitions without having to worry (too much) about the inaccuracies (and other issues) of human languages. On the other hand, dealing with paradoxes caused by self reference and other issues related to the mathematical content of the *well formed definition* is delegated to the concept of "can be recognized to *succeed* to define..."2012-08-25
  • 0
    @ThomasKlimpel: Doesn't matter. Just replace every instance of "well-formed defintion" in my comment with "well-formed definition which can be recognized to succeed".2012-08-25
  • 0
    @HenningMakholm The difference is that the meaning of "well-formed definition which can be recognized to succeed" is closely linked to the meaning of "definable subset of the natural number". But my initial question is exactly about the problems of this notion. So does your comment answers the question? Ignoring the self reference, your sentence seems to be interpretable as a definition of a "subset" based on an infinite set of "definable subsets". I guess this definition will *succeed*, if the infinite set is "recursively enumerable". However, I will have to think about it to be sure.2012-08-25
  • 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