2002/10/05 by Bhupinder Singh Anand, Anand, Bhupinder Singh · 5 citations
Computer Science · Mathematics · #03B10 #Computability, Logic, AI Algorithms #FOS: Mathematics #General Mathematics (math.GM) #math.GM #msc:03B10
paper · pdf · doi:10.48550/arxiv.math/0210078
v6; introduced ACI compliant notation for citations; replaced Corollary 1.2; corrected Corollary 14.3; other minor corrections and additions; 76 pages; an HTML version is available at http://alixcomsi.com/CTG_06_Consequences.htm
openalex publication_date 2002/10/05 · arxiv created 2003/05/11 · arxiv updated 2009/11/30 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We give a precise definition of a formal mathematical object as any symbol for an individual constant, predicate letter, or a function letter that can be introduced through definition into a formal mathematical language without inviting inconsistency. We then show: there is an elementary, recursive, number-theoretic relation that is not a formal mathematical object, since it is not the standard interpretation of any of its representations in Goedel's formal system P; the range of a recursive number-theoretic function does not always define a (recursively enumerable set) formal mathematical object consistently in any Axiomatic Set Theory that models P; there is no P-formula, Con(P), whose standard interpretation is unambiguously equivalent to Goedel's number-theoretic definition of "P is consistent"; every recursive number-theoretic function is not strongly representable in P; Tarski's definitions of "satisfiability" and "truth" can be made constructive, and intuitionistically unobjectionable, by reformulating Church's Thesis constructively; the classical definition of Turing machines can be extended to include self-terminating, converging, and oscillating routines; a constructive Church's Thesis implies, firstly, that every partial recursive number-theoretic function can be constructively extended as a unique total function, and, secondly, that we can define effectively computable functions that are not classically Turing-computable; Turing's and Cantor's diagonal arguments do not necessarily define Cauchy sequences.