Priority constructions
type: Item
instance of: scholarly article
title: Priority constructions
zbMATH Open document ID: 0858.03045
DOI: 10.1016/0168-0072(95)00053-4
author: Joseph R. Shoenfield
published in: Annals of Pure and Applied Logic
publication date: 1997-03-19T00:00:00Z
review text: Priority arguments are used in recursion theory to prove many theorems about the r.e. degrees. Usually one wants to construct a set (or sets). The basic idea is to write down the requirements you want your set to satisfy, order them in some way so that some requirements have priority over others, and then construct your set giving priority to the requirements of higher priority. In the course of the construction a requirement may become injured by the actions of a requirement of higher priority. In a finite-injury argument this can only happen to a particular requirement infinitely often. In an infinite-injury argument this may occur infinitely often. In this paper finite-injury and infinite-injury arguments are both put into (different) uniform frameworks. Virtually any finite-injury argument, and most infinite injury arguments (of type \(0''\)) can be put into this framework. Harder arguments, namely \(0'''\) arguments, can not.
reviewed by: William Gasarch
Mathematics Subject Classification ID: 03D25
zbMATH DE Number: 933092
zbMATH Keywords: recursively enumerable degrees
zbMATH Keywords: priority argument
zbMATH Keywords: finite-injury arguments
zbMATH Keywords: infinite-injury arguments
MaRDI profile type: Publication
full work available at URL: 0168-0072(95)00053-4
OpenAlex ID: W4213295930
cites work: The upper semi-lattice of degrees of recursive unsolvability
cites work: On some games which are relevant to the theory of recursively enumerable sets
cites work: Non-bounding constructions
cites work: Q3819052
Recommended article: Q3728007
Recommended article: Formal Methods for Components and Objects
Recommended article: Priority queues
Recommended article: Some construction
Recommended article: On the expressibility of priority
Recommended article: Scheduling recurrent construction
Recommended article: Acknowledgement of priority
description: scientific article; zbMATH DE number 933092