The shortest definition of a number in Peano arithmetic

摘要

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.