Ideas from 'Intro to Gödel's Theorems' by Peter Smith [2007], by Theme Structure

[found in 'An Introduction to Gödel's Theorems' by Smith,Peter [CUP 2007,978-0-521-67453-9]].

Click on the Idea Number for the full details    |     back to texts     |     expand these ideas


4. Formal Logic / F. Set Theory ST / 4. Axioms for Sets / a. Axioms for sets
There cannot be a set theory which is complete
5. Theory of Logic / A. Overview of Logic / 7. Second-Order Logic
Second-order arithmetic can prove new sentences of first-order
5. Theory of Logic / E. Structures of Logic / 5. Functions in Logic
A 'total function' maps every element to one element in another set
A 'partial function' maps only some elements to another set
Two functions are the same if they have the same extension
An argument is a 'fixed point' for a function if it is mapped back to itself
The 'range' of a function is the set of elements in the output set created by the function
5. Theory of Logic / E. Structures of Logic / 7. Predicates in Logic
The Comprehension Schema says there is a property only had by things satisfying a condition
5. Theory of Logic / E. Structures of Logic / 8. Theories in Logic
A 'theorem' of a theory is a sentence derived from the axioms using the proof system
5. Theory of Logic / H. Proof Systems / 4. Natural Deduction
A 'natural deduction system' has no axioms but many rules
5. Theory of Logic / I. Semantics of Logic / 2. Formal Truth
No nice theory can define truth for its own language
5. Theory of Logic / J. Model Theory in Logic / 2. Isomorphisms
A 'bijective' function has one-to-one correspondence in both directions
An 'injective' ('one-to-one') function creates a distinct output element from each original
A 'surjective' ('onto') function creates every element of the output set
5. Theory of Logic / K. Features of Logics / 3. Soundness
If everything that a theory proves is true, then it is 'sound'
Soundness is true axioms and a truth-preserving proof system
A theory is 'sound' iff every theorem is true (usually from true axioms and truth-preservation)
5. Theory of Logic / K. Features of Logics / 4. Completeness
A theory is 'negation complete' if it proves all sentences or their negation
A theory is 'negation complete' if one of its sentences or its negation can always be proved
'Complete' applies both to whole logics, and to theories within them
5. Theory of Logic / K. Features of Logics / 5. Incompleteness
Two routes to Incompleteness: semantics of sound/expressible, or syntax of consistency/proof
Gödel's First Theorem sabotages logicism, and the Second sabotages Hilbert's Programme
5. Theory of Logic / K. Features of Logics / 7. Decidability
'Effective' means simple, unintuitive, independent, controlled, dumb, and terminating
A theory is 'decidable' if all of its sentences could be mechanically proved
Any consistent, axiomatized, negation-complete formal theory is decidable
5. Theory of Logic / K. Features of Logics / 8. Enumerability
A set is 'enumerable' is all of its elements can result from a natural number function
A finite set of finitely specifiable objects is always effectively enumerable (e.g. primes)
A set is 'effectively enumerable' if a computer could eventually list every member
The set of ordered pairs of natural numbers <i,j> is effectively enumerable
The thorems of a nice arithmetic can be enumerated, but not the truths (so they're diffferent)
5. Theory of Logic / K. Features of Logics / 9. Expressibility
Being 'expressible' depends on language; being 'capture/represented' depends on axioms and proof system
6. Mathematics / A. Nature of Mathematics / 3. Numbers / a. Numbers
For primes we write (x not= 1 ∧ ∀u∀v(u x v = x → (u = 1 ∨ v = 1)))
6. Mathematics / A. Nature of Mathematics / 3. Numbers / g. Real numbers
The reals contain the naturals, but the theory of reals doesn't contain the theory of naturals
6. Mathematics / A. Nature of Mathematics / 3. Numbers / q. Arithmetic
The truths of arithmetic are just true equations and their universally quantified versions
6. Mathematics / B. Foundations for Mathematics / 3. Axioms for Number / a. Axioms for numbers
All numbers are related to zero by the ancestral of the successor relation
The number of Fs is the 'successor' of the Gs if there is a single F that isn't G
6. Mathematics / B. Foundations for Mathematics / 3. Axioms for Number / b. Baby arithmetic
Baby arithmetic covers addition and multiplication, but no general facts about numbers
Baby Arithmetic is complete, but not very expressive
6. Mathematics / B. Foundations for Mathematics / 3. Axioms for Number / c. Robinson arithmetic
Robinson Arithmetic 'Q' has basic axioms, quantifiers and first-order logic
Robinson Arithmetic (Q) is not negation complete
6. Mathematics / B. Foundations for Mathematics / 3. Axioms for Number / d. Peano arithmetic
Natural numbers have zero, unique successors, unending, no circling back, and no strays
6. Mathematics / B. Foundations for Mathematics / 3. Axioms for Number / f. Mathematical induction
The logic of arithmetic must quantify over properties of numbers to handle induction
6. Mathematics / B. Foundations for Mathematics / 3. Axioms for Number / g. Incompleteness of Arithmetic
Multiplication only generates incompleteness if combined with addition and successor
Incompleteness results in arithmetic from combining addition and successor with multiplication
8. Modes of Existence / A. Relations / 4. Formal Relations / c. Ancestral relation
The 'ancestral' of a relation is a new relation which creates a long chain of the original relation