more on this theme
|
more from this thinker
Single Idea 10850
[filed under theme 6. Mathematics / B. Foundations for Mathematics / 4. Axioms for Number / b. Baby arithmetic
]
Full Idea
Baby Arithmetic is negation complete, so it can prove every claim (or its negation) that it can express, but it is expressively extremely impoverished.
Gist of Idea
Baby Arithmetic is complete, but not very expressive
Source
Peter Smith (Intro to Gödel's Theorems [2007], 08.3)
Book Ref
Smith,Peter: 'An Introduction to Gödel's Theorems' [CUP 2007], p.55
The
44 ideas
from 'Intro to Gödel's Theorems'
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]
|
10076
|
The 'range' of a function is the set of elements in the output set created by the function
[Smith,P]
|
10074
|
A 'total function' maps every element to one element in another set
[Smith,P]
|
10077
|
A 'surjective' ('onto') function creates every element of the output set
[Smith,P]
|
10079
|
A 'bijective' function has one-to-one correspondence in both directions
[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]
|
10596
|
A theory is 'sound' iff every theorem is true (usually from true axioms and truth-preservation)
[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]
|
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]
|