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Π0 n , 186 BΣ0 n , 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

Purchased from American Mathematical Society for the exclusive use of nofirst nolast (email unknown) Copyright 2012 American Mathematical Society. Duplication prohibited. Please report unauthorized use to cust-serv@ams.org. Thank You! Your purchase supports the AMS' mission, programs, and services for the mathematical community.