WEAKLY 2-RANDOMS AND 1-GENERICS IN SCOTT SETS

DOI10.1017/JSL.2017.73MaRDI QIDQ4638993zbMATH OpenOpenAlexFDO

Authors Linda Brown Westrick

Publication date 2 May 2018

Published in Journal of Symbolic Logic (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1711.00153

zbMATH Keywords

degree theorygenericityalgorithmic randomnesslattice embeddingScott set

Mathematics Subject Classification ID

Algorithmic randomness and dimension (03D32) Other Turing degree structures (03D28) Second- and higher-order arithmetic and fragments (03F35)

Abstract: Let $S$ be a Scott set, or even an $omega$-model of $mathsfWWKL$. Then for each $AinS$, either there is $XinS$ that is weakly 2-random relative to $A$, or there is $XinS$ that is 1-generic relative to $A$. It follows that if $A_1,dots,A_{n}inS$ are non-computable, there is $XinS$ such that each $A_i$ is Turing incomparable with $X$, answering a question of Kuv{c}era and Slaman. More generally, any $forallexists$ sentence in the language of partial orders that holds in $mathcalD$ also holds in $mathcal{D}_S$, where $mathcal{D}_S$ is the partial order of Turing degrees of elements of $S$.

Recommendations

• Almost weakly 2-generic sets
• A Weakly 2-Random Set That Is Not Generalized Low
• Some remarks on \((\mathcal{F}_1,\mathcal{F}_2)\)-scrambled sets
• Generalized specification property and distributionally scrambled sets
• An explicit description of all scrambled sets of weakly unimodal functions of type 2^
• Scott functions, their representations on domains, and applications to random sets
• A strengthening of Scott's \(ZF^{\neq}\) result
• On scrambled sets and a theorem of Kuratowski on independent sets
• Theory and Applications of Models of Computation
• scientific article; zbMATH DE number 1180209

Cites work

• scientific article; zbMATH DE number 3861137 (Why is no real title available?)
• A measure-theoretic proof of Turing incomparability
• Computability and randomness
• Lowness and nullsets
• Turing incomparability in Scott sets

Cited in

(5)

• Bounds on weak scattering
• Almost weakly 2-generic sets
• Turing incomparability in Scott sets
• A Weakly 2-Random Set That Is Not Generalized Low
• An explicit description of all scrambled sets of weakly unimodal functions of type 2^

This page was built for publication: WEAKLY 2-RANDOMS AND 1-GENERICS IN SCOTT SETS

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