A list of arithmetical structures complete with respect to the first-order definability
From MaRDI portal
Publication:5941257
DOI10.1016/S0304-3975(00)00113-4zbMath0971.03035OpenAlexW2033524652WikidataQ127662677 ScholiaQ127662677MaRDI QIDQ5941257
Publication date: 20 August 2001
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/s0304-3975(00)00113-4
arithmetical structureelementary definabilityfirst-order definabilityPascal's triangles modulo \(n\)undecidable theories
Binomial coefficients; factorials; (q)-identities (11B65) Decidability (number-theoretic aspects) (11U05) Classical first-order logic (03B10) Decidability of theories and sets of sentences (03B25) Basic properties of first-order languages and structures (03C07)
Related Items
Some new results in monadic second-order arithmetic ⋮ Computational complexity of logical theories of one successor and another unary function ⋮ A note on definability in fragments of arithmetic with free unary predicates ⋮ The theory of ceers computes true arithmetic ⋮ The lattice of definability: origins, recent developments, and further directions ⋮ DECIDABILITY AND CLASSIFICATION OF THE THEORY OF INTEGERS WITH PRIMES ⋮ On arithmetical first-order theories allowing encoding and decoding of lists ⋮ Decidability of the theory of the natural integers with the Cantor pairing function and the successor ⋮ INTERPRETING ARITHMETIC IN THE FIRST-ORDER THEORY OF ADDITION AND COPRIMALITY OF POLYNOMIAL RINGS
Cites Work
- The elementary theory of the natural lattice is finitely axiomatizable
- Twins problem in formal arithmetic
- Logically defined subsets of \(\mathbb{N}{}^ k\)
- Complexity of logical theories involving coprimality
- The theory of \(\langle \mathbb{N} , +, V_ k, V_ l\rangle\) is undecidable
- The theory of successor with an extra predicate
- Büchi's monadic second order successor arithmetic.
- Presburgerness of predicates regular in two number systems
- On Pascal triangles modulo a prime power
- Theories of generalized Pascal triangles
- Definability, decidability, complexity
- Contribution à l'étude d'une conjecture de théorie des nombres par le codage ZBV. (Contribution to the study of a conjecture of number theory by ZBV coding)
- Presburger arithmetic and recognizability of sets of natural numbers by automata: New proofs of Cobham's and Semenov's theorems
- Solvability of the theory of integers with addition, order, and multiplication by an arbitrary number
- All arithmetical sets of powers of primes are first-order definable in terms of the successor function and the coprimeness predicate
- The elementary theory of finite fields
- Decidability and undecidability of theories with a predicate for the primes
- Decidability and essential undecidability
- Elementary Properties of Ordered Abelian Groups
- Weak Second‐Order Arithmetic and Finite Automata
- Definability in terms of the successor function and the coprimeness predicate in the set of arbitrary integers
- Answer to a problem raised by J. Robinson: The arithmetic of positive or negative integers is definable from successor and divisibility
- Decision Problems of Finite Automata Design and Related Arithmetics
- An Infinite Product for e
- On the bounded monadic theory of well-ordered structures
- ON CERTAIN EXTENSIONS OF THE ARITHMETIC OF ADDITION OF NATURAL NUMBERS
- A combinatorial approach to the theory of ω-automata
- Notes on Binomial Coefficients Iii-Any Integer Divides Almost All Binomial Coefficients†
- Model-interpretability into trees and applications
- A note on undecidable extensions of monadic second order successor arithmetic
- Completeness Theorems, Incompleteness Theorems and Models of Arithmetic
- Undecidable extensions of Skolem arithmetic
- Undecidable extensions of Büchi arithmetic and Cobham-Semënov Theorem
- More on an undecidability result of Bateman, Jockusch and Woods
- Definability in structures of finite valency
- Definability and decidability issues in extensions of the integers with the divisibility predicate
- Decidability and undecidability of extensions of second (first) order theory of (generalized) successor
- On the base-dependence of sets of numbers recognizable by finite automata
- Definability in the monadic second-order theory of successor
- Decidability of Second-Order Theories and Automata on Infinite Trees
- Uniform tag sequences
- Definability and decision problems in arithmetic
- A reduction in the number of primitive ideas of arithmetic
- On direct products of theories
- Existential Definability in Arithmetic
- Concatenation as a basis for arithmetic
- Decidability of the theory of the natural integers with the Cantor pairing function and the successor
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
