2

I have a question about a passage in Enderton's "A Mathematical Introduction to Logic", p. 241.

He writes that if some formula $\exists v \rho$ defines a recursively enumerable set $Q$ in $\mathfrak{N}$, then it cannot represent $Q$ in $\text{Cn } A_E$ (since $Q$ would be recursive).

He then shows how "it can come halfway". By this, does Enderton mean that, although we can have (1) we can't have (2), but only (3)?

(1) $a \in Q \leftrightarrow A_E \vdash \exists v \rho (\mathbf{S}^a\mathbf{0}, v)$

(2) $a \notin Q \leftrightarrow A_E \vdash \lnot(\exists v \rho (\mathbf{S}^a\mathbf{0}, v))$

(3) $a \notin Q \leftrightarrow A_E \nvdash \exists v \rho (\mathbf{S}^a\mathbf{0}, v)$

If a set $Q$ is such that (1) and (2) are true of it, and $Q$ is definable in $\mathfrak{N}$, does that make $Q$ a recursive relation, and do (1) and (2) amount to $Q$ being numeralwise determined?

MonkeyKing
  • 3,178
user65526
  • 1,373

1 Answers1

0

Hint

You have to use :

THEOREM 35F [page 239] A relation is recursive iff both it and its complement are recursively enumerable.

and the definition [page 206] of a [unary] relation $R$ being representable in $A_E$ :

$a \in R \ ⇒ \ A_E \vdash ρ(S^a0)$,

$a \notin \ R ⇒ \ A_E \vdash ¬ρ(S^a0)$.

Now, the r.e. set $Q$ is such that :

$a \in Q \iff \exists b \ (a,b) \in R$,

and obviously :

$a \notin Q \iff \lnot \exists b \ (a,b) \in R$.

If $R$ is recursive, the predicate $\exists y R(x,y)$ is r.e. but not necessarily so for $\lnot \exists y R(x,y)$.

The fact that $\lnot \exists y R(x,y)$ is not r.e. means that we cannot "move from" $A_E \nvdash \exists x \rho$ to $A_E \vdash \lnot \exists x \rho$.

Mauro ALLEGRANZA
  • 94,169