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