Index
, 129, see also halting set
1-randomness, 159
1-reduction, 133
Ackermann function, 53
alphabet, 87
and, logical, 9
antecedent, 10
antisymmetry, 22
arithmetic
Peano, 173, 175, 183
Robinson, 104, 173
second-order, 178
standard model, 104, 173
arithmetic transfinite recursion, 183
arithmetical
completeness, 133
comprehension axiom, 183
hierarchy, 131
arity, 103, 170
Arslanov completeness criterion,
143
associativity, 33
automorphism, 30
of a lattice, 147
axiom of a production system, 88
axiomatizable, 163
base case, 31
Berry’s paradox, 163
bijection, 30
binary sequence, 43, 157
binary string, 43, 157
bit-flip, 46
Boolean algebra, 147
bounding, 186
BΠn,
0
186
BΣn,
0
186
c.e., see computably enumerable
capping, 150, 153
cardinality, 20, 25, 191
Cartesian product, 16
Chaitin’s Ω, 165
characteristic function, 43
Church-Turing thesis, 65
closure operator, 33
co-c.e., 102
code, 56
of a Turing machine, 59
codomain, 29
cofinite, 106
coinfinite, 106
complement, 17
completeness theorem, 103, 172
composition, 51
via indices, 80
comprehension, 179
arithmetical, 183
Π1,
1
184
199
Previous Page Next Page