If the relation $f(x_1, ..., x_n)=y$ is $\Sigma_1$, then is its negation also $\Sigma_1$?

Question

If the relation $f(x_1, ..., x_n)=y$ is $\Sigma_1$, then is its negation also $\Sigma_1$?

The above question (ore more like the imperative to prove it in the affirmative) is Exercise 1. on page 54 of Smullyan's Gödel's Incompleteness Theorems, and it would show that every $\Sigma_1$-function is recursive. He gives the 'hint' that if $f(x_1, ..., x_n)$ is unequal to $y$, then it is equal to some number other than $y$.

Now I understand that the hint hints at a solution where you do not just negate the $\Sigma_1$-formula that expresses $f(x_1, ..., x_n)=y$, since that would no longer be $\Sigma_1$, as $\exists v_{n+2}(v_1, ..., v_n, v_{n+1}, v_{n+2})$ expresses $f(x_1, ..., x_n)=y$ , and its negation would be $\forall v_{n_2}\neg (v_1, ..., v_n, v_{n+1}, v_{n+2})$, which is an unbounded universal quantifier.

But this is where I'm stuck. It seems to me that if we want to express that $f(x_1, ..., x_n)= u$, where $u \neq y$, then we would always need to have a formula in which $y$ occurs free, which would then have too many free variables to express an $n+1$-ary relation, since we have to have $x_1, ..., x_n$ and $u$ free as well.

More specifically, we could take the formula $\exists v_{n+2}(v_1, ..., v_n, v_{n+1}, v_{n+2}) \wedge v_{n+3} \neq v_{n+1}$, which would then express $g(x_1, ..., x_n)=(y,u)$ where $f(x_1,..., x_n)=y$ and $\neg f(x_1, ..., x_n)=u$, or more precisely, $g(x_1, ..., x_n, y)=u$. But what we need is $g(x_1, ..., x_n)=u$.

Could the formula be $\exists v_{n+1}(\exists v_{n+2}(v_1, ..., v_n, v_{n+1}, v_{n+2}) \wedge v_{n+3} \neq v_{n+1})$? This would be true iff there is a number $k$ such that $\exists v_{n+2}(v_1, ..., v_n, \overline{k}, v_{n+2}) \wedge v_{n+3} \neq \overline{k}$, which in turn would be true for any numbers $k_1, ..., k_n$ such that $f(k_1, ..., k_n)=k$ and $u\neq k$.

[Of course this isn't technically a regular formula since $v_{n+1}$ is bound, while $v_{n+3}$ is free, so by definition, it does not express any relation.

The definitions are this:

• A regular formula $F$ is such that for any $i$, if $v_i$ is a free variable of $F$, then for any $j \leq i$, $v_j$ is also a free variable of $F$.
• A regular formula $F(v_1,...,v_n)$ expresses the set of all $n$-tuples $(k_1, ..., k_n)$ of natural numbers such that $F(\overline{k_1}, ..., \overline{k_n})$ is a true sentence.]

Answer 1

If $f$ is a function, then:

$$f(x_1,\dots,x_n) \neq y \iff \exists z\, (f(x_1,\dots,x_n) = z \land z \neq y).$$

More precisely, if $f(x_1,\dots,x_n) = y$ is expressed by the $\Sigma_1$-formula $\varphi(x_1,\dots,x_n,y)$, then $f(x_1,\dots,x_n) \neq y$ is expressed by the formula $\exists z\, (\varphi(x_1,\dots,x_n,z)\land (z\neq y))$, which is also $\Sigma_1$ (since $z\neq y$ is quantifier-free, hence $\Sigma_1$, and the $\Sigma_1$ formulas are closed under conjunction and existential quantifiers).