COMPUTABILITY AND LOGIC
CONTENTS COMPUTABILITY THEORY 1 ENUMERABILITY ENUMERABILITY ENUMERABLE SETS 2 DIAGONALIZATION 3 TURING COMPUTABILITY 4 UNCOMPUTABILITY THE HALTING PROBLEM THE PRODUCTIVITY FUNCTION 5 ABACUS COMPUTABILITY ABACUS MACHINES SIMULATING ABACUS MACHINES BY TURING MACHINES THE SCOPE OF ABACUS COMPUTABILITY 6 RECURSIVE FUNCTIONS PRIMITIVE RECURSIVE FUNCTIONS MINIMIZATION 7 RECURSIVE SETS AND RELATIONS RECURSIVE RELATIONS SEMIRECURSIVE RELATIONS FURTHER EXAMPLES 8 EQUIVALENT DE?NITIONS OF COMPUTABILITY CODING TURING COMPUTATIONS UNIVERSAL TURING MACHINES RECURSIVELY ENUMERABLE SETS CONTENTS BASIC METALOGIC 9 A PR´ECIS OF FIRST-ORDER LOGIC: SYNTAX FIRST-ORDER LOGIC SYNTAX 10 A PR´ECIS OF FIRST-ORDER LOGIC: SEMANTICS 10 1 SEMANTICS 10 2 METALOGICAL NOTIONS 11 THE UNDECIDABILITY OF FIRST-ORDER LOGIC 11 1 LOGIC AND TURING MACHINES 11 2 LOGIC AND PRIMITIVE RECURSIVE FUNCTIONS 12 MODELS 12 1 THE SIZE AND NUMBER OF MODELS 12 2 EQUIVALENCE RELATIONS 12 3 THE L¨OWENHEIM–SKOLEM AND COMPACTNESS THEOREMS 13 THE EXISTENCE OF MODELS 13 1 OUTLINE OF THE PROOF 13 2 THE FIRST STAGE OF THE PROOF 13 3 THE SECOND STAGE OF THE PROOF 13 4 THE THIRD STAGE OF THE PROOF 13 5 NONENUMERABLE LANGUAGES 14 PROOFS AND COMPLETENESS 14 1 SEQUENT CALCULUS 14 2 SOUNDNESS AND COMPLETENESS 14 3 OTHER PROOF PROCEDURES AND HILBERT’S THESIS 15 ARITHMETIZATION 15 1 ARITHMETIZATION OF SYNTAX 15 2 G¨ODEL NUMBERS 15 3 MORE G¨ODEL NUMBERS 16 REPRESENTABILITY OF RECURSIVE FUNCTIONS 16 1 ARITHMETICAL DE?NABILITY 16 2 MINIMAL ARITHMETIC AND REPRESENTABILITY 16 3 MATHEMATICAL INDUCTION 16 4 ROBINSON ARITHMETIC 17 INDE?NABILITY, UNDECIDABILITY, INCOMPLETENESS 17 1 THE DIAGONAL LEMMA AND THE LIMITATIVE THEOREMS 17 2 UNDECIDABLE SENTENCES 17 3 UNDECIDABLE SENTENCES WITHOUT THE DIAGONAL LEMMA 18 THE UNPROVABILITY OF CONSISTENCY CONTENTS FURTHER TOPICS 19 NORMAL FORMS 19 1 DISJUNCTIVE AND PRENEX NORMAL FORMS 19 2 SKOLEM NORMAL FORM 19 3 HERBRAND’S THEOREM 19 4 ELIMINATING FUNCTION SYMBOLS AND IDENTITY 20 THE CRAIG INTERPOLATION THEOREM 20 1 CRAIG’S THEOREM AND ITS PROOF 20 2 ROBINSON’S JOINT CONSISTENCY THEOREM 20 3 BETH’S DE?NABILITY THEOREM 21 MONADIC AND DYADIC LOGIC 21 1 SOLVABLE AND UNSOLVABLE DECISION PROBLEMS 21 2 MONADIC LOGIC 21 3 DYADIC LOGIC 22 SECOND-ORDER LOGIC 23 ARITHMETICAL DE?NABILITY 23 1 ARITHMETICAL DE?NABILITY AND TRUTH 23 2 ARITHMETICAL DE?NABILITY AND FORCING 24 DECIDABILITY OF ARITHMETIC WITHOUT MULTIPLICATION 25 NONSTANDARD MODELS 25 1 ORDER IN NONSTANDARD MODELS 25 2 OPERATIONS IN NONSTANDARD MODELS 25 3 NONSTANDARD MODELS OF ANALYSIS 26 RAMSEY’S THEOREM 26 1 RAMSEY’S THEOREM: FINITARY AND IN?NITARY 26 2 K¨ONIG’S LEMMA 27 MODAL LOGIC AND PROVABILITY 27 1 MODAL LOGIC 27 2 THE LOGIC OF PROVABILITY 27 3 THE FIXED POINT AND NORMAL FORM THEOREMS HINTS FOR SELECTED PROBLEMS