Representability and Formal Theories of Arithmetic

Question 1

Formal Theories of Arithmetic

Baby Arithmetic:

Answer 1

Numerals: Sn is the numeral that stands for n:

Power: can represent all r.e. relations weakly
Limitations: Cannot prove S0 not equal to S1

Question 2

Formal Theories of Arithmetic

Junior Arithmetic:

Answer 2

To get π1: Define < and add postulates

Proof formulas π0 cannot prove

Question 3

Formal Theories of Arithmetic

Finitely Axiomatized Theory: Robinson’s Q

Answer 3

Question 4

Formal Theories of Arithmetic

First-Order Dedekind Peano Arithmetic: DPA

Answer 4

Question 5

What is “expressing?”

Answer 5

Expressing is a mere matter of translation from English into a strict formalism

Nothing to do with theoremhood

Distinguish between ….

Expressing a predicate in formal language

and

Representing a predicate in a formal system

Question 6

What is “representing?”

Answer 6

Need to …

a) All true instances of the predicate are theorems;

b) All false intances are nontheorems

Allows us to connect computable proerties to theorems

Strong notion

Distinguish between ….

Expressing a predicate in formal language

and

Representing a predicate in a formal system

Question 7

How to represent in TNT:

Answer 7

a) If BlooP test can be written for some property of natural umbers - then prepresented in TNT.
Any primitive recursive predicate is represented in FOA

b) If terminator FlooP test can be written for some property of natural numbers, then property is represented in TNT.
Any recursive predicate in representable in FOA