A Framework for Priority Arguments

Front Cover
Cambridge University Press, Apr 19, 2010 - Mathematics
0 Reviews
This book presents a unifying framework for using priority arguments to prove theorems in computability. Priority arguments provide the most powerful theorem-proving technique in the field, but most of the applications of this technique are ad hoc, masking the unifying principles used in the proofs. The proposed framework presented isolates many of these unifying combinatorial principles and uses them to give shorter and easier-to-follow proofs of computability-theoretic theorems. Standard theorems of priority levels 1, 2, and 3 are chosen to demonstrate the framework's use, with all proofs following the same pattern. The last section features a new example requiring priority at all finite levels. The book will serve as a resource and reference for researchers in logic and computability, helping them to prove theorems in a shorter and more transparent manner.
 

What people are saying - Write a review

We haven't found any reviews in the usual places.

Selected pages

Contents

II
1
III
2
IV
3
V
5
VI
7
VII
14
VIII
17
IX
18
LXXV
88
LXXVI
89
LXXIX
90
LXXX
91
LXXXI
93
LXXXII
94
LXXXIII
95
LXXXIV
96

X
21
XI
23
XII
24
XIII
27
XIV
29
XV
31
XVI
33
XVII
36
XVIII
41
XIX
47
XX
49
XXIII
50
XXIV
51
XXV
52
XXVIII
53
XXIX
54
XXX
55
XXXII
56
XXXIII
57
XXXIV
58
XXXV
59
XXXVI
60
XXXIX
61
XL
62
XLII
63
XLV
64
XLVI
66
XLVII
68
XLVIII
69
L
70
LII
71
LIV
73
LV
75
LVI
76
LVII
77
LX
78
LXII
80
LXIII
81
LXV
84
LXVI
85
LXX
86
LXXIII
87
LXXXV
97
LXXXVI
98
LXXXVIII
99
LXXXIX
100
XC
101
XCIV
102
XCV
103
XCVI
104
XCVII
106
XCIX
107
C
108
CI
109
CIII
110
CV
111
CVI
113
CVII
117
CVIII
119
CIX
124
CX
126
CXI
132
CXIII
133
CXIV
136
CXVI
137
CXVII
138
CXVIII
140
CXIX
144
CXX
147
CXXI
149
CXXII
152
CXXIII
154
CXXIV
155
CXXV
158
CXXVI
159
CXXVII
161
CXXVIII
163
CXXIX
164
CXXX
166
CXXXII
167
CXXXIII
168
CXXXIV
173
CXXXV
175
Copyright

Other editions - View all

A Framework for Priority Arguments
Manuel Lerman
No preview available - 2010

Common terms and phrases

action is compatible action sentences activated action Analysis antiderivative arithmetical hierarchy assignment is followed backtracking extender basic module block Clauses i)–(iii computable partial functional computably enumerable degrees computably enumerable set conflicts constrained construction has infinite current path defined Definition Definition 2.7.7 follow different directing sentence ensure existential finite first follows from Lemma Free Derivative Friedberg–Muˇcnik functional axioms Furthermore Hence iff immediate successor implemented incompatible infinite support initial derivative least element Limit Path Link Analysis minimal pair node of Tk oracle out(k outcome parameters path computation path through T1 PL(m place a number poset preferential derived assignment principal derivative priority method proved as Lemma quantifiers requirement is assigned resp satisfied satisfy Section shared functional action specified standard derived assignment standard initial assignment strong minimal suffices Suppose switched Tk+1 trees of strategies true path validated action Verification weight function

About the author (2010)

Manuel Lerman is a Professor Emeritus of the Department of Mathematics at the University of Connecticut. He is the author of Degrees of Unsolvability: Local and Global Theory, has been the managing editor for the book series Perspectives in Mathematical Logic, has been an editor of Bulletin for Symbolic Logic, and is an editor of the ASL's Lecture Notes in Logic series.

Bibliographic information

QR code for A Framework for Priority Arguments
TitleA Framework for Priority Arguments
Volume 34 of Lecture Notes in Logic
AuthorManuel Lerman
PublisherCambridge University Press, 2010
ISBN1139487876, 9781139487870
Subjects › 

Mathematics / Logic
  
Export CitationBiBTeX EndNote RefMan