Ex Libris                        Wanted                           
blank

       
blank

blank
blank
blank
blank
Rockingham G.R. Deducibility and Decidability
Rockingham G.R.  Deducibility and Decidability







?
Ctrl+Enter


: Deducibility and Decidability

: Rockingham G.R.

:

The classic results obtained by Gödel, Tarski, Kleene, and Church in the early thirties are the finest flowers of symbolic logic. They are of fundamental importance to those investigations of the foundations of mathematics via the concept of a formal system that were inaugurated by Frege, and of obvious significance to the mathematical disciplines, such as computability theory, that developed from them.

Derived from courses taught by the author over several years, this new exposition presents all of the results with their original proofs and central concepts in a manner that is unified by a systematic grounding of the notion of effectiveness in the semantics of the existential quantifier. Logicians and non-mathematicians, repelled by detail which is not obviously relevant in the standard textbooks, will be able to reach the heart of the matter with a minimum of fuss.


: en

: /

:

ed2k: ed2k stats

: 1990

: 162

: 05.04.2008

: | | ID
blank
$Cl \Sigma tb$      69
$Tr_{B}$      6466 68 69 107
$\Delta fm$      68
$\imath$      68 84
$\mathbb{F}$      140
$\mathbb{T}$      140
$\mathbf{P}$      15 72 8998 105108 114 128131
$\mathbf{P}^{a,m}$      130
$\mathbf{Q}$      75 22 72 108 114 117118 129
$\mathbf{Q}^{+}$, $\mathbf{Q}!$      21
$\mathbf{Q}^{O}$, $\mathbf{Q}^{O}!$, $\mathbf{Q}'$      22
$\mathbf{R}$      75 72 9899 110 116117 121 129
$\mathbf{S}$      1 24 72 98
$\mathbf{S}^{+}$      45
$\mathbf{S}_{1}$      see Kleene
$\mathcal{R}$      93
$\mathcal{T}_{1}$      see Kleene
$\omega$-completeness      see Property
$\omega.2$      
96 fn.
$\Sigma cl$, $\Sigma fm$, $\Sigma tb$      6869
$\Sigma$      2 6162
$\Sigma$-provable      26 46
$\Sigma$-provable, $\Sigma pr$      69 8687 106108 114 121
$\Sigma$-provable, $\Sigma_{n} pr$, $\Pi_{n} pr$      126127 128
$\Sigma$-provable, $\Sigma_{n}$-, $\Pi_{n}$-provable      125 126
$\varepsilon_{0}$      96 fn. 97 104
$^{2} \mathbf{P}$, $ ^{2} \mathbf{P}^{+}$      114
A      8 137 142
Ackermann, W.      87 112 119
Adequacy Theorem      131 148
ap, $ap_l$      68
Application (formal), [ ]      139
Application (formal), [ ], ap      68
Application (formal), [ ], Application Principle      142 149
Application (formal), [ ], pap      84
Application (formal), [ ], partial application (formal), [ ]      85
Application (informal)      7374 7980 134135
Arbib, M.A.      122
Argument      135
Arithmetical concepts      8 89 97 111
Arithmetization      5972 esp. 6566 106 107 108
Arkadencafe (Vienna)      101
Ars Combinatoria      see Leibniz
Assign/ment, | |      140 f. 148
Assign/ment, | |, being standardly assigned T      90 109 111115 119 142
Assign/ment, | |, Putnam assign/ment, | |      131
Assign/ment, | |, standard assign/ment, | |      142 (see also Model)
Axiomatization      8 89
B      11
BD      55
Begriffsschrift      67 100
Benacerraf, P.      7
Bernays, P.      131
Berry, G.G.      4
Beth numbers      50 53
Beth, E.W.      6
Binary (notation, representation)      95
Branch      3234 143
Brouwer Koenig Infinity Lemma      3336
Brouwer, L.E.J.      33 35 101
Buridan, J.      78 84
Cantor's argument      10 37 73 81 110
Cantor, G.      10 60 96
Cargile, J.      76
Carnap on definite descriptions      141142
Carnap on syntax      6566
Carnap's Fixed-point Lemma      8384 8998 130
Carnap's fixed-point, C      8285 8998 109 115 117 126 130
Carnap, carn      85
Carnap, R.      101102
casus      86
Category-mistake      75
Chain      3233
Chandra, A.K.      39
Charles II      113
Choice      see Function
Chomsky, A.N.      67
Church's Theorem      117119
Church's thesis      4043 4749 57 72 84 115 116
Church, A.      45 60 6667 79 115
Cichon, E.A.      95
Classification      78
Clos/ed, closure $\Sigma cl$, $Cl \Sigma tb$      69
Clos/ed, closure of $\Sigma$-tableaux      24
Clos/ed, closure of regular tableaux      145
Clos/ed, closure, Rgcl, Clrgtb      71
Closure condition      147
Clrgtb      71
cnjn      64
Co-denoting      135
Co-extensive      8 43f. 55 57 114 135
Cock Robin      35 43
Code number      see Encoding
Cohen, L.J.      86
Compatibility, formal      117 118 130
Complement      44 46 135
Complete/ness      45 14 1819 1922 67 89 148149 110
composition      85
Composition, comp      85
Concatenation      58 136
Concatenation, $ ^{\frown}$      58
Confirm/ation, confirm/ation ability      40 4344 Procedure)
Congruen/t, congruence      83 138
conjugate      143
Conjugate, $\bar{ }$      144
Connected/ness      1 5 6 93
Connectives      136
Consisten/t, consistency      90 91 93 110 147 148
Constructive choice function      121
Constructive techniques      2022 9091
Constructive truth      3536 110
Constructivists      90 93 121
Continuum, uncountability of      10
Convention T      114
Corners, $\ulcorner \urcorner$      1 (see also Quotation)
Correctness Theorem      131 148
Cretan/s      see Paradox Liar
Cross-reference      8384
Curry, H.B.      79
Cut-free      145 148
Cut-Rule      144 148
Dash/ing      2 6162
Dash/ing, dash      62 68
Davidson, D.      67 112 113
Davis, M.      40
Dbl      89
Ddn      89
de Fermat, P.      35 43
Deci/sion, lability      67 72 115118 120 Procedure)
Dedekind, R.      4 15 5051
Deduc/tion, cf.      115118
Deduc/tion, deducibility, formal, $\vdash$      3 16 19 101 145
Deduc/tion, deducibility, formal, $\vdash$, Deducible, Dbl      8998 105108 126 128131
Deduc/tion, deducibility, formal, $\vdash$, Fmddn, Fmdbl      70 72
Definition      8 105 114115
Definition, recursive      49 f. 8687 111
Degree      see Sentence-form
denote      78 135
Descend/ant, descendance-chain      see Sentence-form
Description operator      14 136 142 149
Descriptions, definite      141142
Descriptor      135
Descriptor-form      139
Descriptor-form, $\Delta$-descriptor-form      23 56
Descriptor-form, $\Sigma$-descriptor-form      23
Descriptor-form, Dscfm      67
Descriptor-letter      see Letter/s
diag      82
diagg      85
Diagonal, diagonal argument, diagonal procedure      73 102
Diagonalization      7388
Diagonalization of a predicate      73 90 110
Diagonalization of a predicate-form      82 85 90
Diagonalization, diag      82
Diagonalization, diagg      85
DICTIONARY      20 139
Dictionary, standard dictionary      139140
Dirichlet, P.G.L.      20 108
Disconfirm/ation, disconfirmability      44 (see also Predicate Procedure)
Domain      4548 135
Dreben, B.      120
Dscfm      67
dsjn      64
Dummett, M.A.E.      4 35 103 134
e      8 137 142
Edwards, H.      35 65
Effective/ness      80 (see also Procedure Relation Function Operation Letter/s)
Ehrenfeucht, A.      122
Elementary      5657 70
Eliminability      130
Enc      54
Encod/e, enc      54
Encod/e, encoding      5253
Enderton, H.B.      9
Entscheidungsproblem      117 119120
Epimenides      see Paradox Liar
Equivalence, analytical equivalence      76
Equivalence, elementary equivalence      6
Equivalence, local, global equivalence      107 114
Etchemendy, J.      113
Eubulides      see Paradox Liar
Euclid      2021
Expressions, formal      10 137139
Extension of predicate      89 4447 115 135
Extension of sequence      33
Extension of set      15 130131 147
Extension rules for tableaux      26 125 143
Extensionality      4 9 135
Extensionality, cf.      105
Feferman, S.      46 84 92 93 94 129
Finit/ary, fistic      see Hilbert's Programme
fit      140
fixed-point      see Carnap Function Jeroslow Montague
Fmdbl      72 98100 108
Fmddn      70
FN      68
FORM      see Subject- sentence- descriptor-
Form, simple      64 87
Form, top-form      143
Form, tpfm      69
Form, universal-form      21 147
Formal numerals      2
Formal numerals, Fnsq, fn      6164 68
Formal numerals, theoretically dispensable      14
Formal system      100104
free      139
Frege, F.L.G.      4 14 21 50 67 78 100101 103 141 142
Friedman, H.      95 112
Fulfilment      2728 31
Function      4548 136
Function, choice function      120 122 128
Function, fixed-point of a function      82 fn.
Function, propositional function      78 134
G      8992 94 112 126
Geach, P.T.      78 79
Gentzen, G.      97
Geometry      2021
Goedel on mathematical intuition      102103
Goedel's First Theorem      79 99 100103 117
Goedel's second theorem      99 103104 129
Goedel's witness G to $\mathbf{P}$'s incompleteness      8992 94
Goedel, K.      9 20 24 42 54 60 67 76 79 83 89 90 91 93 9899 101105 109 110 111 112 117 119 121123
Goedel-number      60
Goedel-number, **      61 88
Goedel-number, fn      68
Goldfarb, W.      120
Goodstein, R.L., Goodstein's Theorem      9597
Grelling, K.      110
Grounded (form)      see Sentence-form Induction Hierarchy
Grzegorczyk, A.      56
Hallett, M.      10
halt/ing      30 38
Hardy, G.H.      120 fn.
Harrington, L.      95
Haugeland, J.      37
Henkin, L.      92
Heterologicality      110
Hierarchy, arithmetical      124128
Hilbert's Programme      91 103104
Hilbert, D.      60 fn. 87 91 100 103104 111 112 119 131 142
Hook, hk      64
Hook, hkup      71
Hook-up      145
IFF      10 fh.
Imdsc      106
Incompleteness of $\mathbf{P}$      20 8998 105 Goedel)
Incompleteness of $\mathbf{Q}$      1922
Incompleteness of $\mathbf{R}$      98
Incompleteness of $\mathbf{S}$      5 98
Inconsistency      see Consistency
Independence classic independence proofs re-vamped      98
Independence from $\mathbf{P}$      8998
Independence from $\mathbf{Q}$      2022
Independence from $\mathbf{S}$      5
INDEX      see Sentence-form
Induction on grounded forms      13
Induction on numbers      34 15 9697 103 126
Induction on ordinals      9697
Infinit/ary, infinitistic      see Hilbert's Programme
Intuition, mathematical      102103
Intuitionists      see Constructivists
Irreflexiv/e, Irreflexivity      1 5 6
Isaacson, D.      9798
Isomorphism      6
Jeffrey, R.G.      143
Jeroslow's Fixed-point Lemma      88
Jeroslow's fixed-point, J      88
Jeroslow, jer      88
Jeroslow, R.G.      88
Jones, J.P.      22
Kalmar, L.      5657
Kaplan, D.      79
Kirby, L.      95 96
Kleene, $S_1$, $\mathfrak{T}_1$      70 (see also Recursion Theorem)
Kleene, S.C.      19 42 69 87 115 116 121 124 131 139
Klein, F.      20
Kneale, W.      77
Kneebone, G. T.      101
Kochen, S.      98
Koenig, J.      33 35 82
Kreisel, G.      60 fn. 106 130
Kripke, S.      98
Kronecker, L.      65 fn.
L      1 137 142
Laius      76
Langford, C.H.      5 9
le Veque, W.J.      20
Leibniz, G.W. v.      118119
Length      136
Length in Mostowski's sense      93 122
Letter/s      6667 136137
Levy, A.      106 fn. 130
Lewis, D.      37
Lewis, H.R.      39 120
Limitations by statute      41 f.
Lingua Philosophica      see Leibniz
Lob's Theorem      99
Lob, M.H.      92 94
Lobatschewsky, N.I.      2021
Logic, second-order      87 112 114
1 2
blank
blank
blank
HR
@Mail.ru
       © , 2004-2020
   | Valid HTML 4.01! | Valid CSS!