[FOM] Re: New Characterization of Recursivity

[Ali Enayat]

1. I now concede that, as pointed out in Henk's message of June 2, the
characterizations of Sigma_1 and Pi_1 predicates in terms of "persistence"
properties only manage to establish a weak version of Henk's
characterization of recursivity.

The following example is instructive:

Consider the simplest recursive set, E = the empty set.

Consider the following Sigma_1 formulae F(x) and G(x):

F(x) = "x = x and there is a t such that t is the Godel number of the proof
of 0=1 from PA".

G(x) = "x = x".

In the standard model of arithmetic, F and G are one of the infinitely many
pairs of Sigma_1 formulae which witness the recursivity of E (albeit, a
bizzare pair).

[a pair (F,G) of Sigma_1 formulae witnesses the recursivity of X iff X is
the solution set of F, and the complement of X is the solution set of G].

By Godel's second incompletness theorem, there is an end extension M of the
standard model of PA such that M belives that the solution set of M is all
of M.

Therefore, given a recursive set X, one cannot simply pick *any* Sigma_1
predicate whose solution set is X to serve as f(x) in Henk's
characterization.


2. However, Henk's characterization follows immediately from the following
"fine-tuning" of the classical characterization of recursivity:

X is recursive iff there is a Turing machine T with the following
properties:

(1) On any given input, if T converges on some input q, and outputs s, then
s = 0 or s = 1, but not both.

(2) For any input q, property (1) above holds in any "universe" B that
contains a sufficiently large finite subset F of the hereditarily finite
sets (B is required to end extend F, hence Delta_0 formulae will be
absolute).

(3) T eventually halts on all inputs q.

(4) T outputs 1 on an input q iff q is in X.

The fine-tuning (2) is classical. The first time I encountered it was in
the proof of Trakhtenbrot's theorem (asserting that the set of sentences in
the language of binary graphs that are valid in finite domains is not
r.e.). See section 6.2.1 of the following text for a beautiful
presentation:

Finite Model Theory, by H.-D. Ebbinghaus and J. Flum (Springer).

Regards,

Ali Enayat

P.S. I should also add that "P-extensions" are much stronger than "end
extensions" since they are required to preserve the power set
operation. E.g., generic extensions of models of set theory are always end
extensions and never P-extensions.