Premium
The shortest definition of a number in Peano arithmetic
Author(s) -
Roy Dev K.
Publication year - 2003
Publication title -
mathematical logic quarterly
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.473
H-Index - 28
eISSN - 1521-3870
pISSN - 0942-5616
DOI - 10.1002/malq.200310006
Subject(s) - mathematics , peano axioms , second order arithmetic , discrete mathematics , order (exchange) , arithmetic , finance , economics
The shortest definition of a number by a first order formula with one free variable, where the notion of a formula defining a number extends a notion used by Boolos in a proof of the Incompleteness Theorem, is shown to be non computable. This is followed by an examination of the complexity of sets associated with this function.