zbMATH — the first resource for mathematics

Notions of weak genericity. (English) Zbl 0549.03042
[Correction of the faulty review Zbl 0542.03028.] The notion of n-generic set was introduced to deal with forcing in arithmetic. A set A is called n-generic iff for every \(\Sigma^ 0_ n\) sentence \(\phi\) of number theory with a constant set, either \(A\Vdash\phi \) or \(A\Vdash\neg \phi\), or iff for every \(\Sigma^ 0_ n\) set \({\mathcal S}\) of strings, there exists a string \(\sigma\subseteq A\) such that either \(\sigma\) is in \({\mathcal S}\) or no extension of \(\sigma\) is in \({\mathcal S}\). It may be generalized along two directions. A is weakly n-forcing if for every \(\Sigma^ 0_ n\) sentence \(\phi\) either \(A\Vdash\neg \neg\phi \) or \(A\Vdash\neg \phi\). A is weakly n-generic if it meets every dense \(\Sigma^ 0_ n\) set \({\mathcal S}\) of strings, i.e., there is a string \(\sigma\in {\mathcal S}\) which is extended by A. In this paper it is shown that every weakly \((n+1)\)-generic set is n-generic and every n-generic set is weakly n-generic and also that if A is weakly n-forcing and weakly n-generic then it is n-generic. A degree of unsolvability is called (weakly) n-generic if it contains a (weakly) n-generic set. A degree a is hyperimmune with respect to a degree b if there is a fixed function \(f\leq a\) which is not dominated by any function recursive in b (here f dominates g iff for all n, f(n)\(\geq g(n))\). The main result of this paper is that a degree b is the n-th jump of a weakly \((n+1)\)-generic degree a iff b is hyperimmune with respect to \(0^{(n)}\) and \(b\geq 0^{(n)}\).
Reviewer: Moh ShawKwei

03E40 Other aspects of forcing and Boolean-valued models
03D30 Other degrees and reducibilities in computability and recursion theory
Full Text: DOI
[1] DOI: 10.1002/malq.19690150707 · Zbl 0184.02002 · doi:10.1002/malq.19690150707
[2] DOI: 10.1002/malq.19690152004 · Zbl 0191.30601 · doi:10.1002/malq.19690152004
[3] Fundamenta Mathematicae 56 pp 325– (1965)
[4] DOI: 10.4153/CJM-1958-035-x · Zbl 0082.01505 · doi:10.4153/CJM-1958-035-x
[5] Recursion theory: Its generalizations and applications (1980)
[6] Proceedings of the London Mathematical Society 25 pp 586– (1972)
[7] Theory of recursive functions and effective computability (1968)
[8] DOI: 10.1002/malq.19680140704 · Zbl 0216.29102 · doi:10.1002/malq.19680140704
[9] Axiomatic set theory. I, Proceedings of Symposia in Pure Mathematics 13 (1971)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.