I am reading Chapter 8 Section 41 of Kleene's "Introduction to metamathematics" and I have encountered notion of "numeralwise expressibility". Next is a quote from the textbook:

"Let $P(x_1, ..., x_n)$ be an intuitive number-theoretic predicate. We say that $P(x_1, ... , x_n)$ is numeralwise expressible in the formal system, if there is a formula $\mathrm{P(x_1,...,x_n)}$ with no free variables other than the distinct variables $\mathrm{x_1,...,x_n}$ such that, for each particular $n$-tuple of natural numbers $x_1, ... , x_n$, (i) if $P(x_1, ..., x_n)$ is true then $\vdash \mathrm{P(x_1, ..., x_n)}$ and (ii) if $P(x_1, ..., x_n)$ is false then $\vdash \lnot \mathrm{P(x_1, ..., x_n)}$. "

Question 1: I have trouble understanding what does it mean for something to be true or false without any reference to deducibility. I thought that the whole point of formalism is that we introduce finitary concept of deducibility to encode "truth" as being "provability". I think there might be some misconception on my side here.

Question 2: What is the use of such definition? How is it helpful? Why do we need it?

Question 3: How do I check whether intuitive number-theoretic predicate is true or false?

I would appreciate any suggestions or comments!

  • $\begingroup$ It must be read more or less literally : we know "facts" about natural numbers. Are the expressive and deductive resources of first-order arithmetic "strong enough" to formalize and prove them ? On the deductive side, the answer is NO (see G's Incompleteness Th). $\endgroup$ – Mauro ALLEGRANZA Oct 10 '18 at 6:00
  • $\begingroup$ @MauroALLEGRANZA Aren't the facts we know about natural numbers coming from proofs about them? Is there some fact that does not come from a proof? $\endgroup$ – Daniels Krimans Oct 10 '18 at 6:06
  • $\begingroup$ Yes, they comes form proofs... but not necessarily from proofs in FOL arithmetic. Humans learned to count well before math logic. $\endgroup$ – Mauro ALLEGRANZA Oct 10 '18 at 6:09
  • $\begingroup$ @MauroALLEGRANZA does it mean that truth here means relative truth with respect to some different formal system? $\endgroup$ – Daniels Krimans Oct 10 '18 at 6:17
  • 1
    $\begingroup$ You can see Introduction to Numeralwise Expressibility and see Representability. $\endgroup$ – Mauro ALLEGRANZA Oct 10 '18 at 12:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.