Why should we accept the existence of subsets $A$ such that neither $A$ nor $A^c$ are recursively ennumerable? And how can we persuade others? 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.
 A: 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.
