200 Index recursive, 179 computable function, 65 set, 96 computable model theory, 174 computably (in)separable sets, 101, 136, 175 computably categorical, 176 computably enumerable set, 97 relativized, 129 conjunction, 9 consequent, 10 contradiction, 10 countable, 20 countably infinite, 20 cupping, 150, 153 low, 151 De Morgan’s Laws for predicate logic, 10 for sets, 19 decidable, 85 definability, 147, 150 degree, see Turing degree degree invariance, 154 diagonalization, 63, 105, 190 diagonally non-recursive, 185 disjoint, 16 disjoint union, 101 disjunction, 10 domain of a function, 29 of quantification, 13 domination, 64 dovetailing, 96 E, 146, 153 E∗, 146 effective, 97 effective countability, 56, 62 embedding, 150 enumeration of Turing machines, 60 equality for partial functions, 42 for sets, 15, 19 equivalence class, 25 equivalence relation, 25 equivalence, logical, 11 finite difference, 114, 145 first-order theory, 173 fixed-point theorem, 81 function Ackermann, 53 characteristic, 43 computable, 65 equality, 42 pairing, 57 partial, 42 partial recursive, 54 primitive recursive, 50 odel’s incompleteness, 105, 145, 163, 178 graph general mathematical, 33 of a function, 29, 100, 113 of a relation, 24, 27 greatest lower bound, 28 halting probability, 165 halting set, 78, 99, 114, 128, 129, 133 relativized, 129 high set, 154 implication, logical, 10 incompleteness theorem, 105, 145, 163, 178 independent sentence, 104 index, 60 index set, 82, 86, 135 induction, 179 on N, 31 on recursively defined sets, 35 inductive step, 31 injection, 29 injury, 116, 121 internal state, 44 interpretation, 103, 170 intersection, 16, 18 interval, 158 invariance, 147 for degrees, 154 isomorphism, 29 join, 101, 127, 128, 130, 146 jump, 129
Previous Page Next Page