Partially generic formulas in arithmetic (Q1105594)

Let \(T\) be a consistent r.e. theory ``containing sufficient amount of arithmetic'', and let \(\Gamma\) be either a \(\Sigma_{n+1}\) or \(\Pi_{n+1}\) class of arithmetical formulas. If \(\chi(G;k)\) is an arithmetic formula with parameters k and an extra predicate \(G\), and if \(\xi(x)\) is an arithmetic formula, then \(\chi(\xi;k)\) is the result of replacing \(G\) by \(\xi(x)\) in \(\chi(G;k)\). In what follows it is always assumed that \(\chi\) is positive in \(G\), which means that PA proves ``if \(\chi (\xi_ 0;k)\) and for every x, \(\xi_ 0(x)\) implies \(\xi_ 1(x)\), then \(\chi(\xi_ 1;k)\)''. A formula \(\xi(x)\) is \(\chi\)-generic in \(T\) if for all finite sequences of parameters k if \(T\) proves \(\chi(\xi;k)\), then \(T\) proves \(\chi(\phi;k)\), where \(\phi\) is the disjunction of formulas of the form \(x=n\), for \(n\) in some finite subset of the set numerated in \(T\) by \(\xi(x)\). The main result says that for every r.e. set \(X\) and every \(\Gamma\) formula \(\chi\) there is an enumeration \(\xi(x)\) of \(X\) in the class \(\Gamma\), \(\chi\)-generic in \(T\). This result is applied to give uniform proofs of many facts (some known before and some new) about enumerations of r.e. sets in \(T\), and about sentences which are \(\Gamma\)-conservative over \(T\). Also a model theoretic result concerning relationship between \(\Gamma\)-definable and co-\(\Gamma\)- definable elements in models of \(T\) is given.