more on this theme     |     more from this text

Single Idea 10603

[filed under theme 6. Mathematics / B. Foundations for Mathematics / 4. Axioms for Number / f. Mathematical induction ]

Full Idea

If the logic of arithmetic doesn't have second-order quantifiers to range over properties of numbers, how can it handle induction?

Gist of Idea

The logic of arithmetic must quantify over properties of numbers to handle induction

Source

Peter Smith (Intro to Gödel's Theorems [2007], 10.1)

Book Ref

Smith,Peter: 'An Introduction to Gödel's Theorems' [CUP 2007], p.71

The 44 ideas from Peter Smith

10070 If everything that a theory proves is true, then it is 'sound' [Smith,P]
10069 A theory is 'negation complete' if one of its sentences or its negation can always be proved [Smith,P]
10068 Natural numbers have zero, unique successors, unending, no circling back, and no strays [Smith,P]
10073 There cannot be a set theory which is complete [Smith,P]
10074 A 'total function' maps every element to one element in another set [Smith,P]
10076 The 'range' of a function is the set of elements in the output set created by the function [Smith,P]
10079 A 'bijective' function has one-to-one correspondence in both directions [Smith,P]
10077 A 'surjective' ('onto') function creates every element of the output set [Smith,P]
10078 An 'injective' ('one-to-one') function creates a distinct output element from each original [Smith,P]
10075 A 'partial function' maps only some elements to another set [Smith,P]
10080 'Effective' means simple, unintuitive, independent, controlled, dumb, and terminating [Smith,P]
10081 A set is 'enumerable' is all of its elements can result from a natural number function [Smith,P]
10083 A set is 'effectively enumerable' if a computer could eventually list every member [Smith,P]
10084 A finite set of finitely specifiable objects is always effectively enumerable (e.g. primes) [Smith,P]
10085 The set of ordered pairs of natural numbers <i,j> is effectively enumerable [Smith,P]
10087 A theory is 'decidable' if all of its sentences could be mechanically proved [Smith,P]
10086 Soundness is true axioms and a truth-preserving proof system [Smith,P]
10598 A theory is 'negation complete' if it proves all sentences or their negation [Smith,P]
10597 'Complete' applies both to whole logics, and to theories within them [Smith,P]
10596 A theory is 'sound' iff every theorem is true (usually from true axioms and truth-preservation) [Smith,P]
10595 A 'theorem' of a theory is a sentence derived from the axioms using the proof system [Smith,P]
10088 Any consistent, axiomatized, negation-complete formal theory is decidable [Smith,P]
10599 For primes we write (x not= 1 ∧ ∀u∀v(u x v = x → (u = 1 ∨ v = 1))) [Smith,P]
10600 Being 'expressible' depends on language; being 'capture/represented' depends on axioms and proof system [Smith,P]
10601 The thorems of a nice arithmetic can be enumerated, but not the truths (so they're diffferent) [Smith,P]
10849 Baby arithmetic covers addition and multiplication, but no general facts about numbers [Smith,P]
10850 Baby Arithmetic is complete, but not very expressive [Smith,P]
10851 Robinson Arithmetic 'Q' has basic axioms, quantifiers and first-order logic [Smith,P]
10852 Robinson Arithmetic (Q) is not negation complete [Smith,P]
10602 A 'natural deduction system' has no axioms but many rules [Smith,P]
10603 The logic of arithmetic must quantify over properties of numbers to handle induction [Smith,P]
10604 Incompleteness results in arithmetic from combining addition and successor with multiplication [Smith,P]
10848 Multiplication only generates incompleteness if combined with addition and successor [Smith,P]
10605 Two functions are the same if they have the same extension [Smith,P]
10608 The number of Fs is the 'successor' of the Gs if there is a single F that isn't G [Smith,P]
10609 Two routes to Incompleteness: semantics of sound/expressible, or syntax of consistency/proof [Smith,P]
10610 The reals contain the naturals, but the theory of reals doesn't contain the theory of naturals [Smith,P]
10612 An argument is a 'fixed point' for a function if it is mapped back to itself [Smith,P]
10613 No nice theory can define truth for its own language [Smith,P]
10615 The Comprehension Schema says there is a property only had by things satisfying a condition [Smith,P]
10616 Second-order arithmetic can prove new sentences of first-order [Smith,P]
10618 All numbers are related to zero by the ancestral of the successor relation [Smith,P]
10617 The 'ancestral' of a relation is a new relation which creates a long chain of the original relation [Smith,P]
10619 The truths of arithmetic are just true equations and their universally quantified versions [Smith,P]