The shortest definition of a number in Peano arithmetic

Mathematical Logic Quarterly 49 (1):83-86 (2003)
  Copy   BIBTEX

Abstract

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

Categories

Keywords

Reprint years

DOI

10.1002/malq.200310006

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 92,440

External links

Setup an account with your affiliations in order to access resources via your University's proxy server

Through your library

My notes

Similar books and articles

Sub-Theory of Peano Arithmetic.Andrew Boucher - unknown
On the complexity of models of arithmetic.Kenneth McAloon - 1982 - Journal of Symbolic Logic 47 (2):403-415.
Why Axiomatize Arithmetic?Charles Sayward - 2005 - Sorites 16:54-61.
Equivalence of F with a sub-theory of peano arithmetic.Andrew Boucher - manuscript
Models without indiscernibles.Fred G. Abramson & Leo A. Harrington - 1978 - Journal of Symbolic Logic 43 (3):572-600.
Model-theoretic properties characterizing peano arithmetic.Richard Kaye - 1991 - Journal of Symbolic Logic 56 (3):949-963.
Quantum Mathematics.J. Michael Dunn - 1980 - PSA: Proceedings of the Biennial Meeting of the Philosophy of Science Association 1980:512 - 531.
The strength of nonstandard methods in arithmetic.C. Ward Henson, Matt Kaufmann & H. Jerome Keisler - 1984 - Journal of Symbolic Logic 49 (4):1039-1058.
A model of peano arithmetic with no elementary end extension.George Mills - 1978 - Journal of Symbolic Logic 43 (3):563-567.
Peano arithmetic may not be interpretable in the monadic theory of linear orders.Shmuel Lifsches & Saharon Shelah - 1997 - Journal of Symbolic Logic 62 (3):848-872.
Minimal truth and interpretability.Martin Fischer - 2009 - Review of Symbolic Logic 2 (4):799-815.
“Strenge” arithmetics.Robert K. Meyer & Greg Restall - unknown
Iterations of satisfaction classes and models of peano arithmetic.Roman Murawski - 1992 - Mathematical Logic Quarterly 38 (1):59-84.
Expanding the additive reduct of a model of Peano arithmetic.Masahiko Murakami & Akito Tsuboi - 2003 - Mathematical Logic Quarterly 49 (4):363-368.

Analytics

Added to PP
2013-12-01

Downloads
31 (#519,952)

6 months
7 (#441,767)

Historical graph of downloads
How can I increase my downloads?

Citations of this work

Add more citations

References found in this work

A Note on Boolos' Proof of the Incompleteness Theorem.Makoto Kikuchi - 1994 - Mathematical Logic Quarterly 40 (4):528-532.
The false assumption underlying berry's paradox.James D. French - 1988 - Journal of Symbolic Logic 53 (4):1220-1223.

Add more references