TITLE:
A Proof of Syntactic Incompleteness of the Second-Order Categorical Arithmetic
AUTHORS:
Giuseppe Raguní
KEYWORDS:
Second order, Arithmetic, Categoricity, Incompleteness, Undecidability, Codes, Algorithmic Randomness
JOURNAL NAME:
Open Access Library Journal,
Vol.4 No.10,
October
26,
2017
ABSTRACT: Actually, Arithmetic is considered as syntactically incomplete. However, there are different types of arithmetical theories. One of the most important is the second-order Categorical Arithmetic (AR), which interprets the principle of induction with the so-called full semantics. Now, whoever concluded that AR is sintactically (or semantically, since categoricity implies equivalence of the two types of completeness) incomplete? Since this theory is not effectively axiomatizable, the incompleteness Theorems cannot be applied to it. Nor is it legitimate to assert that the undecidability of the statements is generally kept in passing from a certain theory (such as PA) to another that includes it (such as AR). Of course, although the language of AR is semantically incomplete, this fact does not imply that the same AR is semantically/sintactically incomplete. Pending a response to the previous question, this paper aims to present a proof of the syntactic/semantical incompleteness of AR, by examples based on the different modes of representation (i.e. codes) of the natural numbers in computation.