Sequence encoding without induction

DOI10.1002/MALQ.201200013MaRDI QIDQ2888636zbMATH OpenOpenAlexFDO

Authors Emil Jeřábek

Publication date 1 June 2012

Published in Mathematical Logic Quarterly (MLQ) (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1201.5835

zbMATH Keywords

sequential theoryweak arithmetic

Mathematics Subject Classification ID

First-order arithmetic and fragments (03F30)

Abstract: We show that the universally axiomatized, induction-free theory PA^- is a sequential theory in the sense of Pudl'ak [5], in contrast to the closely related Robinson's arithmetic.

Review text

Sequence encoding has become, since Gödel's proof of his incompleteness theorem, an indispensable tool in the study of arithmetical theories and related areas of mathematical logic. P.~Pudlák, during his work on interpretability, isolated a general concept of theories supporting encoding of sequences of their elements and called them sequential theories. In the present paper the sequentiality of the theory PA\(^{-}\) of discretely ordered commutative semirings with a least element (without the subtraction axiom) and therefore of all its simple extensions is proved. The theory PA\(^{-}\) is an induction-free theory and it is often used as an arithmetical base theory (like the theory Q). The main result can be adopted in a straightforward way to the theory of discretely ordered commutative rings.

Recommendations

• Growing commas. A study of sequentiality and concatenation
• On arithmetical first-order theories allowing encoding and decoding of lists
• The arithmetics of a theory
• scientific article; zbMATH DE number 3997781
• scientific article; zbMATH DE number 4185776

Cites work

• Axiomatizability by a schema
• Cuts, consistency statements and interpretations
• scientific article; zbMATH DE number 51556 (Why is no real title available?)
• Pairs, sets and sequences in first-order theories
• Some Prime Elements in the Lattice of Interpretability Types
• Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme I

Cited in

(11)

• On \(\mathsf{Q}\)
• Weak sequential theories of finite full binary trees
• The small-is-very-small principle
• The interpretation existence lemma
• Cofinal elementary extensions
• Peano Corto and Peano Basso: a study of local induction in the context of weak theories
• THE ARITHMETIC OF THE EVEN AND THE ODD
• A weak theory of building blocks
• Incompleteness of boundedly axiomatizable theories
• When bi-interpretability implies synonymy
• The Borel complexity of the class of models of first-order theories

This page was built for publication: Sequence encoding without induction

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2888636)