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