Partially generic formulas in arithmetic
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.
This page was built for publication: Partially generic formulas in arithmetic
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1105594)
