Encode every pair $(t,x)$ (where $t$ is a Turing machine and $x$ is an input string) as a distinct natural number. Then the halting subset $H$ fails to be recursive.

$$H := \{(t,x) \in \mathbb{N} \mid t \mbox{ halts for input } x\}$$

Nonetheless, $H \subseteq \mathbb{N}$ is recursively enumerable.

Now let $A := 2H \cup (2H^c+1).$ So basically we're just interleaving $H$ and $H^c$ in such a way that $H$ is coded as a subset of the even numbers and $H^c$ is coded as a subset of the odd numbers.

Then according to ZFC, $A$ is a perfectly valid set. More precisely, ZFC proves that $A$ exists. Nonetheless, neither $A$ nor $A^c$ are recursively enumerable (ZFC proves this, too). My question is, why should we accept the existence of sets like $A$ that, as far as I can see, really have no "implementability" at all?

Personally, I do accept that $A$ exists; I think I would feel cramped in a mathematical universe where $A$ was simply not a legitimate construct. Such a universe would not be big enough for my imagination.

But I want an argument with which to convince other people. Basically, the next time an (intelligent) computer programmer, or a practically-minded (but astute) scientist or engineer asks me: "Why should I accept that these silly sets exist?" I want to have a philosophically and/or mathematically convincing answer. I want to be able to actually convince them that $A$ is not so silly after all.

  • $\begingroup$ Because we're open to the existence of oracles. In fact, some people are not open to the nonexistence of an all knowing oracle. $\endgroup$ – Asaf Karagila May 24 '14 at 11:18
  • $\begingroup$ Well, you write yourself that ZFC proves that $A$ exists. Is'n that enough to accept the existence of $A$ ? $\endgroup$ – Archimondain May 24 '14 at 23:38
  • $\begingroup$ @Archimondain, not really; for example, I imagine that we can weaken the separation/replacement schemas of ZFC so that "non-implementable" sets cannot be shown to exist (but perhaps this would be a really bad idea). Bottom line: ZFC is merely a formal system, it lives in a sea of similar formal systems, and there's no particular reason to take any particular element of that sea and say: "This formal system is sacred." $\endgroup$ – goblin May 25 '14 at 7:51
  • $\begingroup$ @user18921: I believe these were the last words of Hippasus of Metapontum. :-P $\endgroup$ – Asaf Karagila May 25 '14 at 8:47
  • 1
    $\begingroup$ I answered this question, but I think that - as written - it is just barely within the scope of the site. The same can be said for many questions about the philosophy of math. The key, in my mind, is to ensure that the question is written in a way that has objective answers. So "what are some arguments that noncomputable sets exist" is better than "why do noncomputable sets exist" or "what is the best argument that noncomputable sets exist". $\endgroup$ – Carl Mummert May 25 '14 at 12:41

Well, I try an answer here. There are plenty of reasons why one should accept the existence of sets that are not r.e.

First you can argue their existence by a cardinality argument, as there are only countably many c.e. sets (or equivalently co-c.e. sets), but uncountably many sets.

Then there are such sets that are natural. Consider for example the set of codes for total computable functions. That is, the set $X$ so that $n \in X$ if the partial computable function coded by $n$, happens to be total, and $n \notin X$ otherwise. The set $X$ is not c.e. or co-c.e.

But why does it make sense to consider $X$ ? Well, it seems reasonable to accept considering the mathematical idea of "being total" for a partial computable function. Therefore it should be natural to consider the set of codes for those functions.

Now on the question of the existence of such sets, I have not much to say. They clearly exists as concepts, but it seems a bit vain in my opinion to ask more. I would say that the set of natural numbers has no more reasons to "exists" than the set $X$. There are both perfectly definable with natural concepts, and also both infinite abstract objects, that does not have much reality in a finite world.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.