An analogy between cardinal characteristics and highness properties of oracles

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

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 proceeding › Conference 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 language	English
Title of host publication	Proceedings of the 13th Asian Logic Conference
Subtitle of host publication	Guangzhou, China, 16 – 20 September 2013
Publisher	World Scientific Publishing Co.
Pages	1-28
Number of pages	28
ISBN (Electronic)	978-981-4678-01-8
ISBN (Print)	978-981-4675-99-4
Publication status	Published - 1 May 2015

Keywords

computability theory
set theory

Access to Document

http://www.worldscientific.com/worldscibooks/10.1142/9596

Handle.net

Persistent link

Bringing set theory and algebraic topology together.
Rasappan, R. (Principal Investigator)
21/10/13 → 20/06/16
Project: Research

Cite this

@inproceedings{d09e78f943494fee830cd578d1705cd9,

title = "An analogy between cardinal characteristics and highness properties of oracles",

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{\textquoteright}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{\textquoteright}s diagram, we extend it to Kurtz randomness and the analogue of the Specker-Eda number.",

keywords = "computability theory, set theory",

author = "Brooke-Taylor, \{Andrew D\} and J{\"o}rg Brendle and Ng, \{Keng Meng\} and Andr{\'e} Nies",

year = "2015",

month = may,

day = "1",

language = "English",

isbn = "978-981-4675-99-4 ",

pages = "1--28",

booktitle = "Proceedings of the 13th Asian Logic Conference",

publisher = "World Scientific Publishing Co.",

address = "Singapore",

}

An analogy between cardinal characteristics and highness properties of oracles. / Brooke-Taylor, Andrew D; Brendle, Jörg; Ng, Keng Meng et al.
Proceedings of the 13th Asian Logic Conference: Guangzhou, China, 16 – 20 September 2013. World Scientific Publishing Co., 2015. p. 1-28.

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

TY - GEN

T1 - An analogy between cardinal characteristics and highness properties of oracles

AU - Brooke-Taylor, Andrew D

AU - Brendle, Jörg

AU - Ng, Keng Meng

AU - Nies, André

PY - 2015/5/1

Y1 - 2015/5/1

N2 - 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.

AB - 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.

KW - computability theory

KW - set theory

M3 - Conference Contribution (Conference Proceeding)

SN - 978-981-4675-99-4

SP - 1

EP - 28

BT - Proceedings of the 13th Asian Logic Conference

PB - World Scientific Publishing Co.

ER -

An analogy between cardinal characteristics and highness properties of oracles

Abstract

Keywords

Access to Document

Handle.net

Fingerprint

Projects

Bringing set theory and algebraic topology together.

Cite this