When is arithmetic possible?

DOI10.1016/0168-0072(90)90053-5MaRDI QIDQ922533zbMATH OpenOpenAlexWikidataFDO

Authors Gregory Loren McColm

Publication date 1990

Published in Annals of Pure and Applied Logic (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0168-0072(90)90053-5

zbMATH Keywords

bounded inductionsexpressibilityparametrization

Mathematics Subject Classification ID

Inductive definability (03D70)

Review text

When a structure or class of structures admits an unbounded induction, arithmetic can be done on the stages of that induction; if only bounded inductions are admitted, then every inductively definable relation can be defined by a finite explicit expression. This article presents evidence that the converse is true, and investigates a combinatorial property equivalent to ``all \(L^{<\omega}_{\infty \omega}\)-definable relations are elementary.

Recommendations

• Whither relevant arithmetic?
• The (metaphysical) foundations of arithmetic?
• Arithmetic and the conditions of possible experience
• What Numbers Could Be (And, Hence, Necessarily Are)
• Arithmetic is determinate

Cites work

• A zero-one law for logic with a fixed-point operator
• An application of games to the completeness problem for formalized theories
• Classification theory and the number of non-isomorphic models
• Elementary induction on abstract structures
• scientific article; zbMATH DE number 3966062 (Why is no real title available?)
• scientific article; zbMATH DE number 3984616 (Why is no real title available?)
• On Moschovakis closure ordinals
• On the Computational Complexity of Algorithms
• Parametrization over inductive relations of a bounded number of variables
• Relational queries computable in polynomial time
• Some applications of the notions of forcing and generic sets
• SOME RAMSEY THEORY IN BOOLEAN ALGEBRA FOR COMPLEXITY CLASSES
• Some restrictions on simple fixed points of the integers
• Upper and lower bounds for first order expressibility

Cited in

(4)

• How to define a linear order on finite models
• When is scalar multiplication decidable?
• Tameness in least fixed-point logic and McColm's conjecture
• First order logic, fixed point logic and linear order

This page was built for publication: When is arithmetic possible?

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