All a b c d e f g h i j k l m n o p q r s t u v w x y z Other

Page 1

Displaying 1 – 4 of 4

Showing per page

Asymptotic density, computable traceability, and 1-randomness

Uri Andrews, Mingzhong Cai, David Diamondstone, Carl Jockusch, Steffen Lempp (2016)

Fundamenta Mathematicae

Let r ∈ [0,1]. A set A ⊆ ω is said to be coarsely computable at density r if there is a computable function f such that {n | f(n) = A(n)} has lower density at least r. Our main results are that A is coarsely computable at density 1/2 if A is computably traceable or truth-table reducible to a 1-random set. In the other direction, we show that if a degree a is hyperimmune or PA, then there is an a-computable set which is not coarsely computable at any positive density.

The strength of the projective Martin conjecture

C. T. Chong, Wei Wang, Liang Yu (2010)

Fundamenta Mathematicae

We show that Martin’s conjecture on Π¹₁ functions uniformly ≤ T -order preserving on a cone implies Π¹₁ Turing Determinacy over ZF + DC. In addition, it is also proved that for n ≥ 0, this conjecture for uniformly degree invariant Π ¹ 2 n + 1 functions is equivalent over ZFC to Σ ¹ 2 n + 2 -Axiom of Determinacy. As a corollary, the consistency of the conjecture for uniformly degree invariant Π¹₁ functions implies the consistency of the existence of a Woodin cardinal.

Currently displaying 1 – 4 of 4

Page 1