Quasi‐completeness and functions without fixed‐points

Mathematical Logic Quarterly 52 (6):595-601 (2006)
  Copy   BIBTEX

Abstract

We prove a completeness criterion for quasi-reducibility and generalize it to higher levels of the arithmetical hierarchy. As an application of the criterion we obtain Q-completeness of the set of all pairs such that the prefix-free Kolmogorov complexity of x is less than n

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 90,593

External links

Setup an account with your affiliations in order to access resources via your University's proxy server

Through your library

Similar books and articles

A quasi-order on continuous functions.Raphaël Carroy - 2013 - Journal of Symbolic Logic 78 (2):633-648.
On Non-wellfounded Sets as Fixed Points of Substitutions.Matti Pauna - 2001 - Notre Dame Journal of Formal Logic 42 (1):23-40.
Polynomial clone reducibility.Quinn Culver - 2014 - Archive for Mathematical Logic 53 (1-2):1-10.
Noetherian varieties in definably complete structures.Tamara Servi - 2008 - Logic and Analysis 1 (3-4):187-204.
A theory of truth that prefers falsehood.Melvin Fitting - 1997 - Journal of Philosophical Logic 26 (5):477-500.
Non‐isolated quasi‐degrees.Ilnur I. Batyrshin - 2009 - Mathematical Logic Quarterly 55 (6):587-597.
Fixed point logics.Anuj Dawar & Yuri Gurevich - 2002 - Bulletin of Symbolic Logic 8 (1):65-88.

Analytics

Added to PP
2013-12-01

Downloads
19 (#682,951)

6 months
2 (#668,348)

Historical graph of downloads
How can I increase my downloads?

Citations of this work

No citations found.

Add more citations