You're quite right that "the $\mu$-operator breaks $\Delta^0_1$-ness." As an explicit example, the formula $\theta(x,y)\equiv$ "the $x$th Turing machine with input $x$ halts within $y$ steps" is $\Delta^0_1$, but the unary relation $$H(x)\equiv \mbox{"}0\not=\mu y.\theta(x,y)\mbox{"}$$ is not $\Delta^0_1$.
However, this doesn't contradict Post's theorem. The mistake is the following:
I always thought “general recursive/computable” meant the total functions closed under the primitive recursive functions and minimization, not the (non total) partial functions.
That's not correct - (general) recursive functions are allowed to be partial. In particular, there is a recursive enumeration of the recursive functions, but there is no such enumeration of the total recursive functions.
Indeed, this is sort of the driving observation behind recursion theory. Remember that diagonalization tells us that we can never have an "effective" notion of "total effective function" - otherwise, the function $f$ given by $f(x) = 1+ t_x(x)$, where $t_x$ is the $x$th effective function according to this notion, would be simultaneously total effective and not total effective. Whenever we have a "concretely defined" class of total recursive functions, it falls short of being the whole class of total recursive functions.
By contrast, once we allow partiality this issue goes away. We can whip up a recursive enumeration $(\varphi_e)_{e\in\mathbb{N}}$ of the (partial) recursive functions (essentially, this is a universal Turing machine), and the function $$\theta(x)=1+\varphi_x(x)$$ is indeed recursive, but there's no contradiction: we have $\theta=\varphi_e$ for some $e$ such that $\varphi_e(e)$ is undefined. Our diagonalizing function $\theta$ is also therefore undefined at $e$, and so there's no issue. In fact, if we spend enough time thinking about this situation (and get a bit clever), we'll eventually arrive at the recursion theorem.
Of course, ease of use isn't a fully satisfying motivator for a shift in the notion of "fundamental object." But recursion theory is supposed to model algorithms, and the simple fact is that there are algorithmic procedures which don't halt, and - while we can easily check that a purported algorithm is "grammatically correct" - there is no good way to determine if an algorithm is going to halt on a given input. So in fact partial functions correspond better to what we care about than total functions.
Since you mention graphs: a (unary, for simplicity) recursive function can be identified with its graph $G_f:=\{(x,y): f(x)=y\}$, and a relation $R\subseteq\mathbb{N}\times\mathbb{N}$ is the graph of some recursive function iff:
If the function is total then its graph is recursive, but otherwise it's merely r.e. - this is a consequence of the second clause, since it means that we can compute $f(x)$ by searching for the unique $y$ such that $(x,y)\in G_f$. By contrast, if we drop the second clause this breaks: a total r.e. relation need not be recursive.
As mentioned in the comments, due to the axiom of extensionality sets have no order, in this case $\{0,2,4,6,8,\ldots,1,3,5,7,\ldots\}$ is equal to $\mathbb N$ since it contains exactly the same members as $\mathbb N$. If we pick a linear order $\prec$ where $0\prec 2\prec 4\prec\ldots 1\prec 3\prec 5\prec\ldots$, this is indeed computably enumerable via the first definition. We can show this using the following algorithm, accepting a pair of numbers as input:
def ordering(a,b):
if (a mod 2) == (b mod 2):
if a < b:
return true
else:
loop forever on this line
else:
if (a mod 2) < (b mod 2):
return true
else:
loop forever on this line
If we input a pair $(a,b)$ into this program, it halts if and only if $a$ precedes $b$ in our ordering, otherwise it never halts. So this is a semi-decision procedure for our ordering.
A more pure application of this is using a pairing function $\pi:\mathbb N\times\mathbb N\to\mathbb N$: if we fix some (computable) pairing function, we may now input a pair of natural numbers in the form of one number, unpack the encoded input, and run the above algorithm. In fact, this also allows us to use the "enumeration" definition of recursive enumerability - there's a program that outputs all encodings of pairs $(a,b)$ where $a$ precedes $b$ in our ordering. In other words, this latter program outputs all naturals $x$ such that $\pi^{-1}(x)$, the unpacking of $x$, is a pair $(a,b)$ where $a\prec b$.
Edit: By request, here is more about a program outputting the encoded pairs:
def unpair(n): # Takes n and unpairs it, in terms of Cantor's pairing π : NxN -> N
w = math.floor((math.sqrt(8*z+1)-1)/2)
t = w*(w+1)/2
return [w-n+t, n-t]
n = 0
while true: # Start enumerating numbers
a = unpair(n)[0] # First entry
b = unpair(n)[1] # Second entry
if ordering(unpair(x)[0], unpair(n)[1]): # If n encodes pair:
print(n)
n += 1
The technical details of unpair don't matter that much, using any other bijective pairing function $\pi:\mathbb N\times\mathbb N\to\mathbb N$ also works, mainly then the answer to the question "what order does this program output pairs in?" changes. For this choice of $\pi$, these are some of the first numbers outputted along with the pairs they code:
- 2, (0,1)
- 5, (0,2)
- 7, (2,1)
- 9, (0,3)
- 13, (1,3)
- 14, (0,4)
- 16, (4,1)
- 18, (2,3)
- ...
Best Answer
$n$ is a power of $2$ iff
$$\forall a\,\forall b\,(2\cdot a+1)\cdot b=n\to a=0. $$ So let's start with something like $$ ((2a+1)b-n)^2$$ which is $\ge 0$ with equality iff $(2a+1)b=n$. Now let's express that $a$ is a positive integer. By Lagrange's four-square-theorem, this is equivalent to $\exists c\exists d\exists e\exists f\,a=1+c^2+d^2+e^2+f^2$. Thus from $$ P(n;a,b,c,d,e,f):=((2a+1)b-n)^2+(1+c^2+d^2+e^2+f^2-a)^2$$ we see that the non-powers of $2$ are diophantine.
As $P$ is always non-negative, we arrive at the complement set by looking at $$ Q(n;a,b,c,d,e,f,g,h,i,j) := 1+g^2+h^2+i^2+j^2-P(n;a,b,c,d,e,f)$$