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

G¨ 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