Relative Definability of n-Generics

2015/11/28 by Wei Wang, Wang, Wei
Computer Science · Mathematics · #03D25 #03D28 #Advanced Topology and Set Theory #Computability, Logic, AI Algorithms #FOS: Mathematics #Logic (math.LO) #semigroups and automata theory

paper · pdf · doi:10.48550/arxiv.1511.08875

openalex publication_date 2015/11/28 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

A set G ⊆ ω is n-generic for a positive integer n if and only if every Σ⁰_n formula of G is decided by a finite initial segment of G in the sense of Cohen forcing. It is shown here that every n-generic set G is properly Σ⁰_n in some G-recursive X. As a corollary, we also prove that for every n > 1 and every n-generic set G there exists a G-recursive X which is generalized \rm low_n but not generalized \rm low_n-1. Thus we confirm two conjectures of Jockusch.

Related

• On Mathias generic sets
• Generic Saturation
• Limits to joining with generics and randoms
• Forcing, genericity and CBERS
• The Genericity Conjecture