Notions of indifference for genericity: Union and subsequence sets

DOI10.1093/LOGCOM/EXAB035arXiv2104.13910MaRDI QIDQ6366381

Tejas Bhojraj

Publication date: 28 April 2021

Abstract: A set $I$ is said to be a universal indifferent set for $1$-genericity if for every $1$-generic $G$ and for all $XsubseteqI$, $GDeltaX$ is also $1$-generic. Miller showed that there is no infinite universal indifferent set for $1$-genericity. We introduce two variants (union and subsequence sets for $1$-genericity) of the notion of universal indifference and prove that there are no non-trivial universal sets for $1$-genericity with respect to these notions. In contrast, we show that there is a non-computable subsequence set for weak-$1$-genericity.

Mathematics Subject Classification ID

Mathematical logic and foundations (03-XX) Computer science (68-XX)

This page was built for publication: Notions of indifference for genericity: Union and subsequence sets

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6366381)