An analogy between cardinal characteristics and highness properties of oracles

Andrew D Brooke-Taylor, Jörg Brendle, Keng Meng Ng, André Nies

Research output: Chapter in Book/Report/Conference proceedingConference Contribution (Conference Proceeding)

113 Downloads (Pure)

Abstract

We present an analogy between cardinal characteristics from set theory and highness properties from computability theory, which specify a sense in which a Turing oracle is computationally strong. While this analogy was first studied explicitly by Rupprecht (Effective correspondents to cardinal characteristics in Cichon’s diagram, PhD thesis, University of Michigan, 2010), many prior results can be viewed from this perspective. After a comprehensive survey of the analogy for characteristics from Cichon’s diagram, we extend it to Kurtz randomness and the analogue of the Specker-Eda number.
Original languageEnglish
Title of host publicationProceedings of the 13th Asian Logic Conference
Subtitle of host publicationGuangzhou, China, 16 – 20 September 2013
PublisherWorld Scientific Publishing Co.
Pages1-28
Number of pages28
ISBN (Electronic)978-981-4678-01-8
ISBN (Print)978-981-4675-99-4
Publication statusPublished - 1 May 2015

Keywords

  • computability theory
  • set theory

Fingerprint Dive into the research topics of 'An analogy between cardinal characteristics and highness properties of oracles'. Together they form a unique fingerprint.

Cite this