A Framework for Priority ArgumentsThis 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.
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 |
Other editions - View all
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