3
$\begingroup$

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.]
$\endgroup$

1 Answer 1

Reset to default
4
$\begingroup$

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).

$\endgroup$
6
  • $\begingroup$ Thanks for the answer! So if I understand correctly, my formula at the end was right, but I'll have to play around with the variables to make it regular. $\endgroup$
    – susypeti
    Oct 11, 2019 at 19:55
  • $\begingroup$ @susypeti To be honest, I'm really confused by your notation. When you write $\exists v_{n+2}\, (v_1,\dots,v_n,v_{n+1},v_{n+2})$, I guess you mean $\exists v_{n+2}\, \varphi(v_1,\dots,v_n)$, where $\varphi$ is a $\Delta_0$ (bounded) formula? $\endgroup$
    – Alex Kruckman
    Oct 11, 2019 at 21:08
  • $\begingroup$ Also, note that a $\Sigma_1$-formula can have multiple existential quantifiers, not just one. So in general, $f(v_1,\dots,v_n) = v_{n+1}$ will be expressed by a formula of the form $\exists v_{n+2}\dots v_{n+k}\, \varphi(v_1,\dots,v_{n+k})$, where $\varphi$ is a $\Delta_0$-formula. $\endgroup$
    – Alex Kruckman
    Oct 11, 2019 at 21:10
  • $\begingroup$ Then yes, it's just a matter of rearranging the variables to make the formula regular, if you care about that. Using the $\Sigma_1$-formula in my last comment to express $f$, we can write $$\exists v_{n+k+1}\, (\exists v_{n+2}\dots v_{n+k}\, \varphi(v_1,\dots,v_{n},v_{n+k+1}, v_{n+2},\dots, v_{n+k}) \land v_{n+k+1}\neq v_{n+1}).$$ $\endgroup$
    – Alex Kruckman
    Oct 11, 2019 at 21:12
  • $\begingroup$ So this is Smullyan's notation that I copied, and in his definition, $\Sigma_1$ has one and only one existential quantifier at the beginning, which flanks a $\Sigma_0$ formula (only bounded quantifiers, if any), so that is why I've always included $\exists v_{n+2}$ before $F(v_1, ..., v_n, v_{n+1}, v_{n+2})$. I think he uses $\Sigma$ for what you call $\Sigma_1$, and then he proves that they are actually equivalent. This is my first time reading about these things so I only know what I've read so far. Thanks for your help explaining it! $\endgroup$
    – susypeti
    Oct 12, 2019 at 0:07

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .