green numbers give full details.     |    back to list of philosophers     |     expand these ideas

Ideas of Peter Smith, by Text

[British, b.1944, At the University of Aberystwyth, and then at Cambridge University.]

2007 Intro to Gödel's Theorems
01.1 p.1 Natural numbers have zero, unique successors, unending, no circling back, and no strays
01.1 p.2 If everything that a theory proves is true, then it is 'sound'
01.1 p.2 A theory is 'negation complete' if one of its sentences or its negation can always be proved
01.3 p.5 There cannot be a set theory which is complete
02.1 p.8 An 'injective' ('one-to-one') function creates a distinct output element from each original
02.1 p.8 The 'range' of a function is the set of elements in the output set created by the function
02.1 p.8 A 'total function' maps every element to one element in another set
02.1 p.8 A 'surjective' ('onto') function creates every element of the output set
02.1 p.8 A 'bijective' function has one-to-one correspondence in both directions
02.1 n1 p.8 A 'partial function' maps only some elements to another set
02.2 p.9 'Effective' means simple, unintuitive, independent, controlled, dumb, and terminating
02.3 p.13 A set is 'enumerable' is all of its elements can result from a natural number function
02.4 p.15 A set is 'effectively enumerable' if a computer could eventually list every member
02.4 p.16 A finite set of finitely specifiable objects is always effectively enumerable (e.g. primes)
02.5 p.16 The set of ordered pairs of natural numbers <i,j> is effectively enumerable
03.4 p.23 A 'theorem' of a theory is a sentence derived from the axioms using the proof system
03.4 p.24 Soundness is true axioms and a truth-preserving proof system
03.4 p.24 A theory is 'sound' iff every theorem is true (usually from true axioms and truth-preservation)
03.4 p.24 A theory is 'negation complete' if it proves all sentences or their negation
03.4 p.24 A theory is 'decidable' if all of its sentences could be mechanically proved
03.4 p.25 'Complete' applies both to whole logics, and to theories within them
03.6 p.26 Any consistent, axiomatized, negation-complete formal theory is decidable
04.5 p.33 For primes we write (x not= 1 ∧ ∀u∀v(u x v = x → (u = 1 ∨ v = 1)))
04.7 p.36 Being 'expressible' depends on language; being 'capture/represented' depends on axioms and proof system
05 Intro p.37 The thorems of a nice arithmetic can be enumerated, but not the truths (so they're diffferent)
08.1 p.51 Baby arithmetic covers addition and multiplication, but no general facts about numbers
08.3 p.55 Robinson Arithmetic 'Q' has basic axioms, quantifiers and first-order logic
08.3 p.55 Baby Arithmetic is complete, but not very expressive
08.4 p.57 Robinson Arithmetic (Q) is not negation complete
09.1 p.59 A 'natural deduction system' has no axioms but many rules
10.1 p.71 The logic of arithmetic must quantify over properties of numbers to handle induction
10.7 p.79 Incompleteness results in arithmetic from combining addition and successor with multiplication
10.7 n8 p.79 Multiplication only generates incompleteness if combined with addition and successor
11.3 p.87 Two functions are the same if they have the same extension
14.1 p.120 The number of Fs is the 'successor' of the Gs if there is a single F that isn't G
18.1 p.156 Two routes to Incompleteness: semantics of sound/expressible, or syntax of consistency/proof
18.2 p.157 The reals contain the naturals, but the theory of reals doesn't contain the theory of naturals
20.5 p.174 An argument is a 'fixed point' for a function if it is mapped back to itself
21.5 p.180 No nice theory can define truth for its own language
22.3 p.190 The Comprehension Schema says there is a property only had by things satisfying a condition
23.4 p.206 Second-order arithmetic can prove new sentences of first-order
23.5 p.209 The 'ancestral' of a relation is a new relation which creates a long chain of the original relation
23.5 p.211 All numbers are related to zero by the ancestral of the successor relation
27.7 p.258 The truths of arithmetic are just true equations and their universally quantified versions